Abstract

The Lee algorithm is a well-known technique for finding interconnection routes in applications such as on printed circuit boards. It is a problem highly suited to the use of the parallelism of optics. An optical solution to routing that is based on multirule symbolic substitution is described. As well as single-destination routing on a single layer, the adaptation of the technique for dealing with multiple destinations and multilayer boards is described. Finally, the performance gain of an optical over an electronic implementation of the algorithm is estimated.

© 1998 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Huang, “Parallel algorithms for optical digital computers,” in Tenth International Optical Computing Conference, S. Horvitz, ed., Proc. SPIE 422, 13–17 (1983).
    [CrossRef]
  2. A. L. Lentine and D. A. B. Miller, “Evolution of the SEED technology—bistable logic gates to optoelectronic smart pixels,” IEEE J. Quantum Electron. 29, 655–669 (1993).
    [CrossRef]
  3. M. J. Murdocca, “Digital optical computing with one-rule cellular automata,” Appl. Opt. 26, 682–688 (1987).
    [CrossRef] [PubMed]
  4. K. H. Brenner, A. Huang, and N. Streibl, “Digital optical computing with symbolic substitution,” Appl. Opt. 25, 3054–3060 (1986).
    [CrossRef] [PubMed]
  5. S. D. Goodman and W. T. Rhodes, “Symbolic substitution applications to image processing,” Appl. Opt. 27, 1708–1714 (1987).
    [CrossRef]
  6. R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
    [CrossRef]
  7. K. S. Huang, C. B. Kuznia, B. K. Jenkins, and A. A. Sawchuk, “Parallel architectures for digital optical cellular image processing,” IEEE Proc. 82, 1711–1723 (1994).
    [CrossRef]
  8. C. Y. Lee, “An algorithm for path connections and its applications,” I. R. E. Trans. Electron. Comput. EC10, 346–365 (1961).
    [CrossRef]
  9. M. Fukui and K. Kitayama, “Applications of image-logic algebra—wire routing and numerical data processing,” Appl. Opt. 31, 4645–4656 (1992).
    [CrossRef] [PubMed]
  10. M. P. Y. Desmulliez, B. R. Gillies, J. F. Snowdon, and B. S. Wherrett, “Simulation and benchmarking of a new algorithm for the optical cellular logic image processor,” Inst. Phys. Conf. Ser. 139, 21–24 (1995).
  11. P. Endecott, “An investigation of symbolic substitution,” Third Year Undergraduate Project Rep. (Department of Computer Science, Manchester University, Manchester, UK, 1991).
  12. T. D. Spiers and D. A. Edwards, “A high-performance routing engine,” in Proceedings of the Twenty-fourth ACM/IEEE Design Automation Conference (Institute of Electrical and Electronics Engineers, New York, 1987), pp. 793–799.

1995 (1)

M. P. Y. Desmulliez, B. R. Gillies, J. F. Snowdon, and B. S. Wherrett, “Simulation and benchmarking of a new algorithm for the optical cellular logic image processor,” Inst. Phys. Conf. Ser. 139, 21–24 (1995).

1994 (1)

K. S. Huang, C. B. Kuznia, B. K. Jenkins, and A. A. Sawchuk, “Parallel architectures for digital optical cellular image processing,” IEEE Proc. 82, 1711–1723 (1994).
[CrossRef]

1993 (1)

A. L. Lentine and D. A. B. Miller, “Evolution of the SEED technology—bistable logic gates to optoelectronic smart pixels,” IEEE J. Quantum Electron. 29, 655–669 (1993).
[CrossRef]

1992 (1)

1987 (2)

1986 (1)

1961 (1)

C. Y. Lee, “An algorithm for path connections and its applications,” I. R. E. Trans. Electron. Comput. EC10, 346–365 (1961).
[CrossRef]

Brenner, K. H.

Buller, G. S.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Craig, R. G. A.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Desmulliez, M. P. Y.

M. P. Y. Desmulliez, B. R. Gillies, J. F. Snowdon, and B. S. Wherrett, “Simulation and benchmarking of a new algorithm for the optical cellular logic image processor,” Inst. Phys. Conf. Ser. 139, 21–24 (1995).

Edwards, D. A.

T. D. Spiers and D. A. Edwards, “A high-performance routing engine,” in Proceedings of the Twenty-fourth ACM/IEEE Design Automation Conference (Institute of Electrical and Electronics Engineers, New York, 1987), pp. 793–799.

Fukui, M.

Gillies, B. R.

M. P. Y. Desmulliez, B. R. Gillies, J. F. Snowdon, and B. S. Wherrett, “Simulation and benchmarking of a new algorithm for the optical cellular logic image processor,” Inst. Phys. Conf. Ser. 139, 21–24 (1995).

Goodman, S. D.

Huang, A.

K. H. Brenner, A. Huang, and N. Streibl, “Digital optical computing with symbolic substitution,” Appl. Opt. 25, 3054–3060 (1986).
[CrossRef] [PubMed]

A. Huang, “Parallel algorithms for optical digital computers,” in Tenth International Optical Computing Conference, S. Horvitz, ed., Proc. SPIE 422, 13–17 (1983).
[CrossRef]

Huang, K. S.

K. S. Huang, C. B. Kuznia, B. K. Jenkins, and A. A. Sawchuk, “Parallel architectures for digital optical cellular image processing,” IEEE Proc. 82, 1711–1723 (1994).
[CrossRef]

Jenkins, B. K.

K. S. Huang, C. B. Kuznia, B. K. Jenkins, and A. A. Sawchuk, “Parallel architectures for digital optical cellular image processing,” IEEE Proc. 82, 1711–1723 (1994).
[CrossRef]

Kitayama, K.

Kuznia, C. B.

K. S. Huang, C. B. Kuznia, B. K. Jenkins, and A. A. Sawchuk, “Parallel architectures for digital optical cellular image processing,” IEEE Proc. 82, 1711–1723 (1994).
[CrossRef]

Lee, C. Y.

C. Y. Lee, “An algorithm for path connections and its applications,” I. R. E. Trans. Electron. Comput. EC10, 346–365 (1961).
[CrossRef]

Lentine, A. L.

A. L. Lentine and D. A. B. Miller, “Evolution of the SEED technology—bistable logic gates to optoelectronic smart pixels,” IEEE J. Quantum Electron. 29, 655–669 (1993).
[CrossRef]

MacKinnon, G.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

McArdle, N.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

McKnight, D. J.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Meredith, P.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Miller, D. A. B.

A. L. Lentine and D. A. B. Miller, “Evolution of the SEED technology—bistable logic gates to optoelectronic smart pixels,” IEEE J. Quantum Electron. 29, 655–669 (1993).
[CrossRef]

Miller, J. M.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Murdocca, M. J.

Redmond, I. R.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Restall, E. J.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Rhodes, W. T.

Sawchuk, A. A.

K. S. Huang, C. B. Kuznia, B. K. Jenkins, and A. A. Sawchuk, “Parallel architectures for digital optical cellular image processing,” IEEE Proc. 82, 1711–1723 (1994).
[CrossRef]

Smith, S. D.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Snowdon, J. F.

M. P. Y. Desmulliez, B. R. Gillies, J. F. Snowdon, and B. S. Wherrett, “Simulation and benchmarking of a new algorithm for the optical cellular logic image processor,” Inst. Phys. Conf. Ser. 139, 21–24 (1995).

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Spiers, T. D.

T. D. Spiers and D. A. Edwards, “A high-performance routing engine,” in Proceedings of the Twenty-fourth ACM/IEEE Design Automation Conference (Institute of Electrical and Electronics Engineers, New York, 1987), pp. 793–799.

Streibl, N.

Tagizadeh, M. R.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Wakelin, S.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Walker, A. C.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Wherrett, B. S.

M. P. Y. Desmulliez, B. R. Gillies, J. F. Snowdon, and B. S. Wherrett, “Simulation and benchmarking of a new algorithm for the optical cellular logic image processor,” Inst. Phys. Conf. Ser. 139, 21–24 (1995).

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Wilson, R. A.

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

Appl. Opt. (4)

I. R. E. Trans. Electron. Comput. (1)

C. Y. Lee, “An algorithm for path connections and its applications,” I. R. E. Trans. Electron. Comput. EC10, 346–365 (1961).
[CrossRef]

IEEE J. Quantum Electron. (1)

A. L. Lentine and D. A. B. Miller, “Evolution of the SEED technology—bistable logic gates to optoelectronic smart pixels,” IEEE J. Quantum Electron. 29, 655–669 (1993).
[CrossRef]

IEEE Proc. (1)

K. S. Huang, C. B. Kuznia, B. K. Jenkins, and A. A. Sawchuk, “Parallel architectures for digital optical cellular image processing,” IEEE Proc. 82, 1711–1723 (1994).
[CrossRef]

Inst. Phys. Conf. Ser. (1)

M. P. Y. Desmulliez, B. R. Gillies, J. F. Snowdon, and B. S. Wherrett, “Simulation and benchmarking of a new algorithm for the optical cellular logic image processor,” Inst. Phys. Conf. Ser. 139, 21–24 (1995).

Other (4)

P. Endecott, “An investigation of symbolic substitution,” Third Year Undergraduate Project Rep. (Department of Computer Science, Manchester University, Manchester, UK, 1991).

T. D. Spiers and D. A. Edwards, “A high-performance routing engine,” in Proceedings of the Twenty-fourth ACM/IEEE Design Automation Conference (Institute of Electrical and Electronics Engineers, New York, 1987), pp. 793–799.

A. Huang, “Parallel algorithms for optical digital computers,” in Tenth International Optical Computing Conference, S. Horvitz, ed., Proc. SPIE 422, 13–17 (1983).
[CrossRef]

R. G. A. Craig, B. S. Wherrett, A. C. Walker, D. J. McKnight, I. R. Redmond, J. F. Snowdon, G. S. Buller, E. J. Restall, R. A. Wilson, S. Wakelin, N. McArdle, P. Meredith, J. M. Miller, M. R. Tagizadeh, G. MacKinnon, and S. D. Smith, “First programmable digital optical processor: optical cellular logic image processor,” in Optics for Computers: Architectures and Technologies, G. J. Lebreton, ed., Proc. SPIE 1505, 76–86 (1991).
[CrossRef]

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

Fig. 1
Fig. 1

Expansion phase.

Fig. 2
Fig. 2

Retrace phase.

Fig. 3
Fig. 3

Symbols for the expansion phase.

Fig. 4
Fig. 4

Rules for the expansion phase: (a) Rules for expanding the generator symbols. (b) Rules for preserving the explored space. (c) Rules for preserving the unexplored space.

Fig. 5
Fig. 5

Expansion process.

Fig. 6
Fig. 6

Expansion evaluation: (a) Points to be connected. (b) start point. (c) Process after four stages. (d) Application of expansion rule set 1. (e) Application of the copy rules. (f) Combination. (g) Mask output. (h) Edge–no-go pattern. (i) Process after five stages. (j) Process after nine stages. The emphasized, i.e., those in boldface type, cells denote state changes.

Fig. 7
Fig. 7

End-point detection.

Fig. 8
Fig. 8

Final expansion pattern.

Fig. 9
Fig. 9

Symbols for the retrace phase.

Fig. 10
Fig. 10

Retrace rules: (a) For expanding the track head. (b) For preserving and expanding the symbol T space. (c) For copying generation symbols.

Fig. 11
Fig. 11

Retrace operation: (a) start point. (b) Process after four stages. (c) Process after nine stages. (d) Final retrace pattern.

Fig. 12
Fig. 12

Retrace-with-erosion rule set for the symbol C.

Fig. 13
Fig. 13

Retrace with erosion: (a) start point. (b) Process after four stages. (c) Process after nine stages. (d) Final retrace pattern.

Fig. 14
Fig. 14

Recognition by use of symbols: (a) Recognition phase. (b) Symbol recognition. (c) Symbol-set recognition.

Fig. 15
Fig. 15

Detection of the absence of symbols.

Fig. 16
Fig. 16

Connection of the source to the destination points: (a) Source and target points. (b) Star connection. (c) Bus route 1. (d) Bus route 2. (e) Bus route 3. (f) Bus route 4. (g) Bus route 5. (h) Bus route 6.

Fig. 17
Fig. 17

Bus route 1 by use of a north–west–south–east precedence.

Fig. 18
Fig. 18

Multiple-destination routing by use of a north–south–east–west precedence.

Fig. 19
Fig. 19

Multilayer-board representation.

Fig. 20
Fig. 20

Multilayer tracking: (a) Additional expansion rules for generator symbols. (b) Rules for preserving the unexplored space.

Fig. 21
Fig. 21

Expansion in a multilayer environment: (a) start point. (b) Expansion 1: Symbols A → B. (c) Expansion 2: Symbols B → C. (d) Expansion 3: Symbols C → A. (e) Expansion 4: Symbols A → B. (f) Expansion 5: Symbols B → C. (g) Expansion 6: Symbols C → A. (h) Expansion 7: Symbols A → B; the finish point is reached.

Fig. 22
Fig. 22

Retrace-with-erosion rule set for the symbol C in multilayer tracking.

Fig. 23
Fig. 23

Routed track.

Fig. 24
Fig. 24

Track-conversion rules for establishing (a) no-go cells and (b) symbols H and V cells.

Fig. 25
Fig. 25

Track conversion.

Fig. 26
Fig. 26

Board merging.

Fig. 27
Fig. 27

Symbols H, V, and H+V cells.

Fig. 28
Fig. 28

Transformation of the merged board.

Metrics