Abstract

We extend the concept of optical content-addressable parallel processing [Appl. Opt. 31, 3241 (1992)] to a novel architecture designed specifically for the parallel and high-speed implementation of database operations called optical content-addressable parallel processor for relational database processing (OCAPPRP). An OCAPPRP combines a parallel model of computation, associative processing, with parallel and high-speed technology optics. The architecture is developed to provide optimal support for high-speed parallel equivalence (pattern matching) and relative-magnitude searches (greater than and lesser than). Distinctive features of the proposed architecture include (1) a two-dimensional match–compare unit for two-dimensional pattern matching, (2) constant-time retrieval of database entries, (3) an optical word and bit-parallel relative-magnitude single-step algorithm, and (4) the capability of constant-time sorting. Since relational database operations rely heavily on parallel equivalence or relative-magnitude searches, database processing is an excellent candidate for implementation on an OCAPPRP. The architecture delivers a speedup factor of n over conventional optical database architectures, where n is the number of rows in a database table. We present an overview of the architecture followed by its optical implementation. The representative relational database operations, intersection, and selection are outlined to illustrate the architecture’s potential for efficiently supporting high-speed database processing.

© 1994 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. P. B. Berra, K.-H. Brenner, W. T. Cathey, H. J. Caulfield, S. H. Lee, H. Szu, “Optical database/knowledgebase machines,” Appl. Opt. 29, 195–205 (1990).
    [CrossRef] [PubMed]
  2. P. B. Berra, A. Ghafoor, M. Guizani, S. J. Marcinkowski, P. A. Mitkas, “Optics and supercomputing,” Proc. IEEE 77, 1797–1815 (1989).
    [CrossRef]
  3. T. Kohonen, Content-Addressable Memories (Springer-Verlag, New York, 1980).
    [CrossRef]
  4. A. Louri, “Optical content-addressable parallel processor: architecture, algorithms, and design concepts,” Appl. Opt. 31, 3241–3258 (1992).
    [CrossRef] [PubMed]
  5. S. Y. Su, Database Computers: Principles, Architectures, and Techniques (McGraw-Hill, New York, 1988).
  6. J. R. Ullman, “Fast implementation of relational operations via inverse projections,” Comput. J. 31, 147–154 (1988).
    [CrossRef]
  7. A. Louri, “Three-dimensional optical architecture and data-parallel algorithms for massively parallel computing,” IEEE Micro. 11, 24–68 (1991).
    [CrossRef]
  8. F. B. McCormick, Photonics in Switching (Academic, Boston, 1993), Vol. II, Chap. 4.
  9. J. A. Neff, R. A. Athale, S. H. Lee, “Two-dimensional spatial light modulators: a tutorial,” Proc. IEEE 78, 826–854 (1990).
    [CrossRef]
  10. A. Louri, J. A. Hatch, “Optical implementation of a single-iteration thresholding algorithm with applications to parallel data-base/knowledgebase processing,” Opt. Lett. 18, 992–994 (1993).
    [CrossRef] [PubMed]
  11. R. A. Athale, M. W. Haney, “Optical implementation of numerical inequality detection and its applications to database machines,” Opt. Lett. 17, 1611–1613 (1992).
    [CrossRef] [PubMed]
  12. C. J. Date, An Introduction to Database Systems (Addison-Wesley, Reading, Mass., 1986).
  13. S. Akyokus, P. B. Berra, “Optical content addressable memories for data/knowledge base processing,” presented at the Fifth International Symposium on Parallel Processing, Anaheim, Calif., 1991.
  14. A. W. Lohmann, “Polarization and optical logic,” Appl. Opt. 25, 1594–1597 (1986).
    [CrossRef] [PubMed]
  15. K. W. Wong, L. M Cheng, M. C. Poon, “Design of digital-optical processors by using both intensity and polarization-encoding schemes,” Appl. Opt. 31, 3225–3232 (1992).
    [CrossRef] [PubMed]
  16. K. M. Johnson, G. Moddel, “Motivations for using ferroelectric liquid crystal spatial light modulators in neurocomputing,” Appl. Opt. 28, 4888–4899 (1989).
    [CrossRef] [PubMed]
  17. C. Warde, A. Fisher, “Spatial light modulators: applications and functional capabilities,” in Optical Signal Processing, J. Horner, ed. (Academic, 1987), New York, pp. 478–524.
  18. G. Gheen, “Optical matrix–matrix multiplier,” Appl. Opt. 29, 886–887 (1990).
  19. H. J. Caulfield, “Massively parallel optical data base management,” in Digital and Optical Shape Representation and Pattern Recognition, R. D. Juday, ed., Proc. Soc. Photo-Opt. Instrum. Eng.938, 52–54 (1988).

1993 (1)

1992 (3)

1991 (1)

A. Louri, “Three-dimensional optical architecture and data-parallel algorithms for massively parallel computing,” IEEE Micro. 11, 24–68 (1991).
[CrossRef]

1990 (3)

J. A. Neff, R. A. Athale, S. H. Lee, “Two-dimensional spatial light modulators: a tutorial,” Proc. IEEE 78, 826–854 (1990).
[CrossRef]

G. Gheen, “Optical matrix–matrix multiplier,” Appl. Opt. 29, 886–887 (1990).

P. B. Berra, K.-H. Brenner, W. T. Cathey, H. J. Caulfield, S. H. Lee, H. Szu, “Optical database/knowledgebase machines,” Appl. Opt. 29, 195–205 (1990).
[CrossRef] [PubMed]

1989 (2)

P. B. Berra, A. Ghafoor, M. Guizani, S. J. Marcinkowski, P. A. Mitkas, “Optics and supercomputing,” Proc. IEEE 77, 1797–1815 (1989).
[CrossRef]

K. M. Johnson, G. Moddel, “Motivations for using ferroelectric liquid crystal spatial light modulators in neurocomputing,” Appl. Opt. 28, 4888–4899 (1989).
[CrossRef] [PubMed]

1988 (1)

J. R. Ullman, “Fast implementation of relational operations via inverse projections,” Comput. J. 31, 147–154 (1988).
[CrossRef]

1986 (1)

Akyokus, S.

S. Akyokus, P. B. Berra, “Optical content addressable memories for data/knowledge base processing,” presented at the Fifth International Symposium on Parallel Processing, Anaheim, Calif., 1991.

Athale, R. A.

R. A. Athale, M. W. Haney, “Optical implementation of numerical inequality detection and its applications to database machines,” Opt. Lett. 17, 1611–1613 (1992).
[CrossRef] [PubMed]

J. A. Neff, R. A. Athale, S. H. Lee, “Two-dimensional spatial light modulators: a tutorial,” Proc. IEEE 78, 826–854 (1990).
[CrossRef]

Berra, P. B.

P. B. Berra, K.-H. Brenner, W. T. Cathey, H. J. Caulfield, S. H. Lee, H. Szu, “Optical database/knowledgebase machines,” Appl. Opt. 29, 195–205 (1990).
[CrossRef] [PubMed]

P. B. Berra, A. Ghafoor, M. Guizani, S. J. Marcinkowski, P. A. Mitkas, “Optics and supercomputing,” Proc. IEEE 77, 1797–1815 (1989).
[CrossRef]

S. Akyokus, P. B. Berra, “Optical content addressable memories for data/knowledge base processing,” presented at the Fifth International Symposium on Parallel Processing, Anaheim, Calif., 1991.

Brenner, K.-H.

Cathey, W. T.

Caulfield, H. J.

P. B. Berra, K.-H. Brenner, W. T. Cathey, H. J. Caulfield, S. H. Lee, H. Szu, “Optical database/knowledgebase machines,” Appl. Opt. 29, 195–205 (1990).
[CrossRef] [PubMed]

H. J. Caulfield, “Massively parallel optical data base management,” in Digital and Optical Shape Representation and Pattern Recognition, R. D. Juday, ed., Proc. Soc. Photo-Opt. Instrum. Eng.938, 52–54 (1988).

Cheng, L. M

Date, C. J.

C. J. Date, An Introduction to Database Systems (Addison-Wesley, Reading, Mass., 1986).

Fisher, A.

C. Warde, A. Fisher, “Spatial light modulators: applications and functional capabilities,” in Optical Signal Processing, J. Horner, ed. (Academic, 1987), New York, pp. 478–524.

Ghafoor, A.

P. B. Berra, A. Ghafoor, M. Guizani, S. J. Marcinkowski, P. A. Mitkas, “Optics and supercomputing,” Proc. IEEE 77, 1797–1815 (1989).
[CrossRef]

Gheen, G.

G. Gheen, “Optical matrix–matrix multiplier,” Appl. Opt. 29, 886–887 (1990).

Guizani, M.

P. B. Berra, A. Ghafoor, M. Guizani, S. J. Marcinkowski, P. A. Mitkas, “Optics and supercomputing,” Proc. IEEE 77, 1797–1815 (1989).
[CrossRef]

Haney, M. W.

Hatch, J. A.

Johnson, K. M.

Kohonen, T.

T. Kohonen, Content-Addressable Memories (Springer-Verlag, New York, 1980).
[CrossRef]

Lee, S. H.

P. B. Berra, K.-H. Brenner, W. T. Cathey, H. J. Caulfield, S. H. Lee, H. Szu, “Optical database/knowledgebase machines,” Appl. Opt. 29, 195–205 (1990).
[CrossRef] [PubMed]

J. A. Neff, R. A. Athale, S. H. Lee, “Two-dimensional spatial light modulators: a tutorial,” Proc. IEEE 78, 826–854 (1990).
[CrossRef]

Lohmann, A. W.

Louri, A.

Marcinkowski, S. J.

P. B. Berra, A. Ghafoor, M. Guizani, S. J. Marcinkowski, P. A. Mitkas, “Optics and supercomputing,” Proc. IEEE 77, 1797–1815 (1989).
[CrossRef]

McCormick, F. B.

F. B. McCormick, Photonics in Switching (Academic, Boston, 1993), Vol. II, Chap. 4.

Mitkas, P. A.

P. B. Berra, A. Ghafoor, M. Guizani, S. J. Marcinkowski, P. A. Mitkas, “Optics and supercomputing,” Proc. IEEE 77, 1797–1815 (1989).
[CrossRef]

Moddel, G.

Neff, J. A.

J. A. Neff, R. A. Athale, S. H. Lee, “Two-dimensional spatial light modulators: a tutorial,” Proc. IEEE 78, 826–854 (1990).
[CrossRef]

Poon, M. C.

Su, S. Y.

S. Y. Su, Database Computers: Principles, Architectures, and Techniques (McGraw-Hill, New York, 1988).

Szu, H.

Ullman, J. R.

J. R. Ullman, “Fast implementation of relational operations via inverse projections,” Comput. J. 31, 147–154 (1988).
[CrossRef]

Warde, C.

C. Warde, A. Fisher, “Spatial light modulators: applications and functional capabilities,” in Optical Signal Processing, J. Horner, ed. (Academic, 1987), New York, pp. 478–524.

Wong, K. W.

Appl. Opt. (6)

Comput. J. (1)

J. R. Ullman, “Fast implementation of relational operations via inverse projections,” Comput. J. 31, 147–154 (1988).
[CrossRef]

IEEE Micro. (1)

A. Louri, “Three-dimensional optical architecture and data-parallel algorithms for massively parallel computing,” IEEE Micro. 11, 24–68 (1991).
[CrossRef]

Opt. Lett. (2)

Proc. IEEE (2)

J. A. Neff, R. A. Athale, S. H. Lee, “Two-dimensional spatial light modulators: a tutorial,” Proc. IEEE 78, 826–854 (1990).
[CrossRef]

P. B. Berra, A. Ghafoor, M. Guizani, S. J. Marcinkowski, P. A. Mitkas, “Optics and supercomputing,” Proc. IEEE 77, 1797–1815 (1989).
[CrossRef]

Other (7)

T. Kohonen, Content-Addressable Memories (Springer-Verlag, New York, 1980).
[CrossRef]

C. J. Date, An Introduction to Database Systems (Addison-Wesley, Reading, Mass., 1986).

S. Akyokus, P. B. Berra, “Optical content addressable memories for data/knowledge base processing,” presented at the Fifth International Symposium on Parallel Processing, Anaheim, Calif., 1991.

C. Warde, A. Fisher, “Spatial light modulators: applications and functional capabilities,” in Optical Signal Processing, J. Horner, ed. (Academic, 1987), New York, pp. 478–524.

F. B. McCormick, Photonics in Switching (Academic, Boston, 1993), Vol. II, Chap. 4.

H. J. Caulfield, “Massively parallel optical data base management,” in Digital and Optical Shape Representation and Pattern Recognition, R. D. Juday, ed., Proc. Soc. Photo-Opt. Instrum. Eng.938, 52–54 (1988).

S. Y. Su, Database Computers: Principles, Architectures, and Techniques (McGraw-Hill, New York, 1988).

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

Fig. 1
Fig. 1

Overview of relational operations. Each relation is a database table with rows called tuples and columns called attributes.

Fig. 2
Fig. 2

Structural organization of the OCAPPRP. In the figure, the values written to the CA are simultaneously compared with each of the four values in the RA. The E, G, L, and match/detector registers store the results. Column registers G h , L h , and E h represent the greater-than, lesser-than, and equality searches, respectively, of row CA h and the RA. As an example, we search for all RA values that are greater than 5. Since the number 5 appears in CA 1, register G 1 indicates that RA 1, RA 2, and RA 4 are larger than 5. These rows are then copied to the output array by the 2-D OU.

Fig. 3
Fig. 3

2-D MCU compares each row of the CA with the entire RA by xoring the two in a vector–matrix fashion. The results of these parallel vector–matrix operations appear vertically stacked in the intermediate array (IA), which will later be processed by the equality and the threshold units. The result of (CA 1) XOR (RA) appears in the lower block of the IA because of a vertical inversion resulting from the optical implementation.

Fig. 4
Fig. 4

Equality unit determines the match–mismatch of input pairs from the CA and the RA by detecting the presence of at least one mismatching bit position. Mismatching bit positions, represented as logical ones in the IA, are detected when the bits are nored across IA rows. In the figure, the second row from the top of register E 1 is set, which means that the word in RA 2 is equal to the word in CA 1. TRhe M/D register reports the matching of the corresponding CA row with at least one row of the RA.

Fig. 5
Fig. 5

Polarization-encoding scheme used for xoring the CA and the RA. The enabled CA is xored with the logical values written to the spatial light modulator (which stores the RA) to form the IA.

Fig. 6
Fig. 6

Optical implementation of the 2-D MCU. Each row of the CA is xored with the RA and reported in the IA in accordance with Fig. 3.

Fig. 7
Fig. 7

Side view of Fig. 6, which illustrates the operation of the 2-D MCU. Each row of the CA is deflected by a different angle. A cylindrical lens array focuses them so that they each form individual expanding beams. The cylindrical lens in the focal plane redirects the off axis beams so that they all pass through the SLM. The cylindrical lens–SLM combination performs the xor operation while focusing the individual beams so that they can be properly scaled and aligned. The realignment step is performed by the third cylindrical lens placed in the beam’s focal plane. The following cylindrical lens array collimates the result beams into a vertically stacked arrangement to form the IA. Because only cylindrical lenses are used, the input beams are unaltered along the top view as they propagate through the system. Notation is the same as that of Fig. 6.

Fig. 8
Fig. 8

Optical implementation of the threshold unit. The optical implementation is continued in Fig. 9. A detailed illustration of the holographic interconnect may be found in Ref. 10. BS’s, beam splitters; PBS, polarizing beam splitter.

Fig. 9
Fig. 9

Optical implementation of the threshold unit (continued). Rotated bits of the greater-than data array resulting from the disabling step appear in Pl1. They are then disabled by a polarizer to form Pl2. One copy of Pl2 is horizontally summed to form the G registers while the other copy is vertically and horizontally summed to form the rank vector, which is used only for sorting. Notation is the same as that of Figs. 6 and 8.

Fig. 10
Fig. 10

Implementation of the 2-D optical OU. A 2-D AO cell in the Fourier plane of a 4-f system redirects the RA rows so that they are shifted in the OA. Row RA 2 is disabled since it did not satisfy the search and does not appear in the output.

Tables (1)

Tables Icon

Table 1 Summary of the Execution Times for Implementing the Full Set of Relational Operations on an OCAPPRPa

Equations (4)

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

[ c a ( m - 1 ) c a 1 c a 0 ] [ r a 1 ( m - 1 ) r a 11 r a 10 r a 2 ( m - 1 ) r a 21 r a 20 r a k ( m - 1 ) r a k 1 r a k 0 ] = [ r a 1 ( m - 1 ) c a ( m - 1 ) r a 11 c a 1 r a 10 c a 0 r a 2 ( m - 1 ) c a ( m - 1 ) r a 21 c a 1 r a 20 c a 0 r a k ( m - 1 ) c a ( m - 1 ) r a k 1 c a 1 r a k 0 c a 0 ] ,
[ c a 1 ( m - 1 ) c a 11 c a 10 c a 2 ( m - 1 ) c a 21 c a 20 c a n ( m - 1 ) c a n 1 c a n 0 ] [ r a ( m - 1 ) r a 11 r a 10 r a 2 ( m - 1 ) r a 21 r a 20 r a k ( m - 1 ) r a k 1 r a k 0 ] = [ r a 1 ( m - 1 ) c a 1 ( m - 1 ) r a 11 c a 11 r a 10 c a 10 r a 2 ( m - 1 ) c a 1 ( m - 1 ) r a 21 c a 11 r a 20 c a 10 r a k ( m - 1 ) c a 1 ( m - 1 ) r a k 1 c a 11 r a k 0 c a 10 r a 1 ( m - 1 ) c a 2 ( m - 1 ) r a 11 c a 21 r a 10 c a 20 r a 2 ( m - 1 ) c a 2 ( m - 1 ) r a 21 c a 21 r a 20 c a 20 r a k ( m - 1 ) c a 2 ( m - 1 ) r a k 1 c a 21 r a k 0 c a 20 r a 1 ( m - 1 ) c a n ( m - 1 ) r a 11 c a n 1 r a 10 c a n 0 r a 2 ( m - 1 ) c a n ( m - 1 ) r a 21 c a n 1 r a 20 c a n 0 r a k ( m - 1 ) c a n ( m - 1 ) r a k 1 c a n 1 r a k 0 c a n 0 ] ,
E h = [ e 1 h e 2 h e k h ] = [ [ R A 1 ( m - 1 ) C A h ( m - 1 ) ] [ R A 11 C A h 1 ] [ R A 10 C A h 0 ] ¯ [ R A 2 ( m - 1 ) C A h ( m - 1 ) ] [ R A 21 C A h 1 ] [ R A 20 C A h 0 ] ¯ [ R A k ( m - 1 ) C A h ( m - 1 ) ] [ R A k 1 C A h 1 ] [ R A k 0 C A h 0 ] ¯ ] ,
1 0 0 0 0 0 0 0 0 0 1 1 1 1 d 1 1 1 1 0 0 0 0 d d 0 0 1 0 0 0 0 d d d d 0 1 1 1 .

Metrics