An Optimal Hardware-Algorithm for Sorting Using a Fixed-Size Parallel Sorting Device.
AbstractWe present a hardware-algorithm for sorting $N$ elements using either a p-sorter or a sorting network of fixed I/O size $p$ while strictly enforcing conflict-free memory accesses. To the best of our knowledge, this is the first realistic design that achieves optimal time performance, running in $\Theta ( {\frac{N \log N}{p \log p}})$ time for all ranges of $N$. Our result completely resolves the problem of designing an implementable, time-optimal algorithm for sorting $N$ elements using a p-sorter. More importantly, however, our result shows that, in order to achieve optimal time performance, all that is needed is a sorting network of depth $O(\log^2 p)$ such as, for example, Batcher's classic bitonic sorting network.
Introduction
Recent advances in VLSI have made it possible to implement algorithm-structured chips as building blocks
for high-performance computing systems. Since sorting is one of the most fundamental computing problems,
it makes sense to endow general-purpose computer systems with a special-purpose parallel sorting device,
invoked whenever its services are needed.
In this article, we address the problem of sorting N elements using a sorting device of I/O size p, where N
is arbitrary and p is fixed. The sorting device used is either a p-sorter or a sorting network of fixed I/O size
p. We assume that the input as well as the partial results reside in several constant-port memory modules.
In addition to achieving time-optimality, it is crucial that we sort without memory access conflicts.
In real-life applications, the number N of elements to be sorted is much larger than the fixed size p that
a sorting device can accommodate. In such a situation, the sorting device must be used repeatedly in order
to sort the input. The following natural question arises: "How should one schedule memory accesses and
the calls to the sorting device in order to achieve the best possible sorting performance?" Clearly, if this
question does not find an appropriate answer, the power of the sorting device will not be fully utilized.
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 p \Theta p reconfigurable
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, University of Texas at Dallas, Richardson, Richardson,
mesh [3, 7, 8]. Beigel and Gill [2] showed that the task of sorting N elements, N - p,
N log N
log p
calls to a p-sorter and presented an algorithm that achieves this bound. However, their algorithm assumes
that the p inputs to the p-sorter can be fetched in unit time, irrespective of their location in memory. Since,
in general, the address patterns of the operands of p-sorter operations are irregular, it appears that the
algorithm of [2] cannot realistically achieve the time complexity of \Theta
N log N
log p
, unless one can solve in
constant time the addressing problem inherent in accessing the p inputs to the p-sorter and in scattering the
output back into memory. In spite of this, the result of [2] poses an interesting open problem, namely that
of designing an implementable \Theta
N log N
log p
time sorting algorithm that uses a p-sorter.
Consider an algorithm A that sorts N elements using a p-sorter in O(f(N; p)) time. It is not clear
that algorithm A also sorts N elements using a sorting network T of I/O size p in O(f(N; p)) time. The
main reason is that the task of sorting p elements using the network T requires O(D(T
proportional to the depth D(T ), which is the maximum number of nodes on a path from an input to an
output, of the network. Thus, if each p-sorter operation is replaced naively by an individual application of
T , the time required for sorting becomes O(D(T ) \Delta f(N; p)). To eliminate this O(D(T )) slowdown factor, the
network must be used in a pipelined fashion. In turn, pipelining requires that sufficient parallelism in the
p-sorter operations be identified and exploited. Recently, Olariu, Pinotti and Zheng [9] introduced a simple
but restrictive design - the row merge model - and showed that in this model N elements can be sorted in
\Theta
log N
time using either a p-sorter or with a sorting network of I/O size p.
To achieve better sorting performance, a new algorithm-structured architecture must be designed. This
involves devising a sorting algorithm suitable for hardware implementation and, at the same time, an architecture
on which the algorithm can be executed directly. Such an algorithm-architecture combination
is commonly referred to as a hardware-algorithm. The major contribution of this article is to present the
first realistic hardware-algorithm design for sorting an arbitrary number of input elements using a fixed-size
sorting device in optimal time, while strictly enforcing conflict-free memory accesses. We introduce a
parallel sorting architecture specially designed for implementing a carefully designed algorithm. The components
of this architecture include a parallel sorting device, a set of random-access memory modules, a set of
conventional registers, and a control unit. This architecture is very simple and feasible for VLSI realization.
We show that in our architectural model N elements can be sorted in \Theta
N log N
log p
time using either a
p-sorter or a sorting network of fixed I/O size p and depth O(log 2 p). In conjunction with the theoretical work
of [2], our result completely resolves the problem of designing an implementable, time optimal, algorithm for
sorting N elements using a p-sorter. More importantly, however, our result shows that in order to achieve
optimal sorting performance a p-sorter is not really necessary: all that is needed is a sorting network of depth
O(log 2 p) such as, for example, Batcher's classic bitonic sorting network. As we see it, this is exceedingly
important since any known implementation of a p-sorter requires powerful processing elements, whereas
Batcher's bitonic sort network uses simple comparators.
Architectural Assumptions
In this section we describe the architectural framework within which we specify our optimal sorting algorithm
using a fixed-size sorting device. We consider that a sequential sorting algorithm is adequate for the case
. Consequently, from now on, we assume that
This assumption implies that just for addressing purposes we need at least 2 log p bits. 1 For the reader's
convenience, Figure 1 depicts our design for 9. To keep the figure simple, control signal lines are not
shown. The basic architectural assumptions of our sorting model include:
R
R R R R R R R R
Memory
Modules
AR AR AR AR AR AR AR AR AR
Sorting Device
Control
Unit

Figure

1: The proposed architecture for
(i) A data memory organized into p independent, constant-port, memory modules Each
word is assumed to have a length of w bits, with w - 2 log p. We assume that the N input elements
are distributed evenly, but arbitrarily, among the p memory modules. The words having the same
address in all memory modules are referred to as a memory row. Each memory module M i is randomly
addressed by an address register AR i , associated with an adder. Register AR i can be loaded with a
word read from memory module M i or by a row address broadcast from the CU (see below).
(ii) A set of data registers, R i , (1 - i - p), each capable of storing a (w We refer to
the word stored in register R i as a composed word, since it consists of three fields:
ffl an element field of w bits for storing an element,
ffl a long auxiliary field of log p bits, and
ffl a short auxiliary field of 0:5 log p bits.
1 In the remainder of this article all logarithms are assumed to be base 2.
These fields are arranged such that the element field is to the left of the long auxiliary field, which is to
the left of the short auxiliary field. Each field of register R i can be loaded independently from memory
module M i , from the i-th output of the sorting device, or by a broadcast from the CU. The output of
register R i is connected to the i-th input of the sorting device, to the CU, and to memory module M i .
We assume that:
ffl In constant time, the p elements in the data registers can be loaded into the address registers or
can be stored into the p modules addressed by the address registers.
ffl The bits of any field of register R i , (1 - i - p), can be set/reset to all 0's in constant time.
ffl All the fields of data register R i , (1 - i - p), can be compared with a particular value, and each
of the individual fields can be set to a special value depending on the outcome of the comparison.
Moreover, this parallel compare-and-set operation takes constant time.
(iii) A sorting device of fixed I/O size p, in the form of a p-sorter or of a sorting network of depth O(log 2 p).
We assume that the sorting device provides data paths of width w+ 1:5 log p bits from its input to its
output. The sorting device can be used to sort composed words on any combination of their element or
auxiliary fields. In case a sorting network is used as the sorting device, it is assumed that the sorting
network can operate in pipelined fashion.
(iv) A control unit (CU, for short), consisting of a control processor capable of performing simple arithmetic
and logic operations and of a control memory used to store the control program as well as the control
data. The CU generates control signals for the sorting device, for the registers, and for memory accesses.
The CU can broadcast an address or an element to all memory modules and/or to the data registers,
and can read an element from any data register. We assume that these operations take constant time.
Described above are minimum hardware requirements for our architectural model. In case a sorting
network is used as the sorting device, one can use a "half-pipelining" scheme: the input to the network is
provided in groups of D rows. The next group is supplied only after the output of the previous group is
obtained. D is the depth of the sorting network. For the sorting network to operate at full capacity, one may
add an additional set of address (resp. data) registers. One set of address (resp. data) registers is used for
read operations, while the order set is used for write operations; both operations are performed concurrently.
Let us now estimate the VLSI area that our design uses for hardware other than data memory, the sorting
device and the CU under the word model, i.e. assuming that the word length w is a constant. We exclude
the area taken by the CU: this is because in a high-performance computer system, one of the processors can
be assigned the task of controlling the parallel sorting subsystem. Clearly, the extra area is only that used
for the address and the data registers, and this amounts to O(p) - which does not exceed the VLSI area of
any implementation of a p-sorter or of a sorting network of I/O size p.
We do not include the VLSI area for running the data memory address bus, which has a width of log N
bits, and the control signal lines to data memory and to the sorting device, since they are needed for any
architecture involving a data memory and a sorting device. It should be pointed out that for any architecture
that has p memory modules involving a total of N - p 2 words, the control circuitry itself requires at least
\Omega\Gamma0/1 flog p; log N
area. Since the operations performed by the control processor are
simple, we can assume that it takes constant area. The length of the control memory words is at least log N
which is the length of data memory addresses. As will become apparent, our algorithms require O( N
of data memory, and consequently, the control memory words have length O(log N
). The control program
is very simple and takes constant memory. However, O( N
are used for control information,
which can be stored in data memory.
3 An Extended Columnsort Algorithm
In this section, we present an extension of the well known Columnsort algorithm [5]. This extended Column-
algorithm will be implemented in our architectural model and will be invoked repeatedly when sorting
a large number of elements. There are two known versions of Columnsort [5, 6]: one involves eight steps, the
other seven. We provide an extension of the 8-step Columnsort, because the 7-step version does not map
well to our architecture.
Columnsort was designed to sort, in column-major order, a matrix of r rows and s columns. The
"classic" Columnsort contains 8 steps. The odd-numbered steps involve sorting each of the columns of the
matrix independently. The even-numbered steps permute the elements of the matrix in various ways. The
permutation of Step 2 picks up the elements in column-major order and lays them down in row-major order.
The permutation of Step 4 is just the reverse of that in Step 2. The permutation of Step 6 amounts to a b rc
shift of the elements in each column. The permutation of Step 8 is the reverse of the permutation in Step 6.
The 8-step Columnsort works under the assumption that r - In [5], Leighton poses as an open
problem to extend the range of applicability of Columnsort without changing the algorithm "drastically". We
provide such an extension. We show that one additional sorting step is necessary and sufficient to complete
the sorting in case r - s(s \Gamma 1). Our extension can be seen as trading one additional sorting step for a larger
range of applicability of the algorithm.

Figure

2: Step by step application of the extended Columnsort algorithm. The first eight steps correspond to
the classic 8-step Columnsort.

Figure

2 shows a matrix of r rows and s columns with which the condition r -
is not satisfied. The first eight steps of this example correspond to the 8-step Columnsort algorithm which
does not produce a sorted matrix. By adding one more step, Step 9, in which the elements in each column
are sorted, we obtain an extended Columnsort algorithm. We assume a matrix M of r rows and s columns,
numbered from 0 to r \Gamma 1 and from 0 to s \Gamma 1, respectively. Our arguments rely, in part, on the following
well-known gem of computer science mentioned by Knuth [4].
Proposition 1 Let M be a matrix whose rows are sorted. After sorting the columns, the rows remain sorted.
The following result was proved in [5].
Lemma 1 If some element x ends up in position M [i; j] at the end of Step 3, then x has rank at least
The following result was mentioned without proof in [5].
Lemma 2 If element x ends up in position M [i; j] at the end of Step 3, then its rank is at most si
Proof. We are interested in determining a lower bound on the number of elements known to be larger
than or equal to x. For this purpose, we note that since at the end of Step 3, element x was in position
are known to be larger than of equal to x. Among these, at most s are
known to be smaller than of equal to s \Gamma j elements in their columns at the end of Step 1. The remaining
must be smaller than or equal to s other elements in their column at the end of Step 1.
Consequently, x is known to be smaller than or equal to at least
rs
elements of M . It follows that the rank of x is at most si + sj, as claimed. 2
For later reference, we now choose r such that
Lemma 3 If some element x ends up in column c at the end of Step 4, then the correct position of x in the
sorted matrix is in one of the pairs of columns 1).
Proof. Consider, again, a generic element x that ended up in position M (i; j) at the end of Step 3. The
permutation specific to Step 4 guarantees that x will be moved, in Step 4, to a position that corresponds, in
the sorted matrix, to the element of rank si + j. In general, this is not the correct position of x. However,
as we shall prove, x is "close" to its correct position in the following sense: if x is in column c at the end of
Step 4, then in the sorted matrix x must be in one of the pairs of columns 1).
Recall that by virtue of Lemmas 1 and 2, combined, x has rank no smaller than si
no larger than si sj. Moreover, simple algebraic manipulations show that
Now consider the elements y and z of ranks si respectively. The number N (y; z)
of elements of the matrix M lying between y and z, in sorted order, is:
and so, by (2), we have
Observe that equation (4) implies that y and z must lie in adjacent columns of the sorted matrix. As we
saw, at the end of Step 4, x lies in the position corresponding to the element of rank is in the sorted
matrix. confirms that x lies somewhere between y and z. Assume that x lies in column
c at the end of Step 4. Thus, the correct position of x is in one of the columns c \Gamma 1 or c in case z is in the
same column as x, and in one of the columns c or c y is in the same column as x. 2
Lemma 4 The rows of M are sorted at the end of Step 4.
Proof. Consider an arbitrary column k, (0 - k - s \Gamma 1), at the end of Step 3. The permutation specified in
Step 4 guarantees that the first r
s elements in column k will appear in positions k; k+s; k+2s;
column 0; the next group of r
s elements will appear in positions k; k+s; k+2s;
on. Since the columns were sorted at the end of Step 3, it follows that all the rows k; k+s;
of M are sorted at the end of Step 4. Since k was arbitrary, the conclusion follows. 2
Lemma 5 If some element x is in the bottom half of column c at the end of Step 5, then its correct position
in the sorted matrix is in one of the columns c or c + 1.
Proof. By Lemma 3, we know that the correct position of x is in one of the pairs of columns
or 1). Thus, to prove the claim we only need to show that x cannot be in column c \Gamma 1. For this
purpose, we begin by observing that by Proposition 1 and by Lemma 4, combined, the rows and columns
are sorted at the end of Step 5. Now, suppose that element x ends up in row t, t - b rc, at the end of Step
5. If x belongs to column c \Gamma 1 in the sorted matrix, then all the elements of the matrix in columns
and c belonging to rows 0; must belong to column c \Gamma 1 or below. By Lemma 3, all elements that
are already in columns 0; must belong to columns 0; in the sorted matrix. Thus, at
least additional elements must belong to column c \Gamma 1 or below, a contradiction. 2
In a perfectly similar way one can prove the following result.
Lemma 6 If some element is in the top half of column c at the end of Step 5, then its correct position in
the sorted matrix is in one of the columns c \Gamma 1 or c.
Now, suppose that we find ourselves at the end of Step 8 of the 8-step Columnsort.
Lemma 7 Every item x that is in column c at the end of Step 8 must be in column c in the sorted matrix.
Proof. We begin by showing that
no element in column c can be in column
We proceed by induction on c. The basis is trivial: no element in column 0 can lie in the column to its left.
Assume that (5) is true for all columns less than c. In other words, no element that ends up in one of the
columns at the end of Step 8, can lie in the column to its left. We only need to prove that the
statement also holds for column c. To see that this must be the case, consider first an element u that lies
in the bottom half of column c at the end of Step 8. At the end of Step 5, u must have been either in the
bottom half of column c or in the top half of column c + 1. If u belonged to the bottom half of column c
then, by Lemma 6, it must belong to columns c or c + 1 in the sorted matrix. If u belonged to the top half
of column c must belong to columns c or c + 1 in the sorted matrix. Therefore, in
either case, u cannot belong to column c \Gamma 1.
Next, consider an element v that lies in the top half of column c at the end of Step 8. If v belonged to
all the elements in the bottom half of column c \Gamma 1 as well as the elements occurring above
v in column c must belong to column c \Gamma 1. By the induction hypothesis, no element that lies in column
at the end of Step 8 can lie in column c \Gamma 2. By Lemmas 5 and 6 combined, no element that lies in the
top half of column c \Gamma 1 can belong to column c. But now, we have reached a contradiction: column
must contain more than r elements. Thus, (5) must hold.
What we just proved is that no element in a column can belong to the column to its left. A symmetric
argument shows that no element belongs to the column immediately to its right, completing the proof. 2
By Lemma 7, one more sorting step completes the task. Thus, we have obtained a 9-step Columnsort
that trades an additional sorting step for a larger range of r versus s.
Theorem 1 The extended 9-step Columnsort algorithm correctly sorts an r \Theta s matrix such that r - s(s \Gamma 1).
4 The Basic Algorithm
In this section we show how to sort, in row-major order, m,
using our architectural
model while enforcing conflict-free memory accesses. The resulting algorithm, referred to as the basic
algorithm, will turn out to be the first stepping stone in the design of our time-optimal sorting algorithm.
The basic algorithm is an implementation of the extended Columnsort discussed in Section 3 with
Our presentation will focus on the efficient use of a generic sorting device of I/O size p. With this in
mind, we shall keep track of the following two parameters that will become key ingredients in evaluating the
running time of the algorithm:
ffl the number of calls to the sorting device, and
ffl the amount of time required by all the data movement tasks that do not involve sorting.
Assume that we have to sort, in row-major order, the elements in
memory rows. The case
2 is perfectly similar. We assume, without loss of generality, that the input is placed, in some
order, in memory rows a
for some integer a - 0. The sorted elements will be placed in
memory rows b
2 such that the ranges [a
do not overlap.
Step 1: Sort all the rows independently.
This step consists of the following loop:
do
read the i-th memory row and sort it in non-decreasing order using the sorting device;
be the resulting sorted sequence;
for all do in parallel
store x j in the i-th word of memory module M j
endfor
endfor
2 calls to the sorting device and O(p 1
data movement not involving sorting.
Step 2: Permuting rows.
The permutation specific to Step 2 of Columnsort prescribes picking up the elements in each memory row
and laying them down column by column. For an illustration, consider the case with the initial
element distribution featured in the following matrix:
At the end of Step 2, the permuted matrix reads:
A careful examination of the permuted matrix reveals that consecutive elements in the same memory row
will end up in the same memory module (e.g. elements 1, 2, 3 will occur in memory module M 1 ). Therefore,
in order to achieve the desired permutation without memory-access conflicts, one has to devise a different
way of picking up the elements in various memory rows. For this purpose, we find it convenient to view
each element x stored in a memory module as an ordered triple hx; row(x); module(x)i where row(x) and
module(x) stand for the identity of the memory row and of the memory module, respectively, containing
x. Further, we let row(x)jmodule(x) denote the binary number obtained by concatenating the binary
representations of row(x) and module(x). The details are spelled out in the following procedure.
procedure
begin
for all do in parallel
read the
-th word of memory module M j
endfor
using the sorting device, sort the p elements in non-decreasing order of row(x)jmodule(x);
be the resulting sorted sequence;
for all do in parallel
store x j in the
-th word of memory module M j
endfor
endfor
Clearly, this procedure involves p 1
iterations. In each iteration, p words are read, one from each memory
module, sorted, and then written back into memory, one word per module, with no read and write memory
access conflicts. It would seem as though each memory module requires an arithmetic unit to compute
the address of the word to be accessed in each iteration. In fact, as we now point out, such arithmetic
capabilities are not required. Specifically, we can use p 1
memory rows to store "offsets" used for memory
access operations. For the above example, the offsets are
At the beginning of Step 2 all the address registers contain a + 1. In the first iteration, the entries in the
first row of the offset matrix are added to the contents of the address registers, guaranteeing that the correct
word in each memory module is being accessed. As an illustration, referring to (7), we note that the offsets
in the first row indicate that the words involved in the read operation will be found at address a
memory module M 1 , address a memory
module M 3 , and so on.
The key observation for understanding what happens in all the iterations is that in any column of the
offset matrix (7), once the entry in the first row is available, the subsequent elements in the same column
can be generated by modulo
2 arithmetic. In our architecture, this computation can be performed by the
adder associated with each address register. In turn, this observation implies that, in fact, the offset matrix
need not be stored at all, as its entries can be generated on the fly.
Yet another important point to note is that each ordered triple hx; row(x); module(x)i is a composed
word with three fields and that the composed words are sorted using the combination of two fields, namely,
row(x) and module(x). Clearly, module(x) has log p bits, but it seems that in order to represent row(x)
we need log N
bits. Actually, we can replace row(x) with the address offset contained in the offset matrix
discussed above. Since the entries in that matrix are integers no larger than p 1
logp bits are sufficient.
Therefore, the concatenation row(x)jmodule(x) involves 1:5 log p bits.
From the above discussion it is clear that Step 2 requires p 1
2 calls to the sorting device and that the time
spent on data movement operations not involving sorting is bounded by O(p 1
Step 3: Same as Step 1.
Step 4: The permutation of Step 2 is performed in reverse; the permuted set of words are stored in rows
a
.
Step 5: Same as Step 1.
Step Shifting rows.
We shall permute the elements slightly differently from the way specified by Columnsort. However, it is easy
to verify that the elements supposed to end up in a given row, indeed end up in the desired row. Since Step
7 sorts the rows, the order in which the elements are placed in the row in Step 6 is immaterial.
The permutation of Step 6 is best illustrated by considering a particular example. Specifically, the
permutation specified by Step 6 of Columnsort involving the three rows shown in (6) is:
Our permutation is a bit different:
Assume that the p 1
consecutive input rows are stored in memory starting from memory row a + 1. In
addition, we assume that memory row a is available to us. Some of its contents are immaterial and will
be denoted by "?"s. The motivation is anchored in the observation that in Step 7 we do not have to sort
memory rows a and a
the elements in these rows will be sorted in Step 9. Consequently, the only rows
that have to be sorted in Step 7 are rows a
1. The details follow.
procedure ROW SHIFT
begin
for all
\Sigma p\Upsilon
, do in parallel
read the i-th word of memory module M j and
store it in the (i \Gamma 1)-th word of memory module M j
endfor
endfor
It is important to note that, in our implementation, Step 6 does not involve sorting. However, O(p 1
time is spent on data movement operations that do not involve sorting.
Step 7: Same as Step 1.
Step 8: This is simply the reverse of the data movement in Step 6.
Step 9: Same as Step 1.
To summarize, we have proved the following result.
Theorem 2 A set of p 3
elements stored in p 1
memory rows can be sorted, in row-major order, without
memory-access conflicts, in at most 7p 1
2 calls to a sorting device of I/O size p and in O(p 1
data
movement not involving sorting.
In essentially the same way one can prove the following companion result to Theorem 2.
Theorem 3 The task of sorting, in row-major order, a set of mp elements stored in m,
memory rows can be performed, without memory-access conflicts, in at most 7m calls to a sorting device of
I/O size p and in O(m) time for data movement operations not involving sorting.
In the remainder of this section we present an important application of the basic algorithm. Suppose
that we wish to merge two sorted sequences an and Our
algorithm for merging A and B relies on the following technical result.
Lemma 8 Assume that a d n 2 e - b b n 2 c+1 and let be the sequence obtained by merging
e and a d n
an . Then, no element in the sequence
strictly larger than any element in the sequence
Proof. We begin by showing that no a i , (1 - i - d ne), is strictly larger than any element in E. The
assumption that a d n 2 e - b b n 2 c+1 guarantees that if the claim is false, then some element a i ,
strictly larger than some element c k ,
To evaluate the position of the element c k in the sorted sequence C, observe that all the b nc elements
in C that come from A are known to be larger than or equal to a i and, therefore, strictly larger than c k .
Consequently, if n is even, then b nc elements in C are larger than c k , implying that k - b nc, a contradiction.
On the other hand, if n is odd, then d ne = b nc+1, and, by assumption, b d n
2 e is larger than a i and, therefore,
strictly larger than c k . In this case, at least d ne elements in C are strictly larger than c k . It follows that
contradicting that c k belongs to E.
Next, we claim that no c i , larger than any element in E. Since C is sorted, if the
statement is false, then c i ? b k for some k, (k - b nc+1). Notice that all elements of C that come from B are
smaller than or equal to b k and, therefore, strictly smaller than c i . It follows that contradicting
that c i belongs to D. This completes the proof of the lemma. 2
A mirror argument proves the following companion result to Lemma 8.
Lemma 9 Assume that a d n be the sequence obtained by merging
no element in the sequence D
2 c is strictly larger than any element in the sequence
It is worth noting that Lemmas 8 and 9, combined, show that given two sorted sequences, each of size
n, the task of merging them can be handled as follows: we begin by splitting the two sequences into two
sequences of size n each, such that no element in the first one is strictly larger than any element in the
second one. Once this "separation" is available, all that remains to be done is to sort the two sequences
independently. The noteworthy feature of this approach is that it fits extremely well our architecture.
2 and consider a sorted sequence stored in m memory rows
stored in m memory rows
1. The goal is to merge these two sequences and to store the resulting sorted
sequence in memory rows r A ; r A 1. The details follow.
procedure MERGE TWO GROUPS
begin
if a d mp
use the basic algorithm to sort b 1
non-increasing
order as c mp - c store the result in memory rows r
else
use the basic algorithm to sort a 1 ; a
non-increasing
order as c mp - c store the result in memory rows r
do
copy memory row r row r A
copy memory row r A +m \Gamma i into memory row r B
endfor
if m is odd then
copy the leftmost d pe elements in row r
into the leftmost d pe positions of row r A
copy the rightmost b pc elements in row r A
into the rightmost b pc positions of row r
endif
endif
if m is odd then
copy the leftmost d pe elements in memory row r C
into the leftmost d pe positions of row r
copy the rightmost b pc elements in row r C
into the rightmost b pc positions of row r A
endif
do
copy memory row r C
copy memory row r C
endfor
use the basic algorithm to sort memory rows r A ; r A non-decreasing
use the basic algorithm to sort memory rows r non-decreasing order
It is obvious that procedure MERGE TWO GROUPS can be implemented directly in our architectural
model. One point is worth discussing, however. Specifically, the task of sorting a sequence in non-increasing
order can be performed in our architecture as follows. The signs of all the elements to be sorted are flipped
and the resulting sequence is then sorted in non-decreasing order. Finally, the signs are flipped back to their
original value. The correctness of the procedure follows from Lemmas 8 and 9. Moreover, the procedure
requires three calls to the basic algorithm.
Consider the task of sorting a collection of 2mp memory rows, with m as above. Having partitioned the
input into two subgroups of m consecutive memory rows each, we use the basic algorithm to sort each group.
Once this is done, we complete the sorting using procedure MERGE TWO GROUPS. Thus, we have the
following result.
Theorem 4 The task of sorting 2mp,
2 , elements stored in 2m memory rows can be performed
in five calls to the basic algorithm and O(m) time for data movement operations not involving sorting. 2
5 An Efficient Multiway Merge Algorithm
Consider a collection A =! A 1 ; A
sequences, each of size p i
We assume that A is stored, top-down, in the order A 1 ; A
consecutive memory
rows. The multiway merge problem is to sort these sequences in row-major order. The goal of this section is
to propose an efficient algorithm MULTIWAY MERGE for the multiway merge problem, and to show how
it can be implemented on our architecture.
procedure MULTIWAY MERGE(A;m; i);
each of size p i
Output: the resulting sorted sequence stored in row-major order in mp i\Gamma2
contiguous memory rows. g
Step 1. Select a sample S of size mp i\Gamma2
2 from A by retaining every p-th element in each
sequence A j , (1 - j - m), and move S to its own dmp i\Gamma4
discussed below;
Step 2.
by one call to the sorting device
else if
by one call to the basic algorithm
else
frecursively multiway merge Sg
endif
(i\Gamma2)=2 be the sorted version of
Step 3. Partition A into p i\Gamma2
each containing at most 2mp elements,
as discussed below, and move the elements of A to their buckets without memory access conflicts;
Step 4. Sort all the buckets individually using the basic algorithm and procedure MERGE TWO GROUPS;
Step 5. Coalesce the sorted buckets into the desired sorted sequence.
2 Notice that if the sample S will be stored in one memory row.
The remainder of this section is devoted to a detailed implementation of this procedure on our architecture

5.1 Implementing Step 1 and Step 2
For convenience, we view A as a matrix of size mp i\Gamma2
2 \Theta p, with the t-th element of memory row j being
denoted by A[j; t]. The element A[j; p] is termed the leader of memory row j.
The goal of Step 1 is to extract a sample S of A by retaining the leader s of every memory row in A,
along with the identity k of the subsequence A k to which the leader belongs. In this context, k is referred to
as the sequence index of s. Two disjoint groups of dmp i\Gamma4
consecutive memory rows each are set aside to
store the sample S and the corresponding set I of sequence indices. In the remainder of this subsection, we
view the memory rows allocated to S and I as two matrices of size dmp i\Gamma4
p. The intention is that at the
end of Step 1, S[x; y] and I[x; y] store the y)-th leader of A and its sequence index, respectively.
To see how Step 1 can be implemented without memory access conflicts, notice that in each memory row
the leader to be extracted is stored in memory module M p . For a generic memory row j, the CU interchanges
temporarily the elements A[j; p] and A[j; d(j)], where p. (This interchange will be
undone at the end of Step 1). Next, dmp i\Gamma4
parallel read operations are performed, each followed by two
parallel write operations. The j-th parallel read operation picks up the k)-th word of memory
module M k , (1 - k - p), and these p elements are stored in the j-th memory row allocated to S. The second
parallel write operation stores the sequence indices of these p elements in the j-th memory row allocated to
I. Thus, Step 1 can be implemented in O(mp i\Gamma2
data movement and no calls to the sorting device.
The sampling process continues, recursively, until a level is reached where procedure MULTIWAY MERGE
is invoked with either which case the corresponding sample set is stored in one memory row and
will be sorted in one call to the sorting device, or with 4, in which case the sample set is stored in m
memory rows, and will be sorted in one call to the basic algorithm. Since the operation of sorting one row
is direct, we only discuss the way the basic algorithm operates in this context.
Conceptually, the process of sorting the samples benefits from being viewed as one of sorting the concatenation
sjk, where s is a sample element and k its sequence index. Recall that, as described in Section
2, our design assumes that the sorting device provides data paths of size w + 1:5 log p from its inputs to
its outputs. This implies that Steps 1, 3, 5, 7, and 9 of the extended Columnsort can be executed directly.
To sort a row r of S and the corresponding row r of I, the CU loads, in two parallel read operations, the
element field and the short auxiliary field of data register R j , (1 - j - p), with S[r; j] and I[r; j], and the
long auxiliary field with 0.
Let s r;j and k r;j be the element and its sequence index stored in register R j and let s r;j jk r;j denote their
concatenation. Next, the contents of the data registers are supplied as input to the sorting device. Let
received by R j after sorting, with s r;j 0 and k r;j 0 stored, respectively in the element and short
auxiliary field of R j . In two parallel write operations, the CU stores the element field and the short auxiliary
field of each register R j , (1 - j - p), into S[r; j] and I[r; j], respectively.
Steps 2, 4, 6, and 8 of the basic algorithm perform permutations. The implementation of Steps 6 and
8 does not involve sorting. In this case, the data movement involving the sample elements and that of the
corresponding sequence indices will be performed in two companion phases. Specifically, viewing the sample
set S and its corresponding sequence index set I as two matrices, the same permutation is performed on S
and I. Steps 2 and 4 of the basic algorithm involve both data movement operations and sorting. The data
movement operations in these steps are similar to those in Steps 6 and 8 and will not be detailed any further.
Recall that the sorting operations in Steps 2 and 4 of the basic algorithm are performed on the concatenation
of the two auxiliary fields storing the relative row number and the column number of the element. Hence, we
perform two companion sorting phases, one for permuting the sample elements and the other for permuting
sequence indices. Clearly, this can be implemented with the same time complexity.
It is easy to confirm that at the end of Step 2 of procedure MULTIWAY MERGE the sample set S is
sorted in row-major order. Furthermore, viewed as matrices, I[x; y] is the sequence index of the sample
element S[x; y]. Let the sorted version of S be
Equation (8) will be used in Step 3 to partition the elements of A into buckets. In order to do so, the leader
of each row in A needs to learn its rank in (8).
Our next goal is to associate with every memory row in A the rank
in S. This task will be carried out in two stages. In the first stage, using the sequence index and the rank
of s in S the CU assigns to s a row number row(s) in A. For every s in S, row(s) is either the exact
row number from which s was extracted in Step 1 or, in case the leaders of several rows are equal, row(s)
achieves a possible reassignment of leaders to rows. The details of the first stage are spelled out in procedure
ASSIGN ROW NUMBERS presented below. For convenience, we use the matrix representation of S and
I. These operations can be easily implemented using the addresses of words corresponding to S[x; y] and
Initially, I contains the sequence indices of samples in S. When the procedure terminates, I[x; y]
contains row(s) corresponding to
procedure ASSIGN ROW NUMBERS
begin
do
r k := the row number of the first memory row storing the sequence A k
endfor
2 e do
for do
endfor
endfor
In the second stage, the CU assigns the rank with the memory row row(s)
contained in I[x; y]. The operations performed on the matrix representations of S and I can be easily implemented
using the addresses of words corresponding to S[x; y] and I[x; y]. Since only read/write operations
are used in the procedure described, the total time spent on these operations is bounded by O(mp i\Gamma2
5.2 Implementing Step 3 and Step 4
Once the rank of each leader in A is known, we are ready to partition A into buckets. Our first objective is
to construct a collection of buckets such that the following conditions are satisfied:
(b1) every element of A belongs to exactly one bucket;
(b2) no bucket contains more than 2mp elements;
(b3) for every i and j, (1 -
strictly larger than any element in B j .
Before presenting our bucket partitioning scheme, we need a few definitions. Let
s mp (i\Gamma2)=2 be as in (8). The memory row with leader s b is said to be regular with respect to bucket B j ,
(j
Notice that equation (9) guarantees that every memory row in A is regular with respect to exactly one bucket
and that the identity of this bucket can be determined by the CU in constant time. Conversely, with respect
to each bucket there are exactly m regular memory rows.
A memory row r with leader s b in some sequence A k , (1 - k - m), is termed special with respect to
bucket B t if, with s a standing for the leader of the preceding memory row in A k , if any, we have
a
Let the memory rows with leaders s a and s b be regular with respect to buckets respectively,
such that j. It is very important to note that equation (10) implies that the memory row whose leader
is s b is special with respect to all the buckets
Conceptually, our bucket partitioning scheme consists of two stages. In the first stage, by associating all
regular and special rows with respect to a generic bucket
2 ), we obtain a set C j of candidate
elements . In the second stage, we assign the elements of A to buckets in such a way that the
actual elements assigned to bucket B j form a subset of the candidate set C j .
Specifically, an element x of a memory row regular with respect to bucket B j is assigned to B j if one of
the conditions below is satisfied:
s (j \Gamma1)m
or
s (j \Gamma1)m - x - s jm whenever s (j
The elements of A that have been assigned to a bucket by virtue of (11) or (12) are no longer eligible for
being assigned to buckets in the remainder of the assignment process.
Consider, further, an element x that was not assigned to the bucket with respect to which its memory
row is regular. Element x will be assigned to exactly one of the buckets with respect to which the memory
row containing x is special. Assume that the memory row containing x is special with respect to buckets
with be the smallest index, 1 - n - l(x), for which one of
the equations (11) or (12) holds with j n in place of j. Now, x is assigned to bucket B jn . The next result
shows that the buckets we just defined satisfy the conditions (b1)-(b3).
the conditions (b1), (b2), and (b3).
Proof. Clearly, our assignment scheme guarantees that every element of A gets assigned to some bucket
and that no element of A gets assigned to more than one bucket. Thus, condition (b1) is verified.
Further, notice that by (9) and (10), combined, for every j, (1
2 ), the candidate set C j
with respect to bucket B j contains at most 2m memory rows, and, therefore, at most 2mp elements of A.
Moreover, as indicated, the elements actually assigned to bucket B j are a subset of C j , proving that (b2) is
Finally, equations (11) and (12) guarantee that if an element x belongs to some bucket b j then it cannot
be strictly larger than any element in a bucket B k with k. Thus, condition (b3) holds as well. 2
It is worth noting that the preceding definition of buckets works perfectly well even if all the input elements
are identical. In fact, if all elements are distinct, one can define buckets in a simpler way. Moreover, in the
case of distinct elements, Steps 1-3 of procedure MULTIWAY MERGE can be further simplified.
We now present the implementation details of the assignment of elements to buckets. Write s
and denote, for every j, (1
2 ), the ordered pair (s (j \Gamma1)m ; s jm ) as the j-th bounding pair. Notice
that equations (11) and (12) amount to testing whether a given element lies between a bounding pair.
By (b2), no bucket contains more than 2mp elements from A. This motivates us to set aside 2m memory
rows for each bucket B j . Out of these, we allocate the first m memory rows to elements assigned to B j coming
from regular memory rows with respect to B j ; we allocate the last m memory rows to elements assigned
to bucket B j that reside in special memory rows with respect to B j . In addition, we find it convenient to
initialize the contents of the 2m memory rows allocated to B j to all +1's.
It is important to note that the regular memory rows with respect to a bucket B j are naturally ordered
from 1 to m by the order of the corresponding leaders in S. To clarify this last point, recall that by (9) the
leaders belonging to bucket B j are
s (j \Gamma1)m+1 ; s (j
Accordingly, the memory row whose leader is s (j \Gamma1)m+1 is the first regular row with respect to B j , the
memory row whose leader is s (j \Gamma1)m+2 is the second regular row with respect to B j , and so on. Similarly,
the fact that each sequence A k is sorted guarantees that it may contain at most one special memory row
with respect to bucket B j . Now, in case such a special row exists it will be termed the k-th special memory
row with respect to B j , to distinguish it from the others.
In order to move the elements to their buckets, the CU scans the memory rows in A one by one. Suppose
that the current memory row being scanned is row r in some sequence A k . We assume that the leader of
row r is s b and that the leader of row r \Gamma 1 is s a . Using equation (9), the CU establishes that row r is
regular with respect to bucket B j , where
similarly, that the previous memory row is regular
with respect to bucket
In case row r is the first row of A k , j 0 is set to 1.
Next, the elements in memory row r are read into the element fields of the data registers the CU broadcasts
to these registers the bounding pair (s (j \Gamma1)m ; s jm ). Using compare-and-set, each register stores in the short
auxiliary field a 1 if the corresponding element is assigned to bucket B j by virtue of (11) or (12) and a 0
otherwise. We say that an element x in some data register is marked if the value in the short auxiliary field
is otherwise, x is unmarked.
Clearly, every element x that is marked at the end of this first broadcast has been assigned to bucket
. In a parallel write operation, the CU copies all the marked elements to the corresponding words of the
row allocated to bucket B j . Once this is done, using compare-and-set, all
the marked elements in the data registers are set to +1 and the short auxiliary fields are cleared.
Further, the CU broadcasts to the data registers, in increasing order, the bounding pairs of the buckets
us follow the processing specific to bucket B j 0 . Having received the bounding pair
data register determines whether the value x stored in its element field satisfies (11)
or (12) with j 0 in place of j and marks x accordingly. In a parallel write operation, the CU copies all the
marked elements to the corresponding words of the next available memory row allocated to bucket B j . Next,
using compare-and-set all the marked elements in the data registers are set to +1, and the short auxiliary
fields are cleared. The same process is then repeated for all the remaining buckets with respect to which row
r is special.
The reader will not fail to note that when the processing of row r is complete, each of its elements has
been moved to the bucket to which it has been assigned. Moreover, by (9) and (10) there are, altogether, at
most mp i\Gamma2
regular rows and at most mp i\Gamma2
special rows, and so the total time involved in assigning the
elements of A to buckets is bounded by O(mp i\Gamma2
no calls to the sorting device. In summary, Step 3
can be implemented in O(mp i\Gamma2
data movement and no calls to the sorting device.
In Step 4, the buckets are sorted independently. If a bucket has no more than p 1
memory rows, it
can be sorted in one call to the basic algorithm. Otherwise, the bucket is partitioned in two halves,
each sorted in one call to the basic algorithm. Finally, the two sorted halves are merged using procedure
GROUPS. By Theorem 4, the task of sorting all the buckets individually can be performed
in O(mp i\Gamma2
calls to the sorting device and in O(mp i\Gamma2
data movement not involving sorting.
5.3 Implementing Step 5
To motivate the need for the processing specific to Step 5, we note that after sorting each bucket individually
in Step 4, there may be a number of +1's in each bucket. We refer to such elements as empty; memory
rows consisting entirely of empty elements will be termed empty rows. A memory row is termed impure if it
is partly empty. It is clear that each bucket may have at most one impure row. A memory row that contains
no empty elements is referred to as pure.
The task of coalescing the non-empty elements in the buckets into mp i\Gamma2
consecutive memory rows will
be referred to as compaction. For easy discussion, we assume that all sorted buckets are stored in consecutive
rows. That is, the non-empty rows of B 2 follow the non-empty rows of B 1 , the non-empty rows of B 3 follow
the non-empty rows of B 2 , and so on, assuming that all empty rows have been removed. The compaction
process consists of three phases.
Phase 1: Let C be the row sequence obtained by concatenating non-empty rows of B j 's obtained in Step 4
of MULTIWAY MERGE in the increasing order of their indices. We partition sequence C into subsequences
x such that each C j contains p 1
consecutive rows of C, except the last subsequence C x , which
may contain fewer rows. Clearly, x - 2mp i\Gamma3
2 . We use the basic algorithm to sort these subsequences
independently. Let the sorted subsequence corresponding to C i be C 0
i with empty rows eliminated for future
consideration. Let D be the row sequence obtained by concatenating rows of C 0
's in the increasing order
of their indices. We partition sequence D into subsequences y such that each D j contains p 1consecutive rows of D, except the last subsequence D y , which may contain fewer rows. We then use the
basic algorithm to sort these subsequences independently. Let the sorted subsequence corresponding to D i
be D 0
i with empty rows eliminated. Let E be the row sequence obtained by concatenating rows of D 0
's in
the increasing order of their indices.
Lemma 11 The preceding row of every impure row, except the last row, of E is a pure row.
Proof. We notice the following fact: except the last row of D, every row of D either contains at least p 1non-empty elements, or if it contains fewer than p 1
non-empty elements then its preceding row must be a
pure row. This is because that each row of C contains at least one non-empty element. An impure row of
D can be generated under one of two conditions: (a) if C j contains fewer than p non-empty elements, then
contains only one row, an impure row, with its non-empty elements coming from p 1
impure rows of C j ,
and (b) if a C j contains more than p non-empty elements, then C 0
contains only one impure row, and its
preceding row is a pure row. The lemma directly follows from this fact. 2
Phase 2: This phase computes a set of parameters, which will be used in the next phase. Let w be the
total number of (non-empty) rows in E. Assume that the rows of E are located from row 1 through row
w. For every j, (1
stand for the number of non-empty elements in the impure
memory row c j . The first subtask of Phase 2 is to determine
i\Gamma2. Consider a generic impure
row c j . To determine n j the CU reads the entire row c j into the data registers R 1
for every k, (1 - k - p), the c j -th word of memory module M k is read into register R k . The long
auxiliary field of data register R k is set to k. By using the compare-and-set feature, the CU instructs each
register R k to reset this auxiliary field to \Gamma1 if the element it holds is +1 (i.e. empty). Next, the data
registers are loaded into the sorting device and sorted in increasing order of their long auxiliary fields. It
is easy to confirm that, after sorting, the largest such value k j is precisely the position of the rightmost
non-empty element in memory row c j . Therefore, the CU sets . Consequently, the task
of computing all the numbers
calls to the sorting device and O(p i\Gamma2
read/write operations and does not involve sorting. Once the numbers are available, the CU
computes the prefix sums oe
This, of course, involves only additions and can be performed by the CU in O(mp i\Gamma2
call
to the sorting device. Let
e.
mod g. Define
Phase 3: Construct row group g, of consecutive rows as follows: if ff k\Gamma2 ? 0 then row
is the starting row of E k , else row k(p 1
is the starting row of E k ; the ending row of E k ,
is row k(p 1
and the ending row of E g is row w. Note that E k and E k+1 may share at most two
rows. By Lemma 11, for contains is at least (p+1)p2elements, and the last two rows
of contains at least p elements. For each g, perform the following operations: (a) sort
using the basic algorithm; (b) replace the fi smallest elements by +1's; (c) sort using the basic
algorithms; and (d) if ff k ? 0 and k ! g, eliminate the last row. For E g , perform (a), (b) and (c) only. Let
k be the row group obtained from E k , and let F be the row sequence obtained by concatenating rows of
's in the increasing order of their indices. F is the compaction of C.
Setting selected elements in a row to +1's can be done in O(1) time by a compare-and-set operation.
For example, setting the leftmost s elements of a row to +1's can be carried out as follows: read the row
into R i 's, then CU broadcast s to all R i 's, and each R i compare i with s and set its content to +1 if i - s;
then the modified row is written back to the memory array.
Based on Lemma 10, it is easy to verify that elements in F are in sorted order after Step 5, which can be
implemented in O(mp i\Gamma2
calls to the sorting device and O(mp i\Gamma2
data movement not involving sorting.
5.4 Complexity Analysis
With the correctness of our multiway merge algorithm being obvious, we now turn to the complexity.
Specifically, we are interested in assessing the total amount of data movement, not involving sorting, that
is required by procedure MULTIWAY MERGE. Specifically, let J(mp i
stand for the time spent on data
movement tasks that do not involve the use of the sorting device. If takes O(1) time. In case
takes O(m) time (refer to Theorem 3). Finally, if i ? 4, our previous discussion shows that
each of Step 1, Step 3, Step 4, and Step 5 require at most O(mp i\Gamma2
recursively,
J(mp i\Gamma2
time. Thus, we obtain the following recurrence system:
It is easy to confirm that, for p - 4, the solution of the above recurrence satisfies J(mp i
A similar analysis, that is not repeated, shows that the total number of calls to a sorting device of I/O size
performed by procedure MULTIWAY MERGE for merging m,
sequences, each of
2 , is bounded by O(mp i\Gamma2
To summarize our discussion we state the following important result.
Theorem 5 Procedure MULTIWAY MERGE performs the task of merging m,
quences, each of size p i
2 , in our architecture, using O(mp i\Gamma2
calls to the sorting device of I/O size p, and
O(mp i\Gamma2
data movement not involving sorting.
6 The Sorting Algorithm
With the basic algorithm and the multiway merge at our disposal, we are in a position to present the details
of our sorting algorithm using a sorting device of fixed I/O size p. The input is a set \Sigma of N items stored, as
evenly as possible, in p memory modules. Dummy elements of value +1 are added, if necessary, to ensure
that all memory modules contain d N
e elements: these dummy elements will be removed after sorting. Our
goal is to show that using our architecture-algorithm combination the input can be sorted in O
N log N
log p
time and O(N ) data space. We assume that p - 16, which along with (1) implies that
log
Equation (13) will be important in the analysis of this section, as our discussion will focus on the case where
a sorting network of I/O size p and depth O(log 2 p) is used as the sorting device 3 . A natural candidate for
such a network is Batcher's classic bitonic sorting network [1] that we shall tacitly assume.
Recall that by virtue of (1) we have, for some t; t - 4,
In turn, equation (14) guarantees that
log N
log p 1-
At this point we note that (14) and (15), combined, guarantee that
log
2: (16)
Write
and observe that by (14),
For reasons that will become clear later, we pad \Sigma with an appropriate number of +1 elements in such a
way that, with N 0 standing for the length of the resulting sequence \Sigma 0 , we have
It is important to note that (14), (17), and (19), combined, guarantee that
suggesting that the number of memory rows used by the sorting algorithm is bounded by O( N
will show that this is, indeed, the case.
The sorting algorithm consists of iterations. In order to guarantee an overall running time
of O( N log N
log p ), we ensure that each iteration can be performed in O( N
As we will see shortly, the
sorting network will be used in the following three contexts:
(i) to sort, individually, M memory rows;
3 As it turns out, the same complexity claim holds if the sorting device used is, instead, a p-sorter.
(ii) to sort, individually, M groups, each consisting of m consecutive memory rows, where m -
(iii) to sort, individually, M groups, each consisting of 2m consecutive memory rows, where m -
.
For an efficient implementation of (i) we use simple pipelining: the M memory rows to sort are input to
the sorting network, one after the other. After an initial overhead of O(log 2 p) time, each subsequent time
unit produces a sorted memory row. Clearly, the total sorting time is bounded by O(log
Our efficient implementation of (ii) uses interleaved pipelining. Let G GM be the groups we wish
to sort. In the interleaved pipelining we begin by running Step 1 of the basic algorithm in pipelined fashion
on group G 1 , then on group G 2 , and on so. In other words, Step 1 of the basic algorithm is performed on
all groups using simple pipelining. Then, in a perfectly similar fashion, simple pipelining is used to carry
out Step 2 of the basic algorithm on all the groups G 1 . The same strategy is used with all the
remaining steps of the basic algorithm that require the use of the sorting device. Consequently, the total
amount of time needed to sort all the groups using interleaves pipelining is bounded by O(log
An efficient implementation of (iii) relies on extended interleaved pipelining. Let G GM be the
groups we want to sort. Recall that Theorem 4 states that sorting a group of 2m consecutive memory rows
requires five calls to the basic algorithm. The extended interleaved pipelining consists of five interleaved
pipelining steps, each corresponding to one of the five calls to the basic algorithm. Thus, the task of sorting
all groups can be performed in O(log time. We now discuss each of the iterations of our sorting
algorithm in more detail.
Iteration 1
The input is Partitioned into N 0
groups, each involving p 1
memory rows. By using interleaved pipelining
with
, each such group is sorted individually. As discussed above, the running time of Iteration 1 is
bounded by O(log
Iteration
1. The input to Iteration k is a collection of N 0
ksorted sequences each of size p
stored in
consecutive memory rows. The output of iteration k is a collection of N 0
+1sorted sequences, each of
size p
stored in p
consecutive memory rows.
Having partitioned these sorted sequences into N 0
consecutive
sequences each, we proceed to sort each group G(k; j) by the call MULTIWAY MERGE(S 1 (k;
We refer to the call MULTIWAY MERGE(S 1 (k;
call of the first level. Observe that, since there are N
there will be altogether N
WAY MERGE calls of the first, one for each group. In Step 1 of a MULTIWAY MERGE call of the first
level we extract a sample S 2 (k; j) of S 1 (k; consisting of p 1
sorted sequences, each of size p
stored
in
consecutive memory rows. In turn, for every j, (1 - j - N
the sample S 2 (k; j) is sorted by
invoking MULTIWAY MERGE(S 2 (k;
which is referred to as a MULTIWAY MERGE call of
the second level. Step 1 of a MULTIWAY MERGE call of the second level extracts a sample S 3 (k; j) of
For every u, 1 -
2 c, a MULTIWAY MERGE call of level u is of the form MULTIWAY MERGE
In Step 2 of the call MULTIWAY MERGE(S u (k;
a MULTIWAY MERGE call of level u+1, which is of the form MULTIWAY MERGE(S u+1 (k;
Let r k;u denote the total number of rows in all samples S u (k; j) of level u. Clearly, we have r
p u . By
(13), r k;u - qp, and r when t is even and 2. The recursive calls to MULTIWAY MERGE
end at level b i k \Gamma1c, the last call being of the form
Note that depending on whether or not i k is odd.
We proceed to demonstrate that for takes O(r k;1 ) time. We will do this by
showing that the total time required by each of the five steps of the MULTIWAY MERGE calls of each level
u is bounded by O(r k;u ).
Consider a particular level u. Step 1 of all MULTIWAY MERGE calls of level u is performed on the
samples S u (k; j), in increasing order of j, so that all the samples S u+1 (k; are extracted one after the other.
Clearly, the total time for these operations is O(r k;u ).
We perform Step 3 of all the MULTIWAY MERGE calls of level u, in increasing order of j, to partition
into buckets each of the samples S u (k; using the corresponding S u+1 (k; j). By Lemma 10, each sample
buckets, and no bucket contains more than 2p 3
elements. As discussed
in Subsection 5.2, the task of moving all the elements of each S u (k; j) to their buckets can be carried out in
O(p
using the sorting device. Thus, the total time for partitioning the samples S u (k;
in all the MULTIWAY MERGE calls of level u is bounded by O( N 0
Step 4 of a MULTIWAY MERGE call of level u sorts the buckets (involving the elements of S u (k; j))
obtained in Step 3. We perform Step 4 of all MULTIWAY MERGE calls of level u in increasing order of
j, and use extended interleaved pipelining with
2 to sort all buckets of each S u (k; j). There are,
altogether, N 0
2u+1buckets in all the S u (k; j)'s. Thus, the total time for sorting all buckets is bounded by
and (d), the total time for sorting the buckets in all
MULTIWAY MERGE calls of level u is O(r k;u ).
Step 5 of a MULTIWAY MERGE call of level u has three phases. As discussed in Subsection 5.3, The
operations of Phase 1 and Phase 3 that involve the sorting device can be carried out using interleaved
pipelining. The operations of Phase 2 that involves the sorting device can be carried out using simple
pipelining. Clearly, the time complexity of Step 5 for all MULTIWAY MERGE calls of level u is bounded
by O(log
We now evaluate the time needed to perform Step 2 of all the MULTIWAY MERGE calls of level u. First,
consider the call of level b i k \Gamma1c, MULTIWAY MERGE(S b
1)). The sample
extracted in Step 1 of this call has p elements
is odd, we use simple pipelining to sort all the samples S b
(k;
we use interleaved pipelining with
2 to sort all the samples S b
(k;
In
either case, the time required is bounded by O( N 0
which is no more than O( N 0
Thus, the total time for Steps 1 through 5 of all the MULTIWAY MERGE calls of level b i k \Gamma1c) is no more
than O(r k;b
). Next, the time to perform Step 2 of all MULTIWAY MERGE calls of level u is inductively
derived as O(r k;u ) using our claim that the total time for Steps 1, 3, 4 and 5 of all MULTIWAY MERGE
calls of level u is no more than O(r k;u ), and hypothesis that Step 2 of all MULTIWAY MERGE calls of level
This, in turn, proves that the total time required for all the MULTIWAY MERGE calls
of level u is bounded by O(r k;u ).
Having shown that the time required for all the MULTIWAY MERGE calls of level u of Iteration k is
O(r k;u ), we conclude that the total time to perform Iteration k is O(r k;1 ), which is O( N
Iteration
2 the N input elements are sorted at the end of iterations. Assume that the algorithm does
not terminate in iterations. The input to Iteration t \Gamma 1 is a collection of
sorted sequences,
2 . Each such sequence is of size p t 2 , stored in p t\Gamma2
consecutive rows. To complete the
sorting, we need to merge these q sequences into the desired sorted sequence. This task is performed by the
call MULTIWAY MERGE(\Sigma t). The detailed implementation of MULTIWAY MERGE(\Sigma using a
sorting network as the sorting device and the analysis involved are almost the same as that of Iteration 2 to
Iteration different parameters are used. If the interleaved pipelining with
2 is used in
a step of MULTIWAY MERGE for iterations 2 to t \Gamma 2, then the corresponding step of MULTIWAY MERGE
for iteration uses the interleaved pipelining with Similarly, if the extended interleaved pipelining
with
2 is used in a step of MULTIWAY MERGE for iterations 2 to t \Gamma 2, then the corresponding
step of MULTIWAY MERGE for iteration uses the extended interleaved pipelining with q. The
MULTIWAY MERGE call of level b t\Gamma1c is MULTIWAY MERGE(S b
If t is odd, then 4. The recursion stops at
the (b t\Gamma1c)-th level. The sample set S b
obtained in Step 1 of the MULTIWAY MERGE call of
level b t\Gamma1c has qp 1
is odd, and it has qp elements if t is even.
Let r t\Gamma1;u be the total number of memory rows in S
. By a simple
induction, we conclude that the MULTIWAY MERGE call of level u, 1 - takes no more than
O(r t\Gamma1;u ) time. The running time of Iteration is the running time of the MULTIWAY MERGE call of
the first level, and it takes O(r t\Gamma1;1
We have shown that each of the iterations of MULTIWAY MERGE can be implemented with time
O( N
we conclude that the running time of our sorting algorithm is O
N log N
log p
. Since a p-sorter
can be abstracted as a sorting network of I/O size p and depth O(1), this time complexity stands if the sorting
device used is a p-sorter. The working data memory for each iteration is O(N ) simply because that the sample
size of an MULTIWAY MERGE call of level u is p times the sample size of an MULTIWAY MERGE call of
level u+1. Since the working data memory of one iteration can be reused by another iteration, the total data
memory required by our sorting algorithm remains to be O(N ). Summarizing all our previous discussions,
we have proved the main result of this work.
Theorem 6 Using our simple architecture, a set of N items stored in N
memory rows can be sorted in
row-major order, without any memory access conflicts, in O
N log N
log p
time and O(N ) data space, by using
either a p-sorter or a sorting network of I/O size p and depth O(log 2 p) as the sorting device.



--R


Sorting n objects with a k-sorter
An optimal sorting algorithm on reconfigurable mesh
The Art of Computer Programming
Tight bounds on the complexity of parallel sorting
Introduction to Parallel Algorithms and Architectures: Arrays
Sorting in O(1) time on a reconfigurable mesh of size n
Sorting n numbers on n
How to sort N items using a sorting Network of fixed I/O size
--TR

--CTR
Classifying Matrices Separating Rows and Columns, IEEE Transactions on Parallel and Distributed Systems, v.15 n.7, p.654-665, July 2004
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
Brian Grattan , Greg Stitt , Frank Vahid, Codesign-extended applications, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado
sorting networks;VLSI;special-purpose architectures;columnsort;hardware-algorithms