Abstract

A new family of interconnection networks, termed the nested crossbar, has been developed. These networks are particularly well suited for processor arrays using optical interconnections due to their high bisection width and high degree of spatial invariance. While a k-ary m-dimensional hypercube has a connectivity ranging from a ring to a binary hypercube, a base-b, m-dimensional nested crossbar has a connectivity ranging from a binary hypercube to a full crossbar (fully connected network). The nested crossbar connection networks were designed to take full advantage of the benefits of optical interconnects. Their high bisection width (a measure of the global nature of a connection topology) allows them to perform efficient, communication intensive computation. Although high bisection width networks occupy a great deal of area in fully electronic implementations, optically interconnected VLSI nested crossbars have very slow area growth rates. This is due to their high degree of spatial invariance which allows holographic nested crossbar connections to be formed in a space invariant or basis set connection system. The nested crossbar networks allow use of minimum numbers of optoelectronic transmitters and detectors to solve certain problems in a given time. For example, a 2-D nested crossbar requiring O(N^3/2) optoelectronic components can be used to compute a matrix-vector multiplication in O(logN) time (N is the number of elements in the vector). A base 2 nested crossbar can compute the multiplication in O(N^1/2 log²N) time with only O(N) transmitters and detectors.

© 1989 Optical Society of America