Abstract

A family of new interconnection networks, termed the nested crossbar, has been developed. These networks are particularly well suited to optical interconnects due to their high bisection width and high degree of space invariance. Algorithms have been developed for computing vector–matrix multiplication with nested crossbar connected processor arrays with time growth rates between O(1) and O(N1/2). (N is the number of elements in the vector.) When these algorithms are implemented on holographic optically interconnected very large scale integrated processor arrays, the nested crossbar networks have area and time growth rates close to fundamental lower bounds. The nested crossbar networks also allow the use of a minimum number of transmitters and detectors.

© 1990 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. T. Kohonen, Self-Organization and Associative Memory (Springer-Verlag, Berlin, 1984).
  2. J. J. Hopfield, “Neural Networks and Physical Systems with Emergent Collective Computational Abilities,” Proc. Natl. Acad. Sci. USA 79, 2554–2558 (1982).
    [CrossRef] [PubMed]
  3. A. K. Jain, Fundamentals of Digital Image Processing (Prentice-Hall, Englewood Cliffs, NJ, 1989).
  4. J. Jau, F. Kiamilev, Y. Fainman, S. Esener, S. H. Lee, “Optical Expert System Based on Matrix-Algebraic Formulation,” J. Opt. Soc. Am. A 4(13), 57 (1987).
  5. C. Seitz, “Concurrent VLSI Architectures,” IEEE Trans. Comput. C-33, 1247–1265 (1984).
    [CrossRef]
  6. C. Mead, L. Conway, Introduction to VLSI Systems (Addison-Wesley, Menlo Park, CA, 1980), pp. 271–276.
  7. M. R. Feldman, S. C. Esener, C. C. Guest, S. H. Lee, “Comparison Between Optical and Electrical Interconnects Based on Power and Speed Considerations, Appl. Opt. 27, 1742–1751 (1988).
    [CrossRef] [PubMed]
  8. M. R. Feldman, C. C. Guest, T. J. Drabik, S. C. Esener, “Comparison Between Electrical and Free Space Optical Interconnects for Fine Grain Processor Arrays Based on Connection Density Capabilities,” Appl. Opt. 28, 3820–3829 (1989).
    [CrossRef] [PubMed]
  9. B. K. Jenkins, P. Chavel, R. Forchheimer, A. A. Sawchuk, T. C. Strand, “Architectural Implications of a Digital Optical Processor,” Appl. Opt. 23, 3465–3474 (1984).
    [CrossRef] [PubMed]
  10. J. D. Ullman, Computational Aspects of VLSI (Computer Science Press, Rockville, MD, 1984), Chap. 2.
  11. J. W. Goodman, F. I. Leonberger, S. Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc. IEEE 72, 850–866 (1984).
    [CrossRef]
  12. W. J. Dally, A VLSI Architecture for Concurrent Data Structures (Kluwer Academic Publishers, Norwell, MA, 1987).
    [CrossRef]
  13. T. J. Drabik, M. R. Feldman, “Holographic Optical Time-Multiplexed Interconnection of Hypercubes,” submitted to IEEE Trans. Comput.
  14. M. R. Feldman, C. C. Guest, “Interconnect Density Capabilities of Computer Generated Holograms for Optical Interconnection of Very Large Scale Integrated Circuits,” Appl. Opt. 28, 3134–3137 (1989).
    [CrossRef] [PubMed]

1989 (2)

1988 (1)

1987 (1)

1984 (3)

C. Seitz, “Concurrent VLSI Architectures,” IEEE Trans. Comput. C-33, 1247–1265 (1984).
[CrossRef]

B. K. Jenkins, P. Chavel, R. Forchheimer, A. A. Sawchuk, T. C. Strand, “Architectural Implications of a Digital Optical Processor,” Appl. Opt. 23, 3465–3474 (1984).
[CrossRef] [PubMed]

J. W. Goodman, F. I. Leonberger, S. Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc. IEEE 72, 850–866 (1984).
[CrossRef]

1982 (1)

J. J. Hopfield, “Neural Networks and Physical Systems with Emergent Collective Computational Abilities,” Proc. Natl. Acad. Sci. USA 79, 2554–2558 (1982).
[CrossRef] [PubMed]

Athale, R. A.

J. W. Goodman, F. I. Leonberger, S. Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc. IEEE 72, 850–866 (1984).
[CrossRef]

Chavel, P.

Conway, L.

C. Mead, L. Conway, Introduction to VLSI Systems (Addison-Wesley, Menlo Park, CA, 1980), pp. 271–276.

Dally, W. J.

W. J. Dally, A VLSI Architecture for Concurrent Data Structures (Kluwer Academic Publishers, Norwell, MA, 1987).
[CrossRef]

Drabik, T. J.

Esener, S.

Esener, S. C.

Fainman, Y.

Feldman, M. R.

Forchheimer, R.

Goodman, J. W.

J. W. Goodman, F. I. Leonberger, S. Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc. IEEE 72, 850–866 (1984).
[CrossRef]

Guest, C. C.

Hopfield, J. J.

J. J. Hopfield, “Neural Networks and Physical Systems with Emergent Collective Computational Abilities,” Proc. Natl. Acad. Sci. USA 79, 2554–2558 (1982).
[CrossRef] [PubMed]

Jain, A. K.

A. K. Jain, Fundamentals of Digital Image Processing (Prentice-Hall, Englewood Cliffs, NJ, 1989).

Jau, J.

Jenkins, B. K.

Kiamilev, F.

Kohonen, T.

T. Kohonen, Self-Organization and Associative Memory (Springer-Verlag, Berlin, 1984).

Kung, S. Y.

J. W. Goodman, F. I. Leonberger, S. Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc. IEEE 72, 850–866 (1984).
[CrossRef]

Lee, S. H.

Leonberger, F. I.

J. W. Goodman, F. I. Leonberger, S. Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc. IEEE 72, 850–866 (1984).
[CrossRef]

Mead, C.

C. Mead, L. Conway, Introduction to VLSI Systems (Addison-Wesley, Menlo Park, CA, 1980), pp. 271–276.

Sawchuk, A. A.

Seitz, C.

C. Seitz, “Concurrent VLSI Architectures,” IEEE Trans. Comput. C-33, 1247–1265 (1984).
[CrossRef]

Strand, T. C.

Ullman, J. D.

J. D. Ullman, Computational Aspects of VLSI (Computer Science Press, Rockville, MD, 1984), Chap. 2.

Appl. Opt. (4)

IEEE Trans. Comput. (1)

C. Seitz, “Concurrent VLSI Architectures,” IEEE Trans. Comput. C-33, 1247–1265 (1984).
[CrossRef]

J. Opt. Soc. Am. A (1)

Proc. IEEE (1)

J. W. Goodman, F. I. Leonberger, S. Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc. IEEE 72, 850–866 (1984).
[CrossRef]

Proc. Natl. Acad. Sci. USA (1)

J. J. Hopfield, “Neural Networks and Physical Systems with Emergent Collective Computational Abilities,” Proc. Natl. Acad. Sci. USA 79, 2554–2558 (1982).
[CrossRef] [PubMed]

Other (6)

A. K. Jain, Fundamentals of Digital Image Processing (Prentice-Hall, Englewood Cliffs, NJ, 1989).

T. Kohonen, Self-Organization and Associative Memory (Springer-Verlag, Berlin, 1984).

J. D. Ullman, Computational Aspects of VLSI (Computer Science Press, Rockville, MD, 1984), Chap. 2.

W. J. Dally, A VLSI Architecture for Concurrent Data Structures (Kluwer Academic Publishers, Norwell, MA, 1987).
[CrossRef]

T. J. Drabik, M. R. Feldman, “Holographic Optical Time-Multiplexed Interconnection of Hypercubes,” submitted to IEEE Trans. Comput.

C. Mead, L. Conway, Introduction to VLSI Systems (Addison-Wesley, Menlo Park, CA, 1980), pp. 271–276.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (3)

Fig. 1
Fig. 1

Nested crossbar topology. The heavy solid lines indicate dimension 1 connections, light solid lines indicate dimension 2 connections, and dashed lines indicate dimension 3 connections. Not all connections are shown for base 4, 2-D and 3-D nested crossbars.

Fig. 2
Fig. 2

Layout of one node of a 2-D shared link nested crossbar in a VLSI grid model. The area of the node is O(N3/4), neglecting the area occupied by the matrix elements. Each box labeled Wijkxy is a shift register containing N1/4 matrix elements.

Fig. 3
Fig. 3

Layout of multiplanar optoelectronic processor arrays with all optoelectronic communication ports confined to a single plane.

Tables (3)

Tables Icon

Table I Lower Bounds on Computation Time for Vector–Matrix Multiplication

Tables Icon

Table II Summary of Performance of Nested Crossbar Connection Networks for Matrix–Vector Multiplication

Tables Icon

Table III Volume and Time Growth Rates for Performing Matrix–Vector Multiplication with Nested Crossbar Connection Networks for PEs in Multiple Planes

Equations (20)

Equations on this page are rendered with MathJax. Learn more.

b j = i = 1 N a i W i j .
A T = Ω ( N 2 ) ,
T q / M D + N / ( M T q ) .
q opt = ( N M D / M T ) 1 / 2 ,
T 2 { N / ( M D M T } 1 / 2 .
b = N 1 / m .
b x y = i = 0 N - 1 j = 0 N - 1 a i j W i j x y .
P x j y = i = 0 N - 1 a x i W x i j y .
k = 0 N - 1 P k x y = i = 0 N - 1 j = 0 N - 1 a i j W i j x y = b x y .
Q x k y for k = FLOOR ( x / N 1 / 4 ) N 1 / 4 + t ,
Q n k l = i = n N 1 / 4 n N 1 / 4 + N 1 / 4 - 1 j = 0 N - 1 a i j W i j k l ,
Q l k y , l = 0 , 1 , , N - 1 , k = FLOOR ( l / N 1 / 4 ) N 1 / 4 + t ,
n = ( FLOOR x / N 1 / 4 ) N 1 / 4 , ( FLOOR x / N 1 / 4 ) N 1 / 4 + 1 , , ( FLOOR x / N 1 / 4 ) N 1 / 4 + N 1 / 4 - 1.
n = N 1 / 4 ROUND ( x / N 1 / 4 ) N 1 / 4 ROUND ( x / N 1 / 4 ) + N 1 / 4 - 1 Q n x y = n = N 1 / 4 ROUND ( x / N ) 1 / 4 N 1 / 4 ROUND ( x / N 1 / 4 ) + N 1 / 4 - 1 i = n N 1 / 4 n N 1 / 4 + N 1 / 4 - 1 j = 0 N - 1 a i j W i j k l = i = 0 N - 1 j = 0 N - 1 a i j W i j x y .
V T = Ω ( N 2 ) .
L 1 L 2 T = Ω ( N 3 / 2 )
l T = Ω ( L 1 L 2 ) ,
L 3 l / tan Φ .
L 3 ( L 1 L 2 ) 1 / 2 / T .
V T 5 / 2 = Ω ( N 9 / 4 ) .

Metrics