Abstract

Regular free-space interconnects such as the perfect shuffle and banyan provided by beam splitters, lenses, and mirrors connect optical logic gates arranged in 2-D arrays. An algorithmic design technique transforms arbitrary logic equations into a near-optimal depth circuit. Analysis shows that an arbitrary interconnect makes little or no improvement in circuit depth and can even reduce throughput. Gate count is normally higher with a regular interconnect, and we show cost bounds. We conclude that regularly interconnected circuits will have a higher gate count compared with arbitrarily interconnected circuits using the design techniques presented here and that regular free-space interconnects are comparable with arbitrary interconnects in terms of circuit depth and are preferred to arbitrary interconnects for maximizing throughput.

© 1988 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. J. von Neumann, “Nonlinear Capacitance or Inductance Switching, Amplifying and Memory Devices,” in John von Neumann’s Collected Works, Vol. 5 (Macmillan, New York, 1963).
  2. H. M. Gibbs, Optical Bistability, Controlling Light with Light, (Academic, New York, 1985).
  3. A recent collection of papers is Technical Digest, Topical Meeting on Optical Bistability (OB3) (Optical Society of America, Washington, DC, 1985).
  4. J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ 82-MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple Quantum Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).
    [CrossRef]
  5. L. C. West, “Spectroscopy of GaAs Quantum Wells,” Ph.D. Thesis, Stanford U. (1985).
    [CrossRef]
  6. D. A. B. Miller, D. S. Chemla, T. C. Damen, T. H. Wood, C. A. Burrus, A. C. Gossard, W. Wiegmann, “The Quantum Well Self-Electrooptic Effect Device: Optoelectronic Bistability and Oscillation and Self-Linearized Modulation,” IEEE J. Quantum Electron. QE-21, 1462 (1985).
    [CrossRef]
  7. A. Huang, “Parallel Algorithms for Optical Digital Computers,” at IEEE 1983 Tenth International Optical Computing Conference, (1983), p. 13.
    [CrossRef]
  8. M. J. Murdocca, “Techniques for Parallel Numeric and Non-Numeric Algorithm Design in Digital Optics,” Master's Thesis, Rutgers U. (1985).
  9. K.-H. Brenner, A. Huang, N. Streibl, “Digital Optical Computing with Symbolic Substitution,” Appl. Opt. 25, 3054 (1986).
    [CrossRef] [PubMed]
  10. M. J. Murdocca, “Digital Optical Computing with One-Rule Cellular Automata,” Appl. Opt. 26, 3365 (1987).
    [CrossRef]
  11. M. J. Murdocca, N. Streibl, “A Digital Design Technique for Optical Computing,” in Technical Digest, Topical Meeting on Optical Computing, Tech. Digest Ser. 1987, Vol. 11 (Optical Society of America, Washington, DC, 1987) pp. 9–11.
  12. K.-H. Brenner, A. Huang, “Optical Implementations of the Perfect Shuffle Interconnections,” Appl. Opt. 27, 135 (1988).
    [CrossRef] [PubMed]
  13. A. W. Lohmann, “Optical Perfect Shuffle,” Appl. Opt. 25, 1530 (1986).
    [CrossRef] [PubMed]
  14. H. S. Stone, “Parallel Processing with the Perfect Shuffle,” IEEE Trans. Comput. C-20, 153 (1971).
    [CrossRef]
  15. D. H. Lawrie, “Access and Alignment of Data in an Array Processor,” IEEE Trans. Comput. C-24, 1145 (1975).
    [CrossRef]
  16. C.-L. Wu, T.-Y. Feng, “The Universality of the Shuffle-Exchange Network,” IEEE Trans. Comput. C-30, 324 (1981).
    [CrossRef]
  17. D. Knuth, The Art of Computer Programming (Addison-Wesley, Reading, MA, 1973), Vol. 3, p. 237.
  18. J. W. Cooley, J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” Math. Comput. 19, 297 (1965).
    [CrossRef]
  19. M. Minsky, Computation: Finite and Infinite Machines (Prentice Hall, Englewood Cliffs, NJ, 1967), p. 117.
  20. See, for example, Z. Kohavi, Switching and Finite Automata Theory (McGraw-Hill, New York, 1978).

1988 (1)

1987 (1)

M. J. Murdocca, “Digital Optical Computing with One-Rule Cellular Automata,” Appl. Opt. 26, 3365 (1987).
[CrossRef]

1986 (2)

1985 (2)

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ 82-MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple Quantum Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).
[CrossRef]

D. A. B. Miller, D. S. Chemla, T. C. Damen, T. H. Wood, C. A. Burrus, A. C. Gossard, W. Wiegmann, “The Quantum Well Self-Electrooptic Effect Device: Optoelectronic Bistability and Oscillation and Self-Linearized Modulation,” IEEE J. Quantum Electron. QE-21, 1462 (1985).
[CrossRef]

1981 (1)

C.-L. Wu, T.-Y. Feng, “The Universality of the Shuffle-Exchange Network,” IEEE Trans. Comput. C-30, 324 (1981).
[CrossRef]

1975 (1)

D. H. Lawrie, “Access and Alignment of Data in an Array Processor,” IEEE Trans. Comput. C-24, 1145 (1975).
[CrossRef]

1971 (1)

H. S. Stone, “Parallel Processing with the Perfect Shuffle,” IEEE Trans. Comput. C-20, 153 (1971).
[CrossRef]

1965 (1)

J. W. Cooley, J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” Math. Comput. 19, 297 (1965).
[CrossRef]

Brenner, K.-H.

Burrus, C. A.

D. A. B. Miller, D. S. Chemla, T. C. Damen, T. H. Wood, C. A. Burrus, A. C. Gossard, W. Wiegmann, “The Quantum Well Self-Electrooptic Effect Device: Optoelectronic Bistability and Oscillation and Self-Linearized Modulation,” IEEE J. Quantum Electron. QE-21, 1462 (1985).
[CrossRef]

Chemla, D. S.

D. A. B. Miller, D. S. Chemla, T. C. Damen, T. H. Wood, C. A. Burrus, A. C. Gossard, W. Wiegmann, “The Quantum Well Self-Electrooptic Effect Device: Optoelectronic Bistability and Oscillation and Self-Linearized Modulation,” IEEE J. Quantum Electron. QE-21, 1462 (1985).
[CrossRef]

Cooley, J. W.

J. W. Cooley, J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” Math. Comput. 19, 297 (1965).
[CrossRef]

Damen, T. C.

D. A. B. Miller, D. S. Chemla, T. C. Damen, T. H. Wood, C. A. Burrus, A. C. Gossard, W. Wiegmann, “The Quantum Well Self-Electrooptic Effect Device: Optoelectronic Bistability and Oscillation and Self-Linearized Modulation,” IEEE J. Quantum Electron. QE-21, 1462 (1985).
[CrossRef]

Feng, T.-Y.

C.-L. Wu, T.-Y. Feng, “The Universality of the Shuffle-Exchange Network,” IEEE Trans. Comput. C-30, 324 (1981).
[CrossRef]

Gibbs, H. M.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ 82-MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple Quantum Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).
[CrossRef]

H. M. Gibbs, Optical Bistability, Controlling Light with Light, (Academic, New York, 1985).

Gossard, A. C.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ 82-MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple Quantum Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).
[CrossRef]

D. A. B. Miller, D. S. Chemla, T. C. Damen, T. H. Wood, C. A. Burrus, A. C. Gossard, W. Wiegmann, “The Quantum Well Self-Electrooptic Effect Device: Optoelectronic Bistability and Oscillation and Self-Linearized Modulation,” IEEE J. Quantum Electron. QE-21, 1462 (1985).
[CrossRef]

Huang, A.

Jewell, J. L.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ 82-MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple Quantum Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).
[CrossRef]

Knuth, D.

D. Knuth, The Art of Computer Programming (Addison-Wesley, Reading, MA, 1973), Vol. 3, p. 237.

Kohavi, Z.

See, for example, Z. Kohavi, Switching and Finite Automata Theory (McGraw-Hill, New York, 1978).

Lawrie, D. H.

D. H. Lawrie, “Access and Alignment of Data in an Array Processor,” IEEE Trans. Comput. C-24, 1145 (1975).
[CrossRef]

Lee, Y. H.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ 82-MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple Quantum Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).
[CrossRef]

Lohmann, A. W.

Miller, D. A. B.

D. A. B. Miller, D. S. Chemla, T. C. Damen, T. H. Wood, C. A. Burrus, A. C. Gossard, W. Wiegmann, “The Quantum Well Self-Electrooptic Effect Device: Optoelectronic Bistability and Oscillation and Self-Linearized Modulation,” IEEE J. Quantum Electron. QE-21, 1462 (1985).
[CrossRef]

Minsky, M.

M. Minsky, Computation: Finite and Infinite Machines (Prentice Hall, Englewood Cliffs, NJ, 1967), p. 117.

Murdocca, M. J.

M. J. Murdocca, “Digital Optical Computing with One-Rule Cellular Automata,” Appl. Opt. 26, 3365 (1987).
[CrossRef]

M. J. Murdocca, N. Streibl, “A Digital Design Technique for Optical Computing,” in Technical Digest, Topical Meeting on Optical Computing, Tech. Digest Ser. 1987, Vol. 11 (Optical Society of America, Washington, DC, 1987) pp. 9–11.

M. J. Murdocca, “Techniques for Parallel Numeric and Non-Numeric Algorithm Design in Digital Optics,” Master's Thesis, Rutgers U. (1985).

Peyghambarian, N.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ 82-MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple Quantum Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).
[CrossRef]

Stone, H. S.

H. S. Stone, “Parallel Processing with the Perfect Shuffle,” IEEE Trans. Comput. C-20, 153 (1971).
[CrossRef]

Streibl, N.

K.-H. Brenner, A. Huang, N. Streibl, “Digital Optical Computing with Symbolic Substitution,” Appl. Opt. 25, 3054 (1986).
[CrossRef] [PubMed]

M. J. Murdocca, N. Streibl, “A Digital Design Technique for Optical Computing,” in Technical Digest, Topical Meeting on Optical Computing, Tech. Digest Ser. 1987, Vol. 11 (Optical Society of America, Washington, DC, 1987) pp. 9–11.

Tukey, J. W.

J. W. Cooley, J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” Math. Comput. 19, 297 (1965).
[CrossRef]

von Neumann, J.

J. von Neumann, “Nonlinear Capacitance or Inductance Switching, Amplifying and Memory Devices,” in John von Neumann’s Collected Works, Vol. 5 (Macmillan, New York, 1963).

Warren, M.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ 82-MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple Quantum Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).
[CrossRef]

West, L. C.

L. C. West, “Spectroscopy of GaAs Quantum Wells,” Ph.D. Thesis, Stanford U. (1985).
[CrossRef]

Wiegmann, W.

D. A. B. Miller, D. S. Chemla, T. C. Damen, T. H. Wood, C. A. Burrus, A. C. Gossard, W. Wiegmann, “The Quantum Well Self-Electrooptic Effect Device: Optoelectronic Bistability and Oscillation and Self-Linearized Modulation,” IEEE J. Quantum Electron. QE-21, 1462 (1985).
[CrossRef]

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ 82-MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple Quantum Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).
[CrossRef]

Wood, T. H.

D. A. B. Miller, D. S. Chemla, T. C. Damen, T. H. Wood, C. A. Burrus, A. C. Gossard, W. Wiegmann, “The Quantum Well Self-Electrooptic Effect Device: Optoelectronic Bistability and Oscillation and Self-Linearized Modulation,” IEEE J. Quantum Electron. QE-21, 1462 (1985).
[CrossRef]

Wu, C.-L.

C.-L. Wu, T.-Y. Feng, “The Universality of the Shuffle-Exchange Network,” IEEE Trans. Comput. C-30, 324 (1981).
[CrossRef]

Appl. Opt. (4)

Appl. Phys. Lett. (1)

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ 82-MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple Quantum Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).
[CrossRef]

IEEE J. Quantum Electron. (1)

D. A. B. Miller, D. S. Chemla, T. C. Damen, T. H. Wood, C. A. Burrus, A. C. Gossard, W. Wiegmann, “The Quantum Well Self-Electrooptic Effect Device: Optoelectronic Bistability and Oscillation and Self-Linearized Modulation,” IEEE J. Quantum Electron. QE-21, 1462 (1985).
[CrossRef]

IEEE Trans. Comput. (3)

H. S. Stone, “Parallel Processing with the Perfect Shuffle,” IEEE Trans. Comput. C-20, 153 (1971).
[CrossRef]

D. H. Lawrie, “Access and Alignment of Data in an Array Processor,” IEEE Trans. Comput. C-24, 1145 (1975).
[CrossRef]

C.-L. Wu, T.-Y. Feng, “The Universality of the Shuffle-Exchange Network,” IEEE Trans. Comput. C-30, 324 (1981).
[CrossRef]

Math. Comput. (1)

J. W. Cooley, J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” Math. Comput. 19, 297 (1965).
[CrossRef]

Other (10)

M. Minsky, Computation: Finite and Infinite Machines (Prentice Hall, Englewood Cliffs, NJ, 1967), p. 117.

See, for example, Z. Kohavi, Switching and Finite Automata Theory (McGraw-Hill, New York, 1978).

D. Knuth, The Art of Computer Programming (Addison-Wesley, Reading, MA, 1973), Vol. 3, p. 237.

A. Huang, “Parallel Algorithms for Optical Digital Computers,” at IEEE 1983 Tenth International Optical Computing Conference, (1983), p. 13.
[CrossRef]

M. J. Murdocca, “Techniques for Parallel Numeric and Non-Numeric Algorithm Design in Digital Optics,” Master's Thesis, Rutgers U. (1985).

M. J. Murdocca, N. Streibl, “A Digital Design Technique for Optical Computing,” in Technical Digest, Topical Meeting on Optical Computing, Tech. Digest Ser. 1987, Vol. 11 (Optical Society of America, Washington, DC, 1987) pp. 9–11.

L. C. West, “Spectroscopy of GaAs Quantum Wells,” Ph.D. Thesis, Stanford U. (1985).
[CrossRef]

J. von Neumann, “Nonlinear Capacitance or Inductance Switching, Amplifying and Memory Devices,” in John von Neumann’s Collected Works, Vol. 5 (Macmillan, New York, 1963).

H. M. Gibbs, Optical Bistability, Controlling Light with Light, (Academic, New York, 1985).

A recent collection of papers is Technical Digest, Topical Meeting on Optical Bistability (OB3) (Optical Society of America, Washington, DC, 1985).

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 (23)

Fig. 1
Fig. 1

Schematic of a digital optical computer. The input array is split into two identical images which are each perfect shuffled (marked as P-S) and recombined onto an optically nonlinear array of AND gates. The AND array is imaged onto a similar setup with an OR array. Feedback is at two places as shown, and masks customize the interconnects so that only selected sites will be enabled.

Fig. 2
Fig. 2

Sixteen-bit 1-D perfect shuffles. The rightmost shuffle is obtained from the leftmost shuffle by swapping elements within pairs.

Fig. 3
Fig. 3

Exchange (a) and bypass (b) operations for a shuffle-exchange network.

Fig. 4
Fig. 4

Optical implementation of the perfect shuffle.

Fig. 5
Fig. 5

Sixteen-bit 1-D butterfly.

Fig. 6
Fig. 6

Isomorphism of banyan network and perfect shuffle network for N = 16.

Fig. 7
Fig. 7

Serial adder. Two numbers enter the adder least significant bit first. Two bits are added on each time step, and one more bit of the result is produced. The carry is stored within the adder as its internal state.

Fig. 8
Fig. 8

State transition diagram (a) and state transition table (b) for a serial adder.

Fig. 9
Fig. 9

State assignment (a) and state transition table with assignments (b) for a serial adder.

Fig. 10
Fig. 10

Network for generating minterms of one variable. Flow of information is from the top to the bottom. Unused connections are marked with dashed lines and are masked out via masks as shown in Fig. 1.

Fig. 11
Fig. 11

Network for generating minterms of two variables.

Fig. 12
Fig. 12

Generation of all three-variable unminimized minterms with butterfly interconnects and two-input two-output AND gates (shown as boxes with an inscribed square). Inputs are provided at level A and two outputs for each minterm are produced at level I.

Fig. 13
Fig. 13

Mapping minterms to state and output functions for a serial adder. Boxes with inscribed crosses are two-input two-output OR gates.

Fig. 14
Fig. 14

Serial adder implemented with butterfly interconnects in an ANDOR network.

Fig. 15
Fig. 15

Serial adder implemented with perfact shuffle interconnects in an AND–OR network.

Fig. 16
Fig. 16

Mask M0 for a serial adder. Light squares are transparent, dark squares are opaque.

Fig. 17
Fig. 17

Mask M1 for a serial adder.

Fig. 18
Fig. 18

Mask M2 for a serial adder.

Fig. 19
Fig. 19

Mask M3 for a serial adder.

Fig. 20
Fig. 20

Transforming a two-level ANDOR circuit with unlimited fan-in and fan-out into a 2 log2N level circuit with fan-in and fan-out of 2.

Fig. 21
Fig. 21

Simple architecture using only NOR gates.

Fig. 22
Fig. 22

Trial-and-error optimization results in a simpler circuit for f than when all minterms are generated.

Fig. 23
Fig. 23

Arbitrary interconnect for minimized serial adder.

Equations (10)

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

s t + 1 = x ¯ y s t + x y ¯ s t + x y s ¯ t + x y s t .
s ¯ t + 1 = x ¯ y ¯ s ¯ t + x ¯ y ¯ s t + x ¯ y s ¯ t + x y ¯ s ¯ t .
z t + 1 = x ¯ y ¯ s t + x ¯ y s ¯ t + x y ¯ s ¯ t + x y s t ;
z ¯ t + 1 = x ¯ y ¯ s ¯ t + x ¯ y s t + x y ¯ s t + x y s ¯ t .
s t + 1 = x y + y s t + x s t ,
s t + 1 = x ¯ y ¯ + y ¯ s ¯ t + x ¯ s ¯ t ,
s t + 1 = x y + x s t + y s t = m 0 + m 1 + m 2 ;
s ¯ t + 1 = x ¯ y ¯ + x ¯ s ¯ t + y ¯ s ¯ t = m 3 + m 4 + m 5 ;
z t + 1 = x ¯ y ¯ s t + x ¯ y s ¯ t + x y s t + x y ¯ s ¯ t = m 6 + m 7 + m 8 + m 9 ;
z t + 1 = x ¯ y ¯ s ¯ t + x ¯ y s t + x y s ¯ t + x y ¯ s t = m 10 + m 11 + m 12 + m 13 .

Metrics