An Optoelectronic Approach to Sorting

Ruth DeJule, Associate Editor -- Semiconductor International, 3/1/1998

Twenty years ago, the operation of sorting consumed up to 25% of all computing time. Used for various functions from routing phone calls and managing data to searching for information on the web and tracking wafer lots, sorting is a computationally intensive operation, requiring countless comparisons. For example, a list of 1000 wafer ID numbers sorted into ascending order may require as many as 500,000 comparisons.

1. Illustration of an ideal system configuration for the recirculating sorter. Input words are sorted beginning with most significant bit (MSB).

A traditional electronic computer is limited by the I/O bottleneck by executing the sorting operation as a series of single comparison steps, each comparing only two words. Optical transmission can avoid this limitation and enable the simultaneous comparisons of multiple word pairs. Therefore, the number of steps to sort a list of 1000 ID numbers can be reduced by 80% to 1000 comparisons.

2. Video images of
smart-pixel array 1
demonstrate the
recirculating sorter.

W O R D 1	W O R D 2	W O R D 3	W O R D 4
0 1 0 0	1 1 1 0	0 1 1 0	0 0 1 0	Data loaded into system.
0 0 0 0	0 0 0 0	1 0 0 0	0 0 0 0	Clock cycle 1
0 1 0 0	0 1 0 0	0 1 0 0	0 0 0 0	Clock cycle 2
0 0 0 0	0 0 1 0	0 0 1 0	1 0 1 0	Clock cycle 3
0 1 0 0	0 0 0 0	0 1 0 0	0 1 0 0	Clock cycle 4
0 0 0 0	0 0 1 0	0 0 1 0	1 0 1 0	Clock cycle 5
0 0 0 0	0 1 0 0	0 1 0 0	1 1 0 0	Clock cycle 6
0 0 1 0	0 1 0 0	0 1 1 0	1 1 1 0	Clock cycle 7
Final Value

The clear advantage of optical transmission is the absence of physical wires and minimization of problems associated with increasing I/O pad densities. A laser beam can be accurately focused to approximately the wavelength of the light, 1 µm, using current semiconductor laser technology. Since adjacent beams of light do not interact, thousands of laser beams can be focused onto a very small area with virtually no cross-talk.

Ways to route information optically are currently under development throughout the industry. One approach, studied at the University of Cincinnati (Cincinnati, Ohio) and Colorado State University (Ft. Collins, Colo.), is the parallel routing of information onto a CMOS chip. This work involves the use of smart-pixel technology using silicon photoreceivers, CMOS logic circuits and vertical cavity surface emitting laser (VCSEL) based optical transmitters. The sorting unit (Fig. 1) recently demonstrated uses two smart-pixel arrays that transmit data optically.

The integration of all smart-pixel components into a single chip that can be fabricated using standard device fabrication processes is the near-term goal. For this demonstration, a simple low-impedance photoreceiver circuit, including a silicon photodetector, was designed to convert optical input to CMOS-compatible electrical signals. The CMOS chip and VCSEL arrays were packaged on separate device mounts.

An array of light and dark spots (1's and 0's) from a spatial light modulator, for example, are detected by photoreceivers in the CMOS circuit and converted to an electrical signal. Word comparisons are then performed between adjacent words beginning with the most significant bit (MSB) and progressing to the least (LSB). A difference in the digits indicates the relative magnitude of the words being compared. Based on the result of word comparisons, electronic logic gates switch the word positions so that the larger word is always moved to the right. This operation is aptly called compare and ex-change (C&E).

Comparisons are made in both smart-pixel arrays with optical transmission between the two, requiring data conversion back and forth between the electrical and optical do-mains. These conversion steps are implemented using silicon-based photoreceiver circuits on the smart-pixel array input and VCSEL-based optical transmitters on the array output.

To verify proper sorting operation, the optical in-put and output signals were monitored using a video camera (Fig. 2). Four randomly ordered four-bit words, or ID numbers, were input in parallel to the system. The sorting unit performed word comparisons in each smart-pixel array and communicated intermediate results to the opposite smart- pixel array. Several comparisions occurred in parallel: words 1 to 2 and 3 to 4 in array 1, words 2 to 3 in array 2 (each comparison was made on a bitwise basis starting with the MSB) and subsequent pipelining to the LSB. Shown is a sequence of images where the optical signals are illuminating smart-pixel array 1. Four words require just four cycles, however the remaining cycles are necessary to flush the three-bit pipeline. The last video image indicates that the initial input pattern has been completely reorganized to produce a sorted set of numbers, increasing from left to right.