A Constant-Time Parallel Sorting Algorithm and Its Optical Implementation.
Sorting is a fundamental operation that has important implications in a vast number of areas. For instance, sorting is heavily utilized in applications such as database machines, where hashing techniques are used to accelerate data processing algorithms. It is also the basis for interprocessor message routing and has strong implications in video telecommunications. However, high- speed electronic sorting networks are difficult to implement with VLSI technology because of the dense, global connectivity required. Optics eliminates this bottleneck by offering global interconnects, massive parallelism, and noninterfering communications. We present a parallel sorting algorithm and its efficient optical implementation using currently available optical hardware. The algorithm sorts n data elements in few steps, independent of the number of elements to be sorted. Thus, it is a constant-time sorting algorithm (i.e. O(1) time). This is a significant performance improvement over state-of-the-art electronic sorting systems where the fastest sorting algorithm for n elements takes O(log n) but requires O(n2) processors. We provide the detailed description of an optical system for generating the rank of a data set and physically reordering it. This is evidence that problems considered "solved" using conventional approaches need to be reconsidered so that the benefits of optics can be properly utilized to obtain new, faster solutions to old problems.
Introduction
Sorting is a basic, fundamental operation used for many symbolic, numeric, and artificial intelligence
(AI) tasks. Some of the applications of sorting include the "togetherness" problem,
i.e., the problem of bringing all identical items in a list or file together. Sorting can also be
used for matching problems, for example, if one is trying to find all matching entries of two
files. If both files are first sorted, then all matching entries can be found in one pass through
the data. A sort can also be used in database and knowledgebase processing. Sorting algorithms
can serve as a basis for performing many common and highly useful operations such
as selection, projection, division, and join in the context of relational databases, and inter-
section, union, difference, and cartesian product in the context of sets. Sorting can be used
to simplify searching. In addition to its widespread use in information processing, sorting is
also important in communications where it serves as the basis for packet routing in networks.
Because of its importance, there has been a great deal of work on developing and analyzing
sorting algorithms and architectures. In general, a sort on a string of n data elements can be
done with O(nlog 2 n) comparisons using the best serial algorithms [1]. Using a conventional
sorting network and taking advantage of parallelism as much as possible permits sorting to
be done in O(log 2 steps. Optical architectures for sorting are worth developing for
two reasons: (1) less conventional architectures may permit a sorting operation to be done
in far fewer steps, and (2) the fastest conventional sorting networks seem to require fairly
dense, globally connected networks that are difficult to implement with conventional electronic
technology alone. An example of the latter is a sorting network based on Batcher's
bitonic sort [2], and for a string of 2 k data elements requires k(k+1)stages. Each stage consists
of Fast Fourier Transform (FFT)-like butterfly interconnections of varying sizes.
Optical technology with its inherent parallelism, high spatial and temporal bandwidths,
and non-interfering communications is well suited for implementing the sorting operation.
In particular, optics is very attractive for sorting because of its ability to process two-dimensional
data arrays in parallel. A two-dimensional optical system has an extremely
high number of individual communication channels, all operating in parallel. Besides this
parallelism, optical interconnects permit the efficient and high-speed implementation of the
global connection patterns required for sorting algorithms. Most importantly, optical systems
permit the implementation of sorting with an execution time independent of the number of
data elements to be sorted (i.e., O(1) time), this is in contrast to electronic sorting systems
where the execution time is some function of the number of data elements. In addition, optical
sorting systems have minimum time-skew and may communicate information at optical
media bandwidths. Thus the sorting throughput can be quite large and is limited in practice
by the response time of the optical active devices used. Finally, due to the widespread use
of optical storage technology in modern high-performance computers and communication
systems (ie. Asynchronous Transfer Mode switches), the data to be sorted is already in optical
form, which may make optical sorting systems commonplace in future high-performance
computers and communication systems.
This paper explores the problem of sorting, discussing the optical implementation of a
highly parallel sorting algorithm that takes into account the unique properties of optics.
Several optical sorting algorithms have been proposed in the past [3]. Stirk and Athale [4]
proposed a parallel-pipelined sorting algorithm using optical compare-and-exchange modules
that has a time complexity of O(log 2 n) steps. Researchers at IBM also proposed an optical
enumeration sort [5] using an optical system based on phase addition and subtraction (inter-
ference) to perform analog algebraic operations. However, these coherent systems, as they
are referred to, are difficult to construct since the alignment is very critical. Furthermore,
the authors of the above-mentioned systems failed to suggest a way of physically reordering
the data elements after their positions in the sorted output are determined. This restricts
the system's usefulness to pointer-based computing systems. In this paper, we propose an
optical system capable of both determining the positions of the sorted data elements and
physically reordering them in O(1) time steps. It uses photonics for highly parallel inter-connects
and optoelectronics, in the form of "smart pixels" [6, 7] and deformable mirror
devices (DMDs) [8, 9, 10] for processing. Thus, it exploits the advantages of both the optical
and electrical domains. The paper is organized as follows. Section 2 introduces the parallel
sorting algorithm. Section 3 discusses the detailed optical implementation of the algorithm,
the devices used, and related issues. Section 5 concludes the paper.
2 A Constant-time Parallel Sorting Algorithm
Given the ability of optics to process 2-D arrays of data in one step, parallel algorithms of
the "divide and conquer" classification [11], that are infeasible on electronic computers due
to the requirement of a large number of processors, become relevant. On occasion these are
also the most natural way of describing a solution to the problem at hand. For example,
to sort an array of n numbers, we need to compare every number to every other number,
and thus compute its rank (position in the sorted output). In what follows, we describe a
sorting algorithm that implements exactly the above strategy in constant time ( i.e. O(1),
independent of the number of words being sorted). In Section 3, we describe an optical
implementation of each of the steps.
Before formalizing the algorithm, let us first discuss the conventions that will be used
in this example and throughout the rest of the paper. Row vectors will be indicated by
lowercase underlined letters, such as x, for example, whereas an uppercase letter indicates a
matrix. A subscript indicates the index of the vector or matrix. Thus, x j indicates the j th
element of the row vector x, A i;j indicates the element in the i th row and the j th column of
matrix A. On occasion, the notation x i will be used to indicate the i th element of column
vector x T , where the i illustrates a correspondence to a matrix row. Finally, two-dimensional
(2-D) data will be referred to as matrices in the context of algorithms and data arrays in
the context of optics. This is done to adhere to both mathematical and optical conventions
for representing 2-D arrays.
Let us consider as an example, sorting the data vector Recall that
sorting an n element vector requires comparing each element of the vector against every
other element of the vector, implicitly or explicitly. This problem can also be formulated
as broadcasting the vector a, and performing one comparison operation for every resulting
pair of elements. As optics allows the processing of two-dimensional data arrays in parallel,
we vertically "spread" the vector a such that we can take advantage of this property. This
creates n copies of the original vector a, and places them in a matrix, say A. In the case of
our example,
Hence, each element of the original vector occupies one column of the new matrix. Now,
if we take the transpose of this spread matrix, each element of the original vector occupies
one row of the transposed matrix.
A T =6664
(2)
The comparison operation between every pair of elements of a is then performed by
taking the difference of the two matrices A and A T where the subtraction is represented as
the addition of a negative quantity.
Note that in the difference matrix D, each column j represents the comparison information
for element a j with every other element of a. Recall that if we are to sort the elements, the
rank of an element indicates its position in the sorted output. It is required that even though
the elements a j of the original vector might not be unique, i.e. multiple occurrences of the
same value, each element is assigned a unique rank from 1 to n. The rest of the sorting
problem then involves using the information in the difference matrix to arrive at a unique
rank for each element in the original vector. Each negative number in column j of D implies
the existence of an element a i ? a j . Then, if we are sorting the numbers in an ascending
order, by the definition of rank given above, a negative number in column j of D contributes
0 to a j 's rank. By a similar argument, each positive number in column j of D contributes 1
to the rank of a j . Finally, all zeroes in column j represent non-unique elements, i.e., numbers
with value equal to a j . Each column necessarily contains one zero, the result of comparing
a j against itself. If we allow zeroes to also contribute one to the rank of a j , we arrive at the
R =6664
meaning that a i appears after a j in the sorted output and
should not contribute to a j 's rank. Similarly, R indicating that a i will
appear in the sorted output before a j and contributes to its rank. Summing each column j,
we obtain the non-unique rank for the corresponding element a j . Thus, in the case of our
example, the ranks of the sorted elements are:
Notice that the multiple instances of the number 8 are assigned the same rank. To resolve
the non-unique ranks, we break ties by comparing the locations of the two elements being
compared. So for every two non-unique numbers in the vector a, if one occurs before the
other, then we consider it to be the larger of the two. Hence, for every fi; jg, such that
as though a i ? a j . To translate this into an operation
on the difference matrix D, we focus our attention on the zeros of D. As mentioned, the
existence of zeros on the main diagonal is guaranteed since the condition
the comparison of an element to itself. Thus, they are of no concern to us. However, zeros
of D for the condition i 6= j mean that the two different elements of a being compared are
equal. Hence, we have identified the existence and location of non-unique numbers. Each
pair of non-unique numbers is repeated, the first in fi; jg and the second in fj; ig. Since we
only need to modify the rank of only one occurrence, we select the earlier occurrence to have
the smaller rank. By our revised rule, if D should not contribute
to the rank of a j , and hence should be negative. Notice that we need to consider modifying
only the upper triangle portion of the difference matrix D. To do so, we create a new matrix
U , where U
U =6664
Next, we subtract U from D, again, by the addition of a negative quantity.
In this new difference matrix D 0 , the negative elements of D remain negative, and hence
contribute nothing to the rank of an element. The positive elements remain positive, or
become 0, and hence, if we consider that all zeroes contribute one to the rank of an element,
the positive elements still contribute the same amount to the rank of an element. The zeros
in the upper triangular portion of the matrix D become negative in D 0 . This resolves the
ties between non-unique ranks in the manner described above. The new rank matrix is then:
indicates that a i appears in the sorted output after a j and R
the opposite. Summing each column of R 0 , we get the fully resolved ranks of each elements
in a.
The result from the algorithm is the generation of the rank vector,
contains the positions of each of the data elements in the sorted output. This algorithm and
an accompanying optical system are complete when they are capable of rearranging the input
data to the order reported in r. The problem of physically reordering the data reduces to
the task of determining, in parallel, which column of r contains the number 1, the number 2,
etc. so that we know which element is 1st, 2nd, etc. in the sorted output. We accomplish this
by comparing each element of r to the numbers [1; . ; n]. Mathematically, this is illustrated
as spreading the r vector n times and subtracting the vector [ horizontally
times, as in the following:
\Gamma6664
In the resulting matrix on the righthand side of Eqn. 8, S highlighted by boldfacing,
indicates in which column j, of r, the value i exists. It tells us that a j is to be relocated to
row i of the sorted output, where we assume the sorted output as a column vector. Note
that S only one element per row of S. If we use S to select/discard elements
from a copy of the A matrix, such that elements select elements A i;j and elements
effectively rearranged the inputs to their positions
in the sorted output. This operation is illustrated below where the selected elements are
boldfaced.
A =6664
Thus, the problem of reordering the data reduces to selecting the appropriate element
from each row of A, since each row of A has a copy of each data element, and discarding the
rest. The discrete steps for constant time sorting are summarized below.
1: Process the input:
(a) Generate matrix A by vertically spreading a n times.
(b) Generate matrix A T by horizontally spreading a T n times.
Step 2: Compare every element of a with every element of a T by computing the difference
Step 3: Generate the U matrix, where U
Step 4: Resolve non-unique ranks by computing matrix D
Step 5: Generate R 0 by thresholding D 0 , where R
Step the rank vector, r, by summing each column of the matrix R 0 .
Step 7: Reorder the sorted data:
(a) Compare every element of r to every element of [1; . ; n] T by expanding both by
n and subtracting the latter from the former to form the S matrix.
(b) Use S to select/discard A where S indicates that data element A i;j should
be transferred to row i in the sorted output.
In Section 3, we present an efficient and economical optical implementation of the proposed
algorithm.
Optical Implementation of the Constant-time Parallel
Sorting Algorithm
We will now consider an optical system that implements the above steps and uses the rank
vector to physically reorder the input data in constant time. We use currently available
components to demonstrate its feasibility. The system contains a mixture of optics and
electronics. Photonics are used for highly parallel, non-interfering interconnects while elec-
tronics, integrated into arrays of "smart pixels", are used for processing. The development
status of these devices is discussed in Refs. [12] and [13]. Smart pixels are optoelectronic
devices which combine optical detectors, simple processing electronics, and optical modulators
or sources on a single substrate for high-speed processing of 2-D data arrays [6, 14].
These devices take advantage of the strengths of both the optical and electrical domains.
Photons do not readily interact with each other in the optical domain. Thus, it is an ideal
communications environment. However, this makes photonics difficult for switching and
control. Electrons, on the other hand, interact very easily which makes them convenient for
controlling each other. Smart pixels capitalize on the benefits of electronics for switching and
control, and photonics for highly parallel communication. The integration of optical sources
provide signal regeneration to the following stage. Furthermore, each of their components
can be readily fabricated with conventional Si and GaAs processing techniques. Some examples
of these are SEED-based [13], Si/PLZT-based [15], and VSTEP-based [16] smart
pixels.
A promising class of lasers that may be used as optical sources both within smart pixels
and as system input is vertical-cavity surface-emitting microlasers [17]. They are capable of
being integrated in densities of over one million microlasers with dimensions of a few -m on
a single chip. Their development is an important milestone in the realization of high-density
optically-interconnected systems.
3.1 Optical Algebraic Operations
In order to implement steps 2, 4, and 7 of the algorithm, we must have a way of subtracting
two numbers. Since the intensity of light cannot be less than zero, we use a dual-wavelength
scheme for representing both positive and negative results [18]. For ease of explanation,
we assume that we are only sorting positive values. Negative values will then occur only
as the subtraction result of two positive numbers. The system can be modified slightly to
accommodate negative data elements, but it is more cumbersome to explain and is avoided
in this paper.
Positive data numbers are represented by the positive light intensity level of one wave-
negated values are represented by an equal positive light intensity
level of a second wavelength, - 2 . Thus, a number is considered negative merely by the fact
that it is encoded on - 2 . Subtraction is performed by first superimposing (summing), via a
beamsplitter, the two modulated wavelengths. Since photons do not interact in free space,
the actual subtraction of the absolute values written to - 1 and - 2 is performed electronically.
The light of wavelength - 1 impinges upon a photodetector preceded by a - 1 color filter while
the light of - 2 impinges upon a photodetector preceded by a - 2 color filter. The color filters
are included to eliminate any crosstalk from the opposing wavelength. In general, the two
wavelengths should be chosen so that their separation is larger than the pass bandwidth
of the filters. The positive photodetector outputs, V (- 1 ) and V (- 2 ), are then fed into the
positive and negative terminals, respectively, of an op-amp, where the subtraction of the
absolute values, occurs.
3.2 Generating the Rank Vector r
3.2.1 Implementation of Step 1 of the Algorithm
Fig. 1 illustrates an optical implementation for the first two steps of the algorithm. In
Step 1, the one-dimensional (1-D) input, a, modulates the columns of a 2-D laser array of
wavelength - 1 to form the A array. Meanwhile, a T modulates the rows of a 2-D laser array
of wavelength - 2 to form the \GammaA T Array (where the '-' is inherent in the use of - 2 ). This
differs slightly from our algorithm which suggested that the two vectors be vertically and
horizontally spread n times with optics. We avoided spreading because the beam intensity
and "distance" between analog levels are reduced to 1
n times the levels of the original beam.
The latter reduction makes it more difficult to distinguish the analog levels at the detectors.
Beam
Electrical
inputs
Electrical
inputs
A Array of
wavelength
positive weights ]
A Array of
wavelength
negative weights ]
column
2-D array of
lasers of
wavelength
2-D array of
lasers of
wavelengthllll
2-D array of laser light
Legend
optical array of
wavelength 2
l
optical array of
wavelength 1
l
optical array of
superimposed wavelengths
and 2
ll
Step 1: Step 2:
light of
wavelength
light of
wavelength5ll
superimposed
light of
andll

Figure

1: The figure presents the optical hardware for implementing steps 1 and 2 of the
algorithm. A and A T are formed by modulating 2-D laser arrays, with wavelengths - 1 and
by a and a T , respectively. These are "summed" to form the difference matrix D.
Furthermore, the beam spreading approach results in more crosstalk (assuming non-ideal
filters) for this particular system since multiple wavelengths would overlap on the same
detector.
3.2.2 Implementation of Step 2 of the Algorithm
Beam
Splitter
Array
-U Array of
wavelength
negative weights ]l000101011100Step 3:
Array
column
Step 4:

Figure

2: The figure illustrates the optical implementation of Step 3 and part of Step 4 of
the proposed algorithm. To resolve non-unique ranks, U is "added" to D to form D 0 , where
the actual subtraction is performed in the next stage, shown in Fig. 3.
The difference array D of Step 2 is formed by "summing" arrays A and \GammaA T . This is
performed optically by merging their optical data planes with a beamsplitter. Recall, that at
this stage, the beams are merely superimposed and the actual subtraction will be performed
later. In Fig. 1, each element of the D array contains two numbers that represent the
superposition of the two colors. The number in the upper right corner represents the intensity
level of the - 2 light component while the number in the lower left corner represents the - 1
light component.
3.2.3 Implementation of Steps 3, 4, 5, and 6 of the Algorithm
Surface-emitting
laser
Op-amp and
thresholding
electronics
Laser driver5l
light intensity level
of wavelengthl
light intensity level
of wavelength
th
Prism
(spatially separates
two wavelengths)
Photodetector
w/ filterl
Photodetector
w/ filterl
l
A single pixel
from D array
Light of Wavelength 1
l
Light of Wavelength 2
l A Single
Smart Pixel

Figure

3: Illustrating the implementation of the actual subtraction from Step 4 and all of Step
5 for a single pixel, the D 0 pixel passes through a prism which separates the two wavelengths.
These light components impinge upon their corresponding photodetectors in the smart pixel
to generate V (- 1 ) and V (- 2 ). The op-amp performs the subtraction
The output is thresholded, the result of which modulates the laser driver.
Fig. 2 illustrates the implementation of Step 3 and part of Step 4. The \GammaU array of Step 3
is formed by modulating a 2-D laser array (not shown) of wavelength - 2 . The summation
of D and \GammaU in Step 4 is performed by the second beamsplitter in Fig. 2. Fig. 3 illustrates,
for a single pixel, the subtraction by the smart pixel of the absolute values in D 0 . Notice the
integration of the photodetectors, modulation electronics, and the surface-emitting laser in
this close-up view of a single smart pixel. The wavelengths of the D 0 Array are separated by a
prism and imaged onto the photodetectors residing within the smart pixel array. The op-amp
subtracts the detected value of - 2 , V (- 2 ), from the detected value of - 1 , V (- 1 ). The output
is then thresholded by a CMOS gate (not shown). The digital output from the thresholding
operation of Step 5 then modulates the surface-emitting laser for communication to the next
stage.5
1Cylindrical
Lens
Prism
Beam
Splitter Smart
Pixel
Array24Rank
Vector
light of wavelength248287582875
3 828758287582857D Array R Array
light of wavelengthll
Column
Column
(As viewed
from behind)

Figure

4: The optical system for implementing the actual subtraction phase of Step 4 along
with Steps 5 and 6 on a full scale. The prism separates the wavelengths so that they may
impinge upon their corresponding photodetectors on the smart pixel array. The subtraction
and thresholding of Steps 4 and 5 are performed by the integrated electronics in the smart
pixel array. The surface-emitting laser writes the result to the R 0 array which then reflects
off the beamsplitter and is then vertically summed by the cylindrical lens to form the rank
vector, r, in Step 6. Notice that the labeling conventions on the D 0 array in this figure have
been changed to mirror the fact that we are now viewing it from behind.
Fig. 4 illustrates Steps 4, 5, and 6 on a full scale where the labeling conventions of the D 0
array have been altered since it is being viewed from the backside in this figure. The output
of the electronic subtraction and thresholding of D 0 by the smart pixel array modulates
the surface-emitting lasers to generate the R 0 array. Since the lasers are integrated on the
same side of the substrate as the photodetectors, the R 0 array propagates back into the
system and reflects off the beamsplitter. The cylindrical lens, which focuses a beam only
in one dimension, vertically sums the ones in the R 0 matrix to form the rank vector, r, in
accordance with Step 6. To this end, the rank vector r is generated. Next, we need to
reorder the input data according to the rank vector. We should note that this additional
step may not be required for all applications. For example, if the data elements are sorted
in a content-addressable memory, then any data element can be recalled directly by its rank,
and if this is what is needed, then physical reordering is not necessary.
3.3 Physical reordering of the input data
3.3.1 Step 7:

Figure

5: The architecture of a single torsion beam DMD pixel [8].
In addition to the generation of the rank vector, an equally important aspect of this paper
is the physical reordering of the input. This has received little attention previously since
prior systems generally proceeded as far as generating the rank vector and recommending
its use as a pointer. Our system uses a novel technique involving torsion-beam DMDs for
accomplishing this final step. DMDs are micromechanical arrays of mirror elements that
are capable of mechanical movement in response to an electrical input. Incident light is
modulated in its direction by reflection from rotated pixels. DMDs are addressed optically
or by integrated circuits. In an optically-addressed device, integrated photodetectors convert
incident beams of light into electrical control signals for the mirror elements. DMDs are also
highly efficient light modulation devices since they modulate under reflection. The devices
exhibit a reflectivity of - 90% [10] with a contrast ratio of 2500:1 [9] for the torsion-beam
configuration. Its pixel switching time is comparable with other optical light modulators.
Furthermore, DMDs are fabricated with conventional Si and GaAS processing techniques
and have been reported in sizes of 1920 \Theta 1080 elements [19].
Torsion Beam
Reflected light for
no angular beam
deflection
Reflected light for
angular beam
deflection of
Reflected light for
angular beam
deflection of
Incident light
Address Electrodes
Landing Electrodes
Differential Bias
Position 2
Position 1
Position 3

Figure

Cross sectional view of a torsion beam DMD pixel illustrating the effects of the
three mirror positions on an incident light beam [8].
The architecture of a single mirror is illustrated in Fig. 5. In the torsion-beam configura-
tion, a square pixel is suspended over an air gap by two thin torsion hinges connected to two
rigid supports. As voltages are applied to the address electrodes, the pixel deflects about the
hinge in response to the electric field. This results in a change in the direction of the incident
light. A cross sectional view of a single mirror is shown in Fig. 6. The differential voltage
on the address electrodes causes the torsion beam to be attracted toward the more positive
electrode. At increasing voltage levels, the angular deflection of the beam increases until it
contacts the landing electrode, which prevents any further deflection. This corresponds to
an angular deflection, ' , of approximately \Sigma10 . The torsion beam and landing electrodes
are held at the same potential in order to prevent current flow upon contact. By applying
a differential bias to the beam and landing electrodes, the voltage required for maximum
angular deflection can be reduced to TTL levels. This differential bias also determines the
number of digital deflection states. In the bistable condition, the beam is in a state of equilibrium
at an angular deflection of meaning that it must be deflected to either the
right or the left. In the tristable condition, the beam is in a state of equilibrium at angular
deflections of We use the tristable condition in our design since the
subtraction result of Step 7a can be negative, zero, or positive.
Optical Axis
Cylindrical
Lens
A single deformable
mirror pixel
(demonstrating
positions 1 and 2)
Top View
Beam
Splitter
Incident light
f
F
F
Opaque Screen
w/ on-axis
opening
Legend
Incident light
Reflected light
F On-axis
Focal Point
F Off-axis
Focal Point
f Focal length
Position 1
Position 2

Figure

7: A top view of the optical system for reordering sorted data. Here, we demonstrate
the use of a DMD to separate data elements. Incident light enters from the side where it
reflects off the beamsplitter and impinges on the DMD mirror. It is then reflected depending
on the mirror's position. Light reflected from position 1 is focused by the cylindrical lens to
point F along the optical axis while the light reflected from position 2 is focused to F'. Thus,
data can be spatially separated by controlling the mirror's position.
Fig. 6 also illustrates the operation of a DMD pixel for the three addressing conditions
potential differences across the electrodes,
results in no angular deflection (position 1) of the torsion beam whereas a
positive potential difference, results in a counterclockwise deflection (position
2) of the torsion beam by 10 . In this position, the incident light is reflected to the left.
Similarly, a negative potential difference deflects the torsion beam counterclockwise by 10
(position 3). Fig. 7 shows a top view of the actual system. Incident light enters from the side
where it is reflected by the beamsplitter and impinges on the DMD pixel. It is then reflected
by the mirror in the direction determined by its position. The reflected beam passes through
the beamsplitter and is focused by the cylindrical lens to a point a distance f from the lens,
where f is the focal length of the lens. Light reflected by the mirror in position 1 is focused
to point F along the optical axis while light reflected by mirror position 2 is focused to point
F'. An opaque screen, with an on-axis opening, blocks the off-axis beam. Thus, data can be
disabled by applying a nonzero potential difference to the DMD's address electrodes so that
the data beam is deflected and focused off-axis, where it is then blocked by the screen.
The optical system in Fig. 8 builds upon these principles to perform the final step of the
algorithm. The first task is the subtraction of the horizontally spread version of [1; . ; n] T
from the vertically spread version of r as outlined in Eqn. 8. To facilitate this, we propose
that the DMD be fabricated such that the column addressing electrodes, V c , of each cell in
a column be connected. Similarly, the row addressing electrodes, V r , of each row should be
connected. This allows us to address the entire array in parallel while also performing the
vector spreading operation required in Eqn. 8. We load r onto the column electrodes and [
onto the row electrodes. The array can be easily implemented by a resistive
network integrated onto the device substrate since its values remain the same for each sort
unless the order of the sort (ascending or descending) is changed. The column addressing lines
may be either electrically or optically-addressed. In the optically-addressed configuration,
an array of photodetectors is integrated onto the DMD substrate which connect internally
to the column addressing lines. To implement this, the r array formed in Fig. 4 is imaged
directly onto the integrated photodetectors. In the electrically-addressed configuration, the
r vector is imaged onto an external photodetector array which is then connected to the
column addressing lines through DMD chip I/O. The optically-addressed configuration is
preferred since it is directly scalable with array size as opposed to the electrically-addressed
configuration which is limited by the device pinout.
If we consider an element of S as the subtraction of a row electrode voltage from a col-
Cylindrical
Lens
Beam
Circles represent
locations of selected
data elements to
appear in the sorted
output
Sorted data
(physically
reordered)
Focal lines
for
DMD positions
Rank vector is written
to column addressing
lines either by
electrical-addressing
or optical-addressing
Array is generated
internally by a resistive
network and written to
the row addressing lines7722255888
A array
(As viewed
from behind)88135
Column
Column index
Boldface values represent
locations of selected data
elements to appear in the
sorted output
Deformable
Mirror
Device
Optical
Axis
Opaque Screen
w/ opening along
the optical axis58Lenslet
Array

Figure

8: Optical setup for physically reordering the sorted input. The A array reflects off
the beamsplitter and is imaged onto the DMD. Selected elements of A reflect off the mirrors
and are focused to a column that lies within the opening of the opaque screen by the lenslet
array and the cylindrical lens. Elements of A to be discarded reflect off the mirror and are
focused to off-axis columns where they are permanently blocked by the screen.
umn electrode voltage, we see that the DMD addressing condition implements the
subtraction in Eqn. 8. Thus, S represents the potential difference across the addressing elec-
trodes. Since the elements selected elements, one per row, of A, the selected
elements are focused to a column at the opening of the opaque screen by the lenslet array
and the cylindrical lens. Elements of A such that S i;j 6= 0 are deflected by the mirror array
and are focused to off-axis columns. The opaque screen discards these, in accordance with
Eqn. 9 by blocking them from the rest of the system. Thus, we have effectively demonstrated
the implementation of Eqn. 9, the physical reordering of the sorted data.
In Fig. 9, we present the physical layout of the proposed optical sorting system. The two
vertical-cavity surface-emitting lasers (VCSELs), V1 and V2, provide the 2-D optical input
data as mentioned in Section 3. V1 generates the A array with wavelength - 1 . In order
to reduce the amount of hardware required (a VCSEL and beamsplitter BS2) while also
reducing the power loss due to beamsplitting, the \GammaA T and \GammaU arrays are generated by a
single VCSEL. Since U is an array of constants, it can easily be added to the A T array as
one of the inputs to the laser drivers for the VCSELs in V2. Since V2 is of wavelength - 2 ,
it provides the array U) to be "added" to A to form the D 0 array. Two copies of
the D 0 array are generated by beamsplitter BS1. One copy is imaged onto SP by polarizing
beamsplitter PBS1 for the generation of the R 0 array. The rank vector is formed by CL1 and
imaged onto the column addressing photodetectors of DMD. In order to preserve the parity
of the array, this 90 degree deflection can be implemented with a pentaprism (not shown)
instead of a mirror. The other copy of D 0 is imaged onto the pixels of DMD by PBS2 for
the reordering step. Since this step requires the A array, a color filter that passes only light
of wavelength - 1 removes the elements from the D 0 array, leaving behind only the
A array. After DMD selects the appropriate elements of A, the sorted data is imaged onto
the 1-D detector array, DET, by the lenslet array, LA, and the cylindrical lens, CL2.
The layout in Fig. 9 suggests that the system volume should be very small. Using 1in.
aperture optics (lenses, beamsplitter and half-wave plates) with a modest 1.5in. component
separation, we see that the entire system can fit in an area of about 20cm \Theta 20cm. Although
l 2
l
Legend
array
array
array
array
Half-wave plate
Filter
Polarizing Beamsplitter
CL - Cylindrical Lens
(Actually
implemented as a pentaprism
to preserve beam parity)
addressing
unit
CF
A arraylll
R array
A array
Electrical
Inputs
Electrical
Inputs
array
(As viewed from behind)
(As viewed from behind)
Approx. 20cm
Approx.
20cm
LA

Figure

9: Layout of the proposed optical sorting system.
the above measurement doesn't include the interface electronics or the heat removal compo-
nents, the complete optical system should be small enough to be manufactured as an add-on
unit for mainframe computers.
Next, we estimate the space bandwidth product (SBWP) of the proposed optical sorting
system. For simplicity, we assume that the lengths of the pixel of the active components
(VCSELs, SP array, and DMD) have the same value which is a. For the given optical setup
of Fig. 10, the diffraction-limited spot diameter, D d , at the detector plane is given by [20]
cl
a
where - denotes the wavelength of the light and f cl represents the focal length of the cylindrical
lens CL2. Then, the maximum height of the image at the detector plane, hM , becomes
f cl la
f
a
Lenslet
Array
Optical
Axis
la
lens focal length
cl - lenslet array focal length
a - lens diameter of the lenslet array
and DMD pixel size
Legend

Figure

10: A top view of a part of the optical setup of Fig. 9. The figure explains how a
DMD pixel of size a is imaged onto a detector pixel of size hM by the lenslet array and the
cylindrical lens.
cl
f la
\Theta a; (11)
where f la represents the focal length of each lens in the lenslet array. Therefore, the maximum
SBWP is given by
2:44-f la
As discussed in Section 3.3, a 1920 \Theta 1080 element DMD with a pixel size of 17 -m is
reported in Ref. [19]. In a typical optoelectronic smart pixel, the power dissipation limited
SPD is known to be about 200(pixels/cm 2 ) [21, 22]. Thus, the length of a square pixel of
array becomes (
Comparing these two pixel size, we should use
the length of SP array as the value of a since it represents the worst case pixel size in the
system. Assuming - is 0.85 -m and f la is 0.1 mm, the SBWP of the proposed optical sorting
system becomes 2410.
In addition to the SBWP, an equally important parameter is the bit-capacity of the
system, i.e. the word size. Since the proposed optical sorting system is analog, the dynamic
range of the detectors is mostly responsible for determining this value. Currently, light
intensity may be produced, controlled, and detected in about 500 discrete levels [23, 24, 25].
This implies that the sorter has the capability of an 8-bit microprocessor. Obviously, this
limits the word-length of the data that can be sorted in constant time. Note that the number
of data elements to be sorted at once is not affected by this limitation. However, this same
restriction is also imposed upon electronic sorting systems. For a string sort, a typical string
might have between 10 and 20 characters in it. Since both optical and electronic sorters
can only operate on a subset of this string at any time, a single character for instance, the
sorting time is inevitably related linearly to the number of characters. In addition to the
word-length restriction, it is also prohibitive to build a sorting system that is capable of
sorting a sequence length of 10,000 data items without iteration, where a sequence length
is the number of data items to be sorted. In general, the sequence length, m, will be much
larger than the number of items, n, that the sorter can hold at any time. Thus, the data set
will have to be divided into m
smaller data subsets of sequence length n which will then be
sorted separately and compared to each other during multiple passes through the data set.
At first glance, it would seem as though one needs to sort each data subset against itself and
then against each other subsets. This approach would extend the execution time to O( m 2
cycles.
5 Conclusion
Advances in optical computing have opened up new possibilities in several fields related
to high-performance computing, high-speed communications, and parallel algorithm design.
It is necessary to take into consideration the specific properties of optics, such as massive
parallelism and global interconnects, to design algorithms that execute faster.
Sorting is a fundamental operation that has important implications in many areas. In
this paper, we presented a parallel sorting algorithm and its efficient optical implementation
using currently available hardware. The algorithm sorts n data elements in constant time,
i.e. independent of the number of words being sorted. The proposed algorithm can provide
a quantum leap over its electronic counterparts in execution time. The proposed optical
system is capable of both generating the rank vector and physically reordering the sorted
data. Previously proposed optical sorting systems proceeded only as far as generating the
rank vector which was used as pointer.
Our system used state-of-the-art optoelectronic devices such as smart pixel arrays and
deformable mirror devices for spatial light modulation. The algorithm and its optical implementation
presented in this paper are an excellent example of what optics can achieve. As
these optoelectronic and smart pixel devices mature, it is expected that such an algorithm
will have a major impact on sorting applications in the future.



--R

Introduction to Parallel Algorithms and Architectures: Arrays
"Sorting Networks and Their Applications,"
"Fast sorting algorithm based on the massive parallelism of optical computing,"
"Sorting with optical compare-and-exchange modules,"
"Optical facility for parallel enumeration sort,"
"Architectural Considerations for Photonic Switching Networks,"
"A Complexity Analysis of Smart Pixel Switching Nodes for Photonic Extended Generalized Shuffle Switching Networks,"
"Deformable-mirror spatial light modulators,"
"Deformable mirror light modulators for image processing,"
"Mirrors on a chip,"
Introduction to Algorithms - A Creative Approach
"Self-Electro-Optic Effect Devices for Optical Information Processing,"
"Field-Effect Transistor Self-Electrooptic Effect Device: Integrated Photodiode, Quantum Well Modulator and Transistor,"
"Amorphous Silicon Carbide Multilayer Modulators for Silicon Smart Pixels,"
"Two-dimensional silicon/PLZT spatial light modulators: design considerations and technology,"
"VSTEP-Based Smart Pixels,"
"Surface-emitting microlasers for photonic switching and interchip connections,"
"Deformable mirror device spatial light modulators and their applicability to optical neural networks,"
"A 1920 \Theta 1080 Element Deformable Mirror Device for High-Definition Displays,"
Fundamentals of Photonics.
"Implementation of Smart Pixels for Optoelectronic Processors and Interconnection Systems I : Optoelectronic Gate Technology,"
"Implementation of Smart Pixels for Optoelectronic Processors and Interconnection Systems II : SEED-Based Technology and Comparison with Optoelectronic Gates,"
"Linear Acousto-Optic Heterodyning Processors for Complex-Valued Data Processing,"
"Input/Output Devices,"
"High accuracy computation with linear analog optical systems: a critical study,"
--TR
optical computing;parallel processing;parallel sorting;sorting