How to Sort N Items Using a Sorting Network of Fixed I/O Size.
AbstractSorting networks of fixed I/O size p have been used, thus far, for sorting a set of p elements. Somewhat surprisingly, the important problem of using such a sorting network for sorting arbitrarily large data sets has not been addressed in the literature. Our main contribution is to propose a simple sorting architecture whose main feature is the pipelined use of a sorting network of fixed I/O size p to sort an arbitrarily large data set of N elements. A noteworthy feature of our design is that no extra data memory space is required, other than what is used for storing the input. As it turns out, our architecture is feasible for VLSI implementation and its time performance is virtually independent of the cost and depth of the underlying sorting network. Specifically, we show that by using our design N elements can be sorted in \Theta({\frac Np} \log {\frac Np}) time without memory access conflicts. Finally, weshow how to use an AT^2-optimal sorting network of fixed I/O size p to construct a similar architecture that sorts N elements in \Theta({\frac N{p}} \log {\frac N{p\log p}}) time.
Introduction
Sorting networks are a well studied class of parallel sorting devices. For an early treatment of the
subject, see [4, 12]; for recent surveys we refer the reader to [2, 3, 7, 19, 22, 23]. In general, sorting
networks are suitable for VLSI realization. This is due, in part, to the fact that the processing
elements are typically simple comparators and the structure of the network is fairly regular.
Several parameters are used to characterize the quality of a sorting network T . The cost of T ,
denoted by C(T ), is the number of constant fan-in processing nodes in the network. The depth of
denoted by D(T ), is the maximum number of nodes on a path from an input to an output. For
Work supported by ONR grant N00014-97-1-0526, NSF grants CCR-9522093 and ECS-9626215, and by Louisiana
grant LEQSF(1996-99)-RD-A-16.
y Department of Computer Science, Old Dominion University, Norfolk, VA 23529-0162, USA
z Istituto di Elaborazione dell'Informazione, C.N.R, Pisa 56126, ITALY
x Department of Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA
example, Batcher's classic bitonic sorting network and odd-even merge sorting network [4, 5] have
cost O(p log 2 p) and depth O(log 2 p), where p is the network I/O size. The time performance of a
sorting network is the number of parallel steps performed, which is usually the depth of the network.
Ajtai, Koml'os and Szemer'edi [1] proposed a sorting network, commonly called the AKS sorting
network, of I/O size p, depth O(log p), and cost O(p log p). Later, Leighton [13] and Paterson [21]
developed comparator-based sorting networks of I/O size p, cost O(p), and depth O(log p) that
elements in O(log p) time. The AKS network is both cost-optimal and depth-optimal (i.e.
time-optimal) in the context of sorting p elements with each comparator used once.
It is interesting to note that in spite of the fact that sorting networks of fixed I/O size p have
been extensively investigated in the context of sorting p elements, their efficient use for sorting
a large number, say N , of elements has not received much attention in the literature. In real-life
applications, the number N of input elements to be sorted is much larger than p. In such a situation,
the sorting network must be used repeatedly, in a pipelined fashion, in order to sort the input
elements efficiently. Assume that the input as well as the partial results reside in several constant-
port memory modules. Then, scheduling memory accesses and the I/O of the sorting network
becomes the key to achieving the best possible sorting performance. Clearly, if an appropriate
answer to this problem is not found, the power of a sorting network will not be fully utilized.
The problem of building sorting networks out of smaller components such as p-sorters and
mergers has received attention in the literature [7, 8, 15, 20]. Bilardi and Preparata [8] use a tree
of of mergers of various sizes to sort using cube-connected cycles. Nassimi and Sahni [15] construct
sorting networks by combining mergers of various sizes. Tseng and Lee [25] construct a sorting
network of I/O size p 2 using O(p) layers of p-sorters. Recently, Parker and Parberry [20] showed
that for arbitrary N , a sorting network of I/O size N can be constructed using p-sorters, thus
answering an open question posed in [12].
A related problem, namely that of sorting N elements by repeatedly using a p-sorter, has
received attention of late [6, 18, 20]. A p-sorter is a sorting device capable of sorting p elements in
constant time. Computing models for a p-sorter do exist. For example, it is known that p elements
can be sorted in O(1) time on a reconfigurable mesh of size p \Theta p [11, 14, 16, 17]. A reconfigurable
mesh is a multiprocessor system in which the processors are connected by a bus system whose
configuration can be dynamically changed to suit computational needs. Beigel and Gill [6] showed
that the task of sorting N elements, N - p,
N log N
log p
calls to a p-sorter. They also
presented an algorithm to sort N elements using \Theta
N log N
log p
calls to the p-sorter. Their algorithm,
however, assumes that the p elements to be sorted by the p-sorter can be fetched in unit time,
regardless of their locations in memory. Since, in general, the address patterns of the operands of
p-sorter operations are irregular, it appears that the algorithm of [6] cannot realistically achieve
the time complexity of O
N log N
log p
, unless one can solve in constant time the addressing problem
on realistic machines. To address this problem, Olariu and Zheng [18] proposed a p-sorter-based
architecture that allows to sort N elements in O( N log N
stricly enforcing conflict-free
memory accesses. In conjunction with the results of [6], their result completely resolves the time
complexity issue of sorting N elements using a p-sorter. As it turns out, a p-sorter is a much more
expensive device than a sorting network, and its use should be avoided whenever possible. Besides,
it is not clear whether it is possible to replace the p-sorter with a pipelined sorting network in the
architecture of [18], while guaranteeing the same performance.
The main contribution of this work is to propose a simple sorting architecture whose main
feature is the pipelined use of a sorting network of fixed I/O size to sort an arbitrarily large
number N of elements. Specifically, we show that by using our design, N elements can be sorted in
log N
Our design consists of a sorting network of fixed I/O size p, a set of prandom-
access memory modules, and a control unit. The memory access patterns are regular: in one step,
elements from two rows of memory modules are supplied as input to the sorting network and/or the
output of the sorting network is written back into two memory rows. Our architecture is feasible for
VLSI implementation. We then show how to use an AT 2 -optimal sorting network of fixed I/O size
p to construct a similar architecture that sorts an arbitrary number N of elements in \Theta( N
log N
time. An important feature of both architectures is that no extra data memory space is required,
other than what is needed for storing the input.
The remainder of the paper is organized as follows. In Section 2 we discuss the details of
the proposed architecture. In Section 3 we show how to obtain row-merge schedules, a critical
ingredient for the efficiency of our design. Section 4 extends the results of Sections 2 and 3 by
showing how to use an AT 2 -optimal sorting network of fixed I/O size p to obtain a architecture to
log N
Finally, Section 5 offers concluding remarks and poses a
number of open problems.
2 The Architecture
A sorting network can be modeled as a directed graph whose nodes represent processing elements
and whose edges represent the links connecting the nodes, as illustrated in Figure 1. The processing
elements can be simple comparators or more complex processors capable of performing arithmetic
operations. A comparator has two inputs and two outputs and is used to perform a compare-
exchange operation. A comparator-based sorting network is a sorting network whose processing
elements are comparators. In the remainder of this work, we use the term sorting network to
refer exclusively to a comparator-based sorting network. Figure 1 and Figure 2 illustrate Batcher's
classic sorting networks, with I/O size 8. As illustrated in Figure 1, two types of comparators are
used. For a type 0 comparator, the smaller and larger of the two input numbers emerge, after
comparison, at the top and bottom output, respectively. A comparator of type 1 produces the
output in reverse order. Unless stated otherwise, we assume that when a sorting network of fixed
I/O size p is used to sort p elements, each of its comparators is used exactly once.
a
I
I
I
I
I
I
I
I
O
O
O
O
O
O
O
a
Figure

1: A bitonic sorting network of I/O size 8.
I
I
I
I
I
I
I
I
O
O
O
O
O
O
O
Figure

2: An odd-even merge sorting network of I/O size 8.
Referring to Figures 1 and 2, we say that a sorting network S is layered if each of its comparators
is assigned to one of the D(S) layers L k , 1 - k - D(S), as follows:
ffl Assign to layer L 1 the comparators whose inputs are outputs of no comparators in the network
and exclude them from further consideration;
ffl for every k, 2 - k - D(S), assign to layer L k the comparators whose inputs are outputs
of comparators in layers L i and layer L j , 1 - exclude them from further
consideration.
A simple inductive argument shows that for every k, 2 - k - D(S), every comparator in layer
k receives at least one input from a comparator in layer L k\Gamma1 . Therefore, in a layered sorting
network the longest paths from the network input to the comparators in layer L k must have the
same length.
We say that a sorting network S is pipelined if for every k, 2 - k - D(S), all paths from the network
input to the comparators in layer L k have the same length 1 . As an illustration, the bitonic sorting
network shown in Figure 1 is a pipelined network, whereas the odd-even merge sorting network of

Figure

2 is not. The intuition for this terminology is that a pipelined sorting network S of I/O size
p can be used to sort sets of p elements concurrently in a pipelined fashion. It is easy to confirm
that in a pipelined network S each layer contains exactly pcomparators. In this context, we shall
refer to layers as stages and denote them by S 1
Given a sorting network S, one can always introduce additional buffer nodes (latches), if nec-
essary, in such a way that the nodes of the resulting network - comparators and latches - can
be partitioned into stages S 1 Specifically, for every k, 1 - k - D(S), place all
the comparators in layer L k in S k . If one of the two inputs of a comparator c in layer L k is the
output of a comparator c 0 in layer L i with a sequence of latch nodes
l 0
on the edge from c 0 to c so that l 0
j is in stage S i+j . For each output of a comparator
c in layer k such that k ! D(S) that is also the output of the network, we add latch nodes
on the output edge. The reader should have no difficulty confirming that in the resulting network
all paths from the network input to the nodes in the same layer have the same length. Thus, this
transformation converts a non-pipelined network into a pipelined one. For example, after adding
latches to the odd-even merge sorting network of Figure 2, we obtain the network shown in Figure
3.
Our proposed architecture, that we call the Row-Merge Architecture, (RMA, for short) is illustrated
in Figure 4 for 8. The RMA involves the following components:
(i) A pipelined sorting network T of fixed I/O size p with inputs I 1 ; I and with outputs
(ii) pconstant-port memory modules pcollectively referred to as the data memory.
For every k, 1 - k - p, memory module M k is connected to inputs I k and I p
+k and to
outputs O k and O p
2 +k of the sorting network.
1 The length of a path is taken to be the number of edges on the path.
O
O
O
O
O
O
O

Figure

3: The odd-even merge sorting network with latches added.
O O O O O O O O
I I I I I I I I12 3
Control Unit
Sorting
Memory
Modules
Network T

Figure

4: The Row-Merge Architecture with
(iii) A control unit (CU) consisting of a control processor (CP) and of a control memory.
The words with the same local address in all memory modules are collectively referred to as a
memory row. The N input elements are stored, as evenly as possible, in d 2N
consecutive memory
rows. Dummy elements of value +1 are added, if necessary, to ensure that all memory modules
contain the same number of elements: these dummy elements will be removed after sorting. The
read/write operations are carried out in a single instruction (address) stream multiple data stream
fashion controlled by the CU. Specifically, the CU is responsible for generating memory access
addresses: in every step, the same address is broadcast to all memory modules which use it as
the local address for the current read or write operation. We assume that the address broadcast
operation takes constant time. The CU can disable memory read/write operations, as necessary,
by appropriately using a mask.
When operating in pipelined fashion, in a generic step i, p elements from two memory rows are
fed into the sorting network; at the end of step the sorted sequence of p elements
from these two rows emerges at the output ports of T and is written back into two memory rows.
This process is continued until all the input elements have been sorted. To simplify our analysis,
we assume that one memory cycle is sufficient for reading, writing, and for comparator operations.
This assumption is reasonable if each memory module has, say, two ports for reading and two
ports for writing. If each memory module has only one port for both reading and writing, the
performance degrades by a small constant factor.
Let (a; b) be an ordered pair of memory rows in data memory. In the process of sorting, the
elements in memory row a (resp. b) are read into the left (resp. right) half of the network input,
and the corresponding elements are sorted in non-decreasing order. Finally, the left (resp. right)
half of the resulting sorted sequence emerging at the network output is written back into data
memory to replace the original row a (resp. b). It is now clear why we refer to our design as the
Row-Merge Architecture.
In order to efficiently sort 2N
memory rows on the RMA, we wish to identify a finite sequence
MS =! (a of pairs of memory rows such that by following this sequence
the elements are sorted in row-major order. We call such a sequence MS a row-merge schedule or,
simply, a merge schedule. At this time, the reader may wonder about the power of the RMA. In
Theorem 1, we provide a partial answer to this question by establishing a lower bound on the time
required by any algorithm that sorts N elements using the RMA.
Theorem 1 Any algorithm that correctly sorts N elements on the RMA using a sorting network
of I/O size p must
log N
Proof. We ignore the time delay caused by the depth of the sorting network and, consequently, we
assume that the sorting network takes O(1) time to sort any group of p elements. This assumption
is reasonable, since it can only help up the algorithm. We show that even with this favorable
assumption, any sorting algorithm must take \Omega\Gamma N
log N
For this purpose, we only need to exhibit a particular sequence of N
memory rows for which
any algorithm operating in the RMA
log N
Consider an arbitrary sequence
real numbers stored in an array A[1:: 2N
such that for every
The 2N
memory rows are assumed to be such that for every
p , all the p
words in
memory row i are equal to a i .
Now consider an arbitrary merge schedule MS that correctly sorts the resulting 2N
memory
rows. From this MS we construct an algorithm B, in the comparison tree model, that sorts the
array A. The idea is that algorithm B simulates on A the actions of MS on the set of memory
rows. More precisely, when MS sorts memory rows i and j, algorithm B compares and, if necessary,
interchanges the entries A(i) and A(j).
Now assume that the merge schedule MS sorts the 2N
memory rows in o( N
log N
time. The
simulation just described implies that algorithm B sorts the array A in o( N
log N
this is impossible as the lower bound for sorting 2N
elements in the comparison tree model is
log N
This completes the proof of the theorem. 2
Generating Row-Merge Schedules
In order to sort N input elements correctly and efficiently on the RMA, we need to find a merge
schedule MS =! (a to guide the computation. The MS specifies, in left
to right order, the pairs of memory rows that will be supplied as input to the sorting network, in a
pipelined fashion. For example, the ordered pair (a supplied in the first time unit, followed
by the ordered pair (a in the second time unit, and so on. For reasons that will be discussed
later, we are interested in merge schedules that satisfy the following three conditions:
(1) The RMA must sort correctly, if a p-sorter is used instead of the sorting network, that is, for
sorting networks of depth one.
(2) A row number appears at most once in any subsequence (a
of MS.
(3) The length of MS should be as close as possible to \Omega\Gamma N
log N
p ), which is the time lower bound
for sorting on the RMA.
A p-sorter can be perceived as a sorting network T of I/O size p and depth D(T Therefore,
condition (1) is a necessary condition for correctly sorting N elements in general. For
if condition (2) is violated, the MS may not guide the pipelined operations to correctly sort the N
elements because of possible data dependencies. To see this, consider the pairs of memory rows
are updated. It is possible that an element that is
originally in row a i is duplicated in both rows b i and row b i+j , while an element that is originally
in row b i or row b i+j is lost. Condition (3) impacts the time performance.
We now present a general framework for generating row-merge schedules. The central idea of
our approach is motivated by the following well-known fact mentioned in [9] and in [12] (p. 241):
Proposition 1 For any parallel algorithm using only compare-exchange operations for sorting m
elements with m processors, there is a corresponding algorithm for sorting rm elements with m
processors, where every comparison in the first algorithm is replaced by a merge-sorting of two lists
of r elements in the second.
For later reference, we refer to Proposition 1 as the compare-exchange/merge-split principle.
Let S be a sorting network of I/O size
. Knuth [12] suggested representing S in the
way shown in Figure 5(b). Specifically, there are m horizontal lines, each labeled by an integer
i. The left and right endpoints of the line labeled i represent, respectively, the i-th input and the
i-th output of the network. A comparator, represented by a directed vertical segment originating
at line i and ending at line j, causes an interchange of its inputs, if necessary, so that the smaller
number appears on line i and the larger number appears on line j. We call this representation the
line representation of S.
Memory row 1
Memory row 2
Memory row 4
Memory row 3
Memory row 5
Memory row 6
Memory row 7
Memory row 8
(a)
(b)

Figure

5: Illustrating the correspondence between (a) memory address space and (b) line representation
of a network S. Here, S is the sorting network shown in Figure 1
Constructing the line representation of a sorting network S of I/O size m from the graph
representation of S is straightforward. We perceive a comparator as a 2 \Theta 2 switch of two states,
straight and cross. We assign an input value i to the network input I i , 1 - i - m, and set all
switches (comparators) to the straight state. Then, the m input values propagate through the
switches. The values j and k received by a switch define the corresponding vertical segment with
endpoints on lines j and k in the line representation of S. The type of the corresponding comparator
determines the direction of the vertical segment. Figure 6 illustrates this propagation process for
the network of Figure 1. A pair of integers and an arrow at the input of each comparator define
the directed vertical line segment in the line representation shown in Figure 5(b).
I
I
I
I
I
I
I
I
O
O
O
O
O
O
O

Figure

Illustrating the method of obtaining the line representation of the network in Figure 1
Assume that the N elements to sort are located in memory rows 1 through m. We generate a
merge schedule MS from the line representation and the layer partition of S by the following greedy
algorithm. Initially, the inputs to all comparators are unmarked. Let C 1 be an arbitrary FIFO (first-
in first-out) queue of comparators at level L 1 . We obtain a FIFO queue C i+1 of comparators in level
L i+1 as follows: Set C i+1 to empty. Scan the comparator queue C i in order and for each comparator
in C i , mark its two output edges. As soon as the two input edges of a comparator c are marked,
include c into layer C i+1 . At this point the reader will not fail to note that comparator c must,
indeed, belong to layer L i+1 . This process is continued, as described, until all C
have been constructed. Finally, concatenate the C j s to obtain a sequence C of comparators such
that C i precedes C i+1 .
ks C(S), be the sequence of comparators obtained from S using the
greedy algorithm just described. With each comparator c k j whose corresponding directed vertical
segment originates at line a j and ends at line b j in the line representation of S, we associate
the ordered pair (a MS =! (a be the resulting sequence of
ordered pairs corresponding to C. Consider the correspondence between the data memory and
the line representation of S such that the horizontal line i corresponds to memory row i. By the
compare-exchange/merge-split principle (Proposition 1), we know that the elements in the memory
can be sorted in row-major order if we merge the rows sequentially, following the merge schedule
MS.

Figure

5 illustrates the correspondence between a data memory of four modules, eight words
per module (i.e. and the line representation of the network in Figure 1. Applying the
greedy algorithm on S shown in Figure 1 as S, we obtain the following merge schedule:
In the bitonic sorting network of I/O size m, assuming m to be even, there are exactly mcomparators per layer. As will be shown shortly, if N ? pD(T ), any MS generated by the greedy
algorithm from the bitonic sorting network of I/O size
satisfies conditions (1) and (2)
above and, therefore, can be used to correctly sort N elements on the RMA. However, there exist
sorting networks that cannot be used to generate a merge schedule that satisfies condition (2) for
This fact restricts the applicability of the MS generating scheme. For example, if
no MS generated directly from the network featured in Figure 7 can satisfy condition
(2). To remedy this problem, we introduce the concept of augmenting sorting networks.L

Figure

7: Line representation of a variant of the bubble sort network.
Given an arbitrary sorting network S of I/O size m, the augmented sorting network S 00 of I/O
size m derived from S is obtained as follows:
ffl Transform S into a pipelined network S 0 by adding latches as described in Section 2;
ffl Group the latches in each layer of S 0 into pairs (in an arbitrary way) and replace each pair
of latches by "dummy" comparators
If m is odd, delete the remaining latch in each stage.
The network obtained at the end of this simple algorithm is the desired augmented sorting network
S 00 . Clearly, in each layer of S 00 there are exactly b m
comparators. To be distinguished from
real comparators, dummy comparators are represented by a node labeled d and by a vertical line
segment without an arrow, in the graph and line representation, respectively. For an illustration,
the augmented network of the odd-even sorting network shown in Figure 2 is given in Figure 8.
We will still use our greedy algorithm to generate an MS from an augmented network S 00 .
The comparator selection process is exactly as described above. However, the task of translating
a comparator sequence into the corresponding MS is slightly modified to accommodate dummy
comparators. When we translate the comparator sequence
ks ) into
MS =! (a
is a dummy comparator then the order of the two row numbers involved is arbitrary. When
we use an MS generated from an augmented network S 00 , the write operations in step i +D(T
are disabled if (a corresponds to a dummy comparator of S 00 . Note that this is possible since,
as specified in the Section 2, our architecture supports masked write operations.
Operating in this fashion, an MS generated from an augmented network S 00 clearly satisfies
condition (1) because of the compare-exchange/merge-split principle (Propositions 1). As we shall
prove in Theorem 2, the MS also satisfies condition (2). The length of the MS is the cost of the
sorting network using which the MS is generated. Both S and S 00 have the same depth, but S 00 has
an increased cost compared with S. We note that, at first, it would seem as though by using S 00
to derive an MS condition (3) will not be satisfied. However, all sorting networks S of I/O size m,
known to the authors, including the network. featured in Figure 7, have O(mD(S)) cost; therefore,
the cost of S 00 is within a constant factor of the cost of S.
To summarize our findings we now state and prove the following important result.
Theorem 2 Let S be any sorting network of I/O size 2N=p and let T be any sorting network of
I/O size p. If N ? pD(T ) then any merge schedule obtained from the augmented network of S by
the greedy algorithm can be used to correctly sort N elements on the Row-Merge Architecture with
T as the sorting device in O( N
Dummy comparators are introduced for convenience only. They amount to a "no-operation".
I
O
O
O
O
O
O
O
d
d
d
d

Figure

8: The augmented odd-even merge sorting network
Proof. We only need to show that if N ? pD(T ), any MS generated from the augmented network
S 00 of S satisfies condition (2). Let MS =! (a be an arbitrary merge
schedule corresponding to the comparator sequence
ks ) generated from S 00 by
the greedy algorithm.
Conceptually, we treat the network S 00 as a data-driven (i.e. data-flow) architecture: the processing
elements are precisely the comparators, whose activation is driven by data availability. We
say that a comparator c is ready for activation whenever its two inputs are available and it has not
yet been used. To prove the theorem, we need to show that for any j such that all comparators
preceding c k j have been used but c k j has not yet been used, all the comparators in the subsequence
are ready for activation.
Let jL i j denote the number of comparators in layer L i of similarly, let jC i j stand for the length
of the subsequence C i constructed from the comparators in L i by the greedy algorithm. Clearly,
c. Initially, there are exactly b N
c comparators, all in C 1 , ready for activation.
Consider a arbitrary j,
1, such that all comparators preceding c k j
have been used
and such that c k j
is ready for activation. Suppose that c k j
is the r-th comparator in C i . Then, the
number of comparators in C i that are ready for activation is, clearly, jL 1. Since each of the
first comparators of C i provides at most two inputs to comparators in layer L i+1 and since
each comparator of L i+1 receives at least one of its inputs from a comparator in layer L i , it follows
that at least the first r \Gamma 1 comparators in C i+1 are ready for activation.
Therefore, the total number of consecutive comparators starting from c k j in C is at least jL i j,
which is at least b N
remaining comparators in C starting from c k j
are ready for activation.
If b N
t such that t ? b N
c the input of comparator c ks does not depend
on the output of any of comparators c k t\GammaD(T )
in C. With this, we just proved
that this MS can be used as a merge schedule for network T . Note also that by our previous
discussion the time required to sort N elements is O(s), where s is the cost of S 00 , and it is bounded
above by O(mD(S)). This completes the proof of the theorem. 2
We note that Theorem 2 has the following important implications:
(a) Any sorting network T whose depth d(T ) satisfies N ? pD(T ) can be used to sort correctly
N elements in pipelined fashion.
(b) If N - p 2 , any sorting network of depth no larger than p can be used as T . Since the depth
of all practical sorting networks of I/O size p is smaller than p, any of these networks can be
used as T in the RMA. It is important to note that this implies that the performance of the
RMA is virtually independent of the sorting network T used as the sorting device.
(c) If N - p 2 , any row-merge schedule generated from the augmented network of any network
S by our greedy algorithm can be used to sort N elements correctly; in other words, the
correctness of any merge schedule is independent of the sorting network S used to generate
it.
(d) The time required for sorting N elements is proportional to D(S), the depth of S.
We can select T from a wide range of sorting networks, depending on their VLSI feasibility.
We also have a wide range of sorting networks to choose from for deriving merge schedules. We
know that the depth of both the bitonic and the odd-even merge sorting network of I/O size m
is O(log 2 m). Thus, using either of them as S to derive a merge schedule, N elements can be
sorted in O( N
log 2 N
time. It is well known that the depth of the AKS sorting network of I/O
size m is bounded by O(log m). Hence, using the AKS network as S, N elements can be sorted in
O( N
log N
Therefore, we take note of the following extension of Theorems 1 and 2.
Theorem 3 The Row-Merge Architecture that uses a sorting network of I/O size p and depth at
most p as the sorting device can sort N elements, N - p, in \Theta( N
log N
To the best of our knowledge, most of the known sorting networks, including the AKS network,
are defined recursively. The graph representations of recursively defined sorting networks can be
constructed in linear time. Given the graph representation of a sorting network S of I/O size 2N
we now estimate the time it takes the CU to generate an MS. The comparators in the first layer,
of S can be easily identified. Next, the nodes of S can be divided into D(S) layers as described
in Section 2. Clearly, this process takes O(C(S)) time. By scanning the nodes of S layer by layer,
latches can be added to convert S into a pipelined network S 0 in O( N
time. Further, by
employing a layer-by-layer scan of the nodes in S 0 , pairs of latches in each layer are combined
into dummy comparators to obtain the augmented network S 00 , and this process takes O( N
time. It is easy to see that the task of constructing the line representation of S 00 from the graph
representation of S 00 can also be carried out in O( N
time. Finally, the greedy algorithm
is performed on S 00 and this algorithm is essentially a Breath-First search, running in O( N
time. Hence, the total time of generating an MS from network S is bounded by O( N
It is interesting to note that, even if the MS schedule is available, the RMA needs O( N
time to complete the task of sorting N elements. Thus, the time it takes the CU to compute
an MS and the time needed by the network T to perform the sorting are perfectly balanced. In
other words, the time complexity claimed in Theorem 3 also holds if the computation required for
generating an MS is taken into account. It is very important to note that once available, the MS
can be used to sort many problem instances.
The working space requirement by the control memory is proportional to mD(S) words, each
of O(log N) bits. Rather remarkably, the RMA does not require extra data memory space other
than what is used for storing the input.
4 The Generalized Row-Merge Architecture
In a number of contexts, especially when the VLSI complexity of T is a concern, it is desirable to
use an AT 2 -optimal network as a parallel sorting device. The main goal of this section is to show
that it is possible to design a sorting architecture that uses an AT 2 -optimal sorting network as its
parallel sorting device. As it turns out, the time performance of the new design, that we call the
Generalized Row-Merge Architecture (GRMA, for short), is slightly better than that of the RMA
discussed in Section 2.
The GRMA uses a sorting network T of fixed I/O size p with inputs I 1 ; I outputs
. It has p constant-port data memory modules collectively referred
to as the data memory. For every k, 1 - k - p, memory module M k is connected to input I k and
to output O k . In one parallel read operation, one memory row is read and supplied as input to T ;
in one parallel write operation the output of T is written back into one memory row. Just like in
the RMA, the memory accesses and the operation of the sorting network T are controlled by the
control unit (CU). There are, however, three major differences between the GRMA and the RMA.
(a) The GRMA has p memory modules rather than pmemory modules.
(b) The sorting network can sort O(D(T memory rows in row-major order in O(D(T
(c) For simplicity, we assume that the GRMA operates in a different pipelining mode than the
RMA. Specifically, a group of r memory rows are fed into the network in r consecutive
time steps and, after sorting, the r rows are written back to memory in r consecutive time
steps. After that, another group of r memory rows is fed into the network, and so on. This
process is repeated until the elements in all groups of r memory rows are sorted. The value
r is proportional to the depth D(T ) of T . (We note here that by changing the control
mechanism, the GRMA can also operate in fully pipelined mode, i.e. the network T can be
fed continuously.)
We select for T Leighton's optimal sorting network [13] which is known to be AT 2 -optimal.
This network, which is a hardware implementation of the well known Columnsort algorithm, has
I/O size q
log q and depth c log q, where c is a constant greater than 1. Two designs were proposed in
[13]: one with a value of c significantly smaller than that of the other. Leighton's sorting network
sorts an array of size log q \Theta q
log q in row-major order in a pipelined fashion. Specifically, in each of
the first log q steps, q
log q
elements are fed into the network, and after c log q steps, these elements
emerge, sorted, at the output of the network in log q consecutive steps.
Let q be such that
log q . We partition the N
memory rows into
log q super-rows, each
containing log qconsecutive memory rows. That is, the i-th super-row consists of memory rows
log q+ 1 through i log q. The operation of the GRMA is partitioned into iterations, with two
super-rows being sorted in each iteration. Each iteration consists of two phases:
ffl a feeding phase during which two super-rows, contains log q memory rows, are fed continuously
into the sorting network, and
ffl a clearing phase, in which the elements in the sorting network are "drained" out.
Let (a; b) be an ordered pair of super-row numbers. The procedure Merge Two Super-rows(a; b)
whose details are given in Figure 9 performs the merge-split operation on the super-rows a and b.
We use a layered sorting network S of size
log q to obtain a merge schedule MS =!
be the list of comparators in
layer L i of S. We concatenate these lists to obtain a sequence C of comparators such that C i
precedes C i+1 . Let ks C(S), be the sequence of comparators obtained from
S. Based on C and the line representation of S, we obtain a merge schedule MS. Guided by MS,
the sorting process proceeds in non-overlapping iterations, each consisting of a call to procedure
Merge Two Super-rows(a; b) to perform a merge-split operation on two super-rows specified by the
in MS.
By the compare-exchange/merge-split principle, the GRMA sorts N elements correctly. Since
each iteration takes O(log q) time, the task of sorting N elements on the GRMA using this MS
procedure Merge Two Super-rows(a; b)
begin
feeding phase */
to log qdo
Read row (a\Gamma1) log q+ i and feed this row to the input of T
endfor
to log qdo
Read row (b\Gamma1) log q
and feed this row to the input of T
endfor
idling */
log q do no-op
clearing phase */
to log q
do
Write the output of T into row (a\Gamma1) log q+ i
endfor
to log q
do
Write the output of T into row (b\Gamma1) log q+ i
endfor

Figure

9: The procedure Merge Two Super-rows.
takes C(log qS) time. Using the layered AKS network as S, we obtain a valid MS of length
O( N
log q log N
log q ) that can be used to sort N elements on the GRMA takes O( N
log N
log q
O( N
log N
log p
time.
An argument similar to that used in the proof of Theorem 1 shows that every algorithm that
sorts N elements on the GRMA requires at
log N
To summarize our findings,
we state the following result.
Theorem 4 The Generalized Row-Merge Architecture that uses an AT 2 -optimal network of I/O
size p as the parallel sorting device sorts N elements, N - O(p log p), in \Theta( N
log N
Notice that in the case of the GRMA the computation of a merge schedule does not require
an augmented network. The length of the merge schedule is somewhat shorter because of using a
network S of smaller I/O size and depth, and without dummy comparators. Again, no extra data
memory is required other than what is used for storing the input.
5 Conclusions and Open Problems
The main motivation for this work was provided by the observation that, up to now, sorting
networks of fixed I/O size p have only been used to sort a set of p elements. Real-life applications,
however, require sorting arbitrarily large data sets. Rather surprisingly, the important problem of
using a fixed I/O size sorting network in such a context has not been addressed in the literature.
Our main contribution is to propose a simple sorting architecture whose main feature is the
pipelined use of a sorting network of fixed I/O size p for sorting an arbitrarily large data set of N
elements. A noteworthy feature of our design is that it does not require extra data memory space,
other than what is used to store the input. As it turns out, the time performance of our design,
that we call the Row-Merge Architecture (RMA) is virtually independent of the cost and depth of
the underlying sorting network. Specifically, we showed that by using the RMA N elements can
be sorted in \Theta( N
log N
memory access conflicts. In addition, we showed how to
use an AT 2 -optimal sorting network of fixed I/O size p to construct a similar architecture, termed
Generalized Row-Merge Architecture (GRMA) that sorts N elements in \Theta( N
log N
At this point, we do not know whether or not a better performance can be achieved by removing
the restriction on the rigid memory access scheme of the RMA, by allowing more flexible, yet regular,
memory access patterns. In such a case, the time lower bounds for both of the RMA and the GRMA
no longer hold. As the results of [6] indicate, N elements cannot be sorted in less
N log N
log p
time using any parallel sorting device of I/O size p. It is an interesting open question to close the
gap between this lower bound and the time performance offered by our designs.
The best performance of the designs proposed in this paper is proportional to the depth of the
AKS network, which is used to construct merge schedules. The constant associated with the depth
complexity of the AKS network is too large to be considered practical. However, our results reveal
the potential of row-merge based simple sorting architectures.
Along this line of thought, a long-standing open problem is to obtain a realistic sorting network
of logarithmic depth. It is equally important to discover a network of depth c log m log log m, where
m is the network I/O size and c is a small constant. Such networks are useful for deriving practically
short merge schedules.



--R

Sorting in c log n parallel steps
Parallel Sorting Algorithms
Parallel Computation

On bitonic sorting networks
Sorting p objects with a k-sorter
A taxonomy of parallel sorting
A minimum area VLSI network for O(log n) time sorting
Optimal sorting algorithms for parallel computers
Optimal VLSI circuits for sorting
An optimal sorting algorithm on reconfigurable mesh
The Art of Computer Programming
Tight bounds on the complexity of parallel sorting
Sorting in O(1) time on a reconfigurable mesh of size p
Parallel permutation and sorting algorithms and a new generalized sorting network
Sorting p numbers on p
A new deterministic sampling scheme with applications to broadcast efficient sorting on the reconfigurable mesh
Sorting N items using a p-sorter in optimal time
Current progress on efficient sorting networks
Constructing sorting networks from k-sorters
Improved sorting networks with O(log N) depth
Parallel sorting: A bibliography ACM SIGACT News
A bibliography of parallel sorting
The VLSI complexity of sorting
A parallel sorting scheme whose basic operation sorts n elements
--TR

--CTR
Stephan Olariu , Cristina Pinotti , Si Qing Zheng, An Optimal Hardware-Algorithm for Sorting Using a Fixed-Size Parallel Sorting Device, IEEE Transactions on Computers, v.49 n.12, p.1310-1324, December 2000
Giuseppe Campobello , Marco Russo, A scalable VLSI speed/area tunable sorting network, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.10, p.589-602, October 2006
Classifying Matrices Separating Rows and Columns, IEEE Transactions on Parallel and Distributed Systems, v.15 n.7, p.654-665, July 2004
Shun-Wen Cheng, Arbitrary long digit integer sorter HW/SW co-design, Proceedings of the conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
pipelined processing;sorting networks;computer architecture;parallel processing;sorting