Time- and VLSI-Optimal Sorting on Enhanced Meshes.
AbstractSorting is a fundamental problem with applications in all areas of computer science and engineering. In this work, we address the problem of sorting on mesh connected computers enhanced by endowing each row and each column with its own dedicated high-speed bus. This architecture, commonly referred to as a mesh with multiple broadcasting, is commercially available and has been adopted by the DAP family of multiprocessors. Somewhat surprisingly, the problem of sorting m, (mn), elements on a mesh with multiple broadcasting of size $\sqrt n\times \sqrt n$ has been studied, thus far, only in the sparse case, where $m\in \Theta \left( {\sqrt n} \right)$ and in the dense case, where m(n). Yet, many applications require using an existing platform of size $\sqrt n\times \sqrt n$ for sorting m elements, with $\sqrt n
Introduction
With the tremendous advances in VLSI, it is technologically feasible and economically viable
to build parallel machines featuring tens of thousands of processors [4, 22, 39, 40, 42, 47].
However, practice indicates that this increase in raw computational power does not always
translate into performance increases of the same order of magnitude. The reason seems to
be twofold: first, not all problems are known to admit efficient parallel solutions; second,
parallel computation requires interprocessor communication which often acts as a bottleneck
in parallel machines.
In this context, the mesh has emerged as one of the platforms of choice for solving
problems in image processing, computer vision, pattern recognition, robotics, and computational
morphology, with the number of application domains that benefit from this simple
and intuitive architecture growing by the day [2, 4, 39, 40, 42]. Its regular and intuitive
topology makes the mesh eminently suitable for VLSI implementation, with several models
built over the years. Examples include the ILLIAC V, the STARAN, the MPP, and the
MasPar, among many others [4, 5, 11, 39]. Yet, the mesh is not for everyone: its large computational
diameter makes the mesh notoriously slow in contexts where the computation
involves global data movement.
To address this shortcoming, the mesh has been enhanced by the addition of various
types of bus systems [1, 2, 16, 18, 20, 23, 39, 43]. Early solutions involving the addition of
one or more global buses shared by all the processors in the mesh, have been implemented
on a number of massively parallel machines [2, 4, 19, 39]. Yet another popular way of
enhancing the mesh architecture involves endowing every row with its own bus. The resulting
architecture is referred to as mesh with row buses and has received a good deal of
attention in the literature. Recently, a more powerful architecture has been obtained by
adding one bus to every row and to every column in the mesh, as illustrated in Figure 1.
In [20] an abstraction of such a system is referred to as mesh with multiple broadcasting,
(MMB, for short). The MMB has been implemented in VLSI and is commercially available
in the DAP family of multicomputers [20, 38, 41]. In turn, due to its commercial
availability, the MMB has attracted a great deal of attention. Applications ranging from
image processing [21, 38, 41], to visibility and robotics [7, 14, 15, 37], to pattern recognition
[9, 10, 20, 25, 37], to optimization [17], to query processing [9, 13], and to other fundamental
problems [3, 6, 8, 9, 10, 16] have found efficient solutions on this platform and some of its
variants [18, 25, 29, 30].
As we shall discuss in Section 2, we assume that the MMB communicates with the
outside world via I/O ports placed along the leftmost column of the platform. This is
consistent with the view that enhanced meshes can serve as fast dedicated coprocessors for
present-day computers [28]. In such a scenario, the host computer passes data, in a systolic
fashion, to the enhanced mesh in batches of
n and so, in the presence of m elements to be
processed, the leftmost m
columns will be used to store the input. From now on, we will
not be concerned with I/O issues, assuming that the input has been pretiled in the leftmost
columns of the platform.
Sorting is unquestionably one of the most extensively investigated topics in computer
science. Somewhat surprisingly, thus far, the problem of sorting m, (m - n), elements on
an MMB of size
addressed only in the sparse case, where m 2 \Theta(
n) or
in the dense case, when m 2 \Theta(n). For the sparse case, Olariu et al. [35] have proposed a
time-optimal \Theta(log n) time algorithm to sort
elements stored in one row of an MMB of
size
n. Yet, many applications require using an existing platform of size
for sorting m elements, with
For example, in automated visual inspection
one is interested in computing a similarity measure coefficient for a vertical strip of the
image [27]. A similar situation arises in the task of tracking a mobile target across a series
of frames [31, 46]. In this latter case, the scene consists typically of static objects and one
is interested only in evaluating movement-related parameters of the target. In order to
perform this task in real-time it is crucial to use the existing platform to process (sort, in
parameter values at pixels in a narrow rectangular subimage only. The width
of the subimage of interest depends, of course, on the speed with which the target moves
across the domain. Therefore, in order to be able to meet read-time requirements one has
to use adaptive sorting algorithms that are as fast as possible.
The main contribution of this paper is to propose the first know adaptive time- and
VLSI-optimal sorting algorithm on the MMB. Specifically, we show that once we fix a
pretiled in the leftmost m
columns of an MMB of size
time. We show that this is time-optimal
for this architecture. It is also easy to see that this achieves the AT 2 lower bound in the
word model. At the heart of our algorithms lies a novel deterministic sampling scheme
reminiscent of the one developed recently by Olariu and Schwing [36]. The main feature of
our sampling scheme is that, when used for bucket sorting, the resulting buckets are well
balanced, making costly rebalancing unnecessary.
The remainder of this paper is organized as follows: Section 2 discusses the model of
computation used throughout the paper; Section 3 presents our time- and VLSI lower bound
arguments; Section 4 reviews a number of basic data movement results; Section 5 presents
the details of our optimal sorting algorithm. Finally, Section 6 summarizes the results and
poses a number of open problems.
2 The Model of Computation
An MMB of size M \Theta N , hereafter referred to as a mesh when no confusion is possible,
consists of MN identical processors positioned on a rectangular array overlaid with a high-speed
bus system. In every row of the mesh the processors are connected to a horizontal
bus; similarly, in every column the processors are connected to a vertical bus as illustrated
in

Figure

1. We assume that the processors in the leftmost column serve as I/O ports,
as illustrated, and that this is the only way the MMB can communicate with the outside
world.

Figure

1: An MMB of size 4 \Theta 4
Processor P (i; j) is located in row i and column j, (1 -
in the northwest corner of the mesh. Each processor P (i; j) has local links to its neighbors
exist. Throughout this paper,
we assume that the MMB operates in SIMD mode: in each time unit, the same instruction
is broadcast to all processors, which execute it and wait for the next instruction. Each
processor is assumed to know its own coordinates within the mesh and to have a constant
number of registers of size O(log MN ); in unit time, the processors perform some arithmetic
or boolean operation, communicate with one of their neighbors using a local link, broadcast
a value on a bus, or read a value from a specified bus. Each of these operations involves
handling at most O(log MN) bits of information.
Due to physical constraints, only one processor is allowed to broadcast on a given bus
at any one time. By contrast, all the processors on the bus can simultaneously read the
value being broadcast. In accord with other researchers [3, 16, 17, 20, 21, 23, 38, 39], we
assume constant broadcast delay. Although inexact, experiments with the DAP, the PPA,
and the YUPPIE multiprocessor array systems seem to indicate that this is a reasonable
working hypothesis [23, 26, 29, 38, 39].
3 The Lower Bounds
The purpose of this section is to show that every algorithm that sorts m; m - n, elements
pretiled in the leftmost d m
e columns of an MMB of size
must take
time.
Our argument is of information transfer type. Consider the submesh M consisting of
processors
n . The input will be constructed in
such a way that every element initially input into M will find its final position in the sorted
order outside of M.
To see that this is possible, note that m - n guarantees that the number of elements in M
satisfies:
mp
- mSince at most O( m
) elements can leave or enter M in O(1) time, it follows that any
algorithm that correctly sorts the input data must take at
time. Thus, we have
the following result.
Theorem 3.1. Every algorithm that sorts m, (m - n), elements stored in the leftmost m
columns of a mesh with multiple broadcasting of size
must take
In addition to time-lower bounds for algorithms solving a given problem, one is often
interested in designing algorithms that feature a good VLSI performance. One of the most
m//n
m/2/n

Figure

2: Illustrating the lower bound argument
commonly used metrics for assessing the goodness of an algorithm implemented in VLSI is
the AT 2 complexity [44], where A is the chip area and T is the computation time. A time
lower bound based on this metric is strong because it is not based on memory requirements
or input/output rate, but on the requirements for information flow within the chip. It is
well-known [44] that in the word model the AT 2 lower bound for sorting m elements on a
VLSI chip is m 2 . In our case, the size m of the input varies, while the area, n, of the mesh is
a constant. Hence, for any algorithm to be AT 2 -optimal, we must have
T is the running time. Thus, in this case, the time lower bound of \Omega\Gamma m
into VLSI-optimality.
In the remaining part of the paper, we show that the lower bounds derived above are tight
by providing an algorithm with a matching running time. For sake of better understanding,
we first present a preliminary discussion on some data movement techniques used throughout
the paper.
4 Data Movement
Data movement operations constitute the basic building blocks that lay the foundations of
many efficient algorithms for parallel machines constructed as an interconnection network of
processors. The purpose of this section is to review a number of data movement techniques
for the MMB that will be instrumental in the design of our sorting algorithm.
Merging two sorted sequences is one of the fundamental operations in computer science.
Olariu et al. [35] have proposed a constant time algorithm to merge two sorted sequences
of total length
stored in one row of an MMB of size
precisely, the
following result was established in [35].
Proposition 4.1. Let S
p n, be
sorted sequences stored in the first row of an MMB of size
holding
a s). The two sequences can be merged
into a sorted sequence in O(1) time.
Since merging is an important ingredient in our algorithm, we now give the details of the
merging algorithm [35]. To begin, using vertical buses, the first row is replicated in all rows
of the mesh. Next, in every row i, (1 - i - r), processor P (i; i) broadcasts a i horizontally
on the corresponding row bus. It is easy to see that for every i, a unique processor P (i; j),
. Clearly, this unique processor can now
use the horizontal bus to broadcast j back to P (i; i). In turn, this processor has enough
information to compute the position of a i in the sorted sequence. In exactly the same way,
the position of every b j in the sorted sequence can be computed in O(1) time. Knowing
their positions in the sorted sequence, the elements can be moved to their final positions in
time.
Next, we consider the problem of merging multiple sorted sequences with a common
length. Let a sequence of
n be stored, one per processor, in
the first row of an MMB of size
n. Suppose that the sequence consists of k sorted
subsequences and each subsequence consists of
consecutive elements of the original
sequence. The goal is to sort the entire sequence.
For definiteness, we assume that subsequence j, (1 - j - k), contains the elements
a (j \Gamma1)
. Our sorting algorithm proceeds by merging the subsequences two
at a time into longer and longer subsequences. The details are as follows. We set aside
submeshes of size 2
\Theta 2
k and every pair of consecutive subsequences is merged in each
one of these submeshes. Specifically, the first pair of subsequences is allocated the submesh
with its north-west corner; the next pair of subsequences is allocated the submesh
with processor
its north-west corner, and so on. Note that moving
the subsequences to the corresponding submeshes amounts to a simple broadcast operation
on vertical buses. Now in each submesh, the corresponding subsequences are merged using
the algorithm described above. By Proposition 4.1, this operation takes constant time. By
repeating the merging operation dlog ke times, the entire sequence is sorted. Consequently,
we have the following result.
Lemma 4.2. A sequence consisting of k equal-sized sorted subsequences stored in the first
row of a mesh with multiple broadcasting of size
can be sorted in O(log
Finally, we look at a data movement technique on an MMB of size
involving the
reorganization of the elements in the leftmost x columns of the mesh sorted in row-major
order to column-major order (see Figure 3(a) to 3(d)). This can be accomplished by a series
of simple data movement operations whose details follow. To simplify the notation, we shall
assume that
x
is an integer. The leftmost x columns of the mesh are moved, one at a
time, as follows. For each column s being moved, every processor P
broadcasts the element it holds to processor P (r;
illustrated in Figure 3(b).
We now view the mesh as consisting of horizontal submeshes R 1 each of
size
x
\Theta p n. In a submesh R p ,
x
broadcasts its value along column bus j and P (j; records it as shown in Figure 3(c).
Again, in constant time, each processor P (j; broadcasts its value along row bus j to
processor P (p; j). The above can be repeated for each submesh R p with 1 - p - x, thus
accomplishing the required data movement in O(x) time. To summarize our findings we
state the following result.
Lemma 4.3. Given a mesh with multiple broadcasting of size
stored in the leftmost x columns in sorted row-major order, the data can be moved into
sorted column-major order in the leftmost x columns in O(x) time.
(a) (b)
(c) (d)
R x
x
x

Figure

3: Illustrating the data movement of Lemma 4.3
5 The Algorithm
We are now in a position to present our time- and VLSI-optimal sorting algorithm for the
MMB. Essentially, our algorithm implements the well-known bucket sort strategy. The
novelty of our approach resides in the way we define the buckets, ensuring that no bucket
is overly full. Throughout, we assume an MMB R of size
Fix an arbitrary constant 1. The input is assumed to be a set S of m
elements from a totally ordered universe 1 stored in the leftmost d m
e columns of R. To
We assume O(1) time comparisons among the elements in the universe.
avoid tedious, but otherwise inconsequential, details we assume that m
is an integer. The
goal is to sort these elements in column-major order, so that they can be output from the
mesh in O( m
time. We propose to show that with the above assumptions the entire task
of sorting can be performed in O( m
time. Thus, from our discussion in Section 3, we can
conclude that our algorithm is both time- and VLSI-optimal. It is worth mentioning yet
another interesting feature of our algorithm, namely, that the time to input the data, the
time to sort, and the time to output the data are essentially the same.
To make the presentation more transparent and easier to follow we refer to the submesh
consisting of the leftmost m
columns of R as M. In other words, M is the submesh that
initially contains the input. Further, a slice of size k of the input consists of the elements
stored in k consecutive rows of M.
We will first present an outline of our algorithm and then proceed with the details. We
start by partitioning M into slices of size m
n and sort the elements in each such slice in
row-major in O( m
using an optimal sorting algorithm for meshes [32, 45]. Next, we
use bucketsort to merge consecutive m
of these into slices of size ( m
order. Using the same strategy, these slices are again merged into larger slices sorted in
row-major order. We continue the merging process until we are left with one slice of size
row-major order. Finally, employing the data movement discussed in Lemma
4.3, the data is converted into column-major order.
We proceed to show that the task of merging m
consecutive sorted slices of size ( m
into a sorted slice of size ( m
time. For this purpose, it is convenient to
view the original mesh R as consisting of submeshes R j;k of size ( m
involving processors P (r; s) such that (j \Gamma 1)( m
We refer to submeshes R k;k as diagonal - see Figure 4 for an illustration. Notice that
the diagonal submeshes can be viewed as independent MMBs, since the same task can be
performed, in parallel, in all of them without broadcasting conflict. The algorithm begins by
moving the elements in every R k;1 to the diagonal submesh R k;k . This can be accomplished,
column by column, in O( m
time. We now present the details of the processing that takes
place in parallel in every diagonal submesh R k;k .
The rightmost element in every row of R k;k will be referred to as the leader of that row
as shown in Figure 4. To begin, the sequence of leaders
in increasing order. Note that by virtue of our grouping, the sequence of leaders consists
leaders
R
R 11
R 22
R 22


Figure

4: Illustrating diagonal submeshes and leaders
of m
sorted subsequences, and so, by Lemma 4.2, the sequence of leaders can be sorted
in O(log m
time. Let this sorted sequence be a 1 , a
For convenience, we
assign a
Next, in preparation for bucket sort, we define a set of ( m
such that for every j, (1
(2)
By definition, the leaders a (j \Gamma1)m p n +1
through a jm
belong to bucket B j . This observation
motivates us to call a row in R k;k regular with respect to bucket B j if its leader belongs
to B j . Similarly, a row of R k;k is said to be special with respect to bucket B j if its leader
belongs to a bucket B t with t ? j, while the leader of the previous row belongs to a bucket
To handle the boundary case, we also say that a row is special with respect
to B j if it is the first row in a slice and its leader belongs to B t with t ? j. Note that, all
elements must be in either regular rows or special rows with respect to B j .
At this point, we make a key observation.
Observation 5.1. With respect to every bucket B j , there exist m
regular rows and at
most m
special rows in R k;k .
Proof. The number of regular rows follows directly from the definition of bucket B j in (2).
The claim concerning the number of special rows follows from the assumed sortedness of
the m
n slices of size ( m
implies that each slice of size ( m
may contain at most one special row with respect to any bucket.
In order to process each of the ( m
buckets individually, we partition the mesh R k;k
into submeshes T
each of size ( m
. Specifically, T 1 contains the
leftmost m
columns of R k;k , T 2 contains the next m
columns, and so on. Each submesh
is dedicated to bucket B j , in order to accumulate and process the elements belonging to
that bucket, as we describe next.
In O( m
time we replicate the contents of T 1 in every submesh T
Next, we broadcast in each submesh T j the values a (j \Gamma1) m
and a j m
that are used in (2)
to define bucket B j . As a result, all the elements that belong to B j mark themselves. All
the unmarked elements change their value to +1.
At this point, it is useful to view the mesh R k;k as consisting of submeshes Q
each of size m
\Theta m
. It is easy to see that processor P (r; s) is in Q l;j if
n .
The objective now becomes to move all the elements in T j belonging to bucket B j to
the submesh Q j;j . To see how this is done, let q k (= a v ),
be the
leader of a regular row with respect to bucket B j . The rank r of this row is taken to be r
1. Now, in the order of their ranks, the regular rows with respect to
are moved to the row in Q j;j corresponding to their rank. It is easy to confirm that all
the regular rows with respect to B j can be moved into the submesh Q j;j in O( m
time.
Now consider a row u of T j that is special with respect to bucket B j . Row u is assigned
the rank s=
. Note that no two special rows can have the same rank. In the order
of their ranks, special rows are moved to the rows of Q j;j corresponding to their ranks. As
the number of special rows is at most m
, the time taken to move all the special rows to
Q j;j is O( m
Notice that as a result of the previous data movement operations, each processor in Q j;j
holds at most two elements: one from a regular row with respect to B j and one from a
special row. Next, we sort the elements in each submesh Q j;j in overlaid row-major order.
In case the number of elements in Q j;j does not exceed m 2
after sorting the elements can
be placed one per processor. If the number of elements exceeds m 2
n , the first m 2
n of them are
said to belong to generation-1 and the remaining elements are said to belong to generation-
2. The elements belonging to generation-1 are stored one per processor in row-major order,
overlaid with those from generation-2, also in row-major order.
This task is performed as follows. Using one of the optimal sorting algorithm for meshes
[32, 45], sort the elements in regular rows in Q j;j in O( m
repeat the same
for the elements in special rows. Merging the two sorted sequences thus obtained can be
accomplished in another O( m
time.
Now, in each submesh Q j;j , all the elements know their ranks in bucket B j . Our next
goal is to compute the final rank of each of the elements in R k;k . Before we give the details
of this operation, we let S 1
be the sorted slices of size ( m
be the largest element in bucket B j . In parallel, using simple data movement, each m j is
broadcast to all the processors in T j in O( m
time. Next, we determine the rank of m j in
each of the S l 's as follows: in every S l we identify the smallest element (if any) strictly larger
than m j . Clearly, this can be done in at most O( m
time, since every processor only has
to compare m j with the element it holds and with the element held by its predecessor. Now
the rank of m j among the elements in R k;k is obtained by simply adding up the ranks of m j
in all the S l 's. Once these ranks are known, in at most O( m
time they are broadcast to
the first row of Q j;j , where their sum is computed in O(log m
knows its rank in R k;k , every element in bucket B j finds, in O(1) time, its rank in R k;k by
using its rank in its own bucket, the size of the bucket, and the rank of m j . Consequently,
we have proved the following result.
Lemma 5.2. The rank in R k;k of every element in every bucket can be determined in
O( m
time.
Finally, we need to move all the elements to the leftmost m
columns of R k;k in row-major
order. In O(1) time, each element determines its final position from its rank r as follows.
The row number x is given by d r
e and the column number y by
In every submesh T j , each element belonging to generation-1 is moved to the row x to
which it belongs in sorted row-major order by broadcasting the m
rows of Q j;j , one at
a time. This takes O( m
time. Notice that at this point every row of R k;k contains at
most m
elements. Knowing the columns to which they belong, in another m
time all the
elements can be broadcast to their positions along the row buses. This is repeated for the
generation-2 elements. In parallel, every diagonal submesh R k;k moves back its data into
the leftmost m
columns of submesh R k;1 . Thus, in O( m
time, all the elements are moved
to the leftmost m
columns of R. Now R contains slices of size ( m
each sorted in
row-major order.
To summarize our findings we state the following result.
Lemma 5.3. The task of merging m
consecutive sorted slices of size ( m
slice of size ( m
can be performed in O( m
time.
be the worst-case complexity of the task of sorting a slice of size ( m
It is easy to confirm that the recurrence describing the behavior of T (i
The algorithm terminates at the end of t iterations, when
Now, by dividing (1) throughout by
by raising to the (t 1)-th power we obtain
By combining (3) and (4), we obtain
In turn, (5) implies that
Thus, the total running time of our algorithm is given by
which is obtained by solving the above recurrence. Since ffl is a constant, we have proved
the following result.
Theorem 5.4. For every choice of a constant set of m, n 1
elements stored in the leftmost d m
e columns of a mesh with multiple broadcasting of size
can be sorted in \Theta( m
time. This is both time- and VLSI-optimal.
6 Conclusions and Open Problems
The mesh-connected computer architecture has emerged as one of the most natural choices
for solving a large number of computational tasks in image processing, computational geom-
etry, and computer vision. Its regular structure and simple interconnection topology makes
the mesh particularly well suited for VLSI implementation. However, due to its large communication
diameter, the mesh tends to be slow when it comes to handling data transfer
operations over long distances. In an attempt to overcome this problem, mesh-connected
computers have been augmented by the addition of various types of bus systems. Among
these, the mesh with multiple broadcasting (MMB) is of a particular interest being commercially
available, being the underlying architecture of the DAP family of multiprocessors.
The main contribution of this paper is to present the first known adaptive time- and
VLSI-optimal sorting algorithm for the MMB. Specifically, we have shown that once we
fix a constant the task of sorting m elements, n 1
pretiled in the
leftmost m
columns of an MMB of size
can be performed in O( m
time. This
is both time- and VLSI-optimal.
A number of problems remain open. First, it would be of interest to see whether the
bucketing technique used in this paper can be applied to the problem of selection. To this
day, no time-optimal selection algorithms for meshes with multiple broadcasting are known.
Also, it is not known whether the technique used in this paper can be extended to meshes
enhanced by the addition of k global buses [1, 12]. Further, we would like to completely
resolve these issues concerning optimal sorting over the entire range
that the results of Lin and others [24] show that for m near
n,\Omega\Gamma378 n) is the time lower
bound for sorting in this architecture. Their results imply that a sorting algorithm cannot
be VLSI-optimal for m near
Quite recently, Lin et al. [24] proposed a novel VLSI architecture for digital geometry
- the Mesh with Hybrid Buses (MHB) obtained by enhancing the MMB with precharged
1-bit row and column buses. It would be interesting to see whether the techniques used in
this paper extend to the MHB. This promises to be an exciting area for future work.

Acknowledgement

: The authors wish to thank the anonymous referees for their constructive
comments and suggestions that led to a more lucid presentation. We are also
indebted to Professor Ibarra for his timely and professional way of handling our submission



--R

Optimal bounds for finding maximum on array of processors with k global buses
Parallel Computation: Models and Methods
Square meshes are not always optimal
Design of massively parallel processor
STARAN parallel processor system hardware
Square meshes are not optimal for convex hull computation

A fast selection algorithm on meshes with multiple broadcasting

Convexity problems on meshes with multiple broadcasting
The MasPar MP-1 architecture




Designing efficient parallel algorithms on mesh connected computers with multiple broadcasting
Efficient median finding and its application to two-variable linear programming on mesh-connected computers with multiple broadcasting
Prefix computations on a generalized mesh-connected computer with multiple buses

Array processor with multiple broadcast- ing
Image computations on meshes with multiple broadcast
A multiway merge sorting network
IEEE Transactions on Computers
Parallel Processing Letters
The mesh with hybrid buses: an efficient parallel architecture for digital geometry
IEEE Transactions on Parallel and Distributed Systems
Computer Vision

Optimal sorting algorithms on bus-connected processor arrays
Methods for realizing a priority bus system
A Guided Tour of Computer Vision
Bitonic sort on a mesh-connected parallel computer
Finding connected components and connected ones on a mesh-connected parallel computer
Data broadcasting in SIMD computers
Optimal convex hull algorithms on enhanced meshes
A. new deterministic sampling scheme

The AMT DAP 500
The Massively Parallel Processor
Parallel Computing: Theory and Practice
Fractal graphics and image compression on a SIMD processor

Constant time BSR solutions to parenthesis matching
The VLSI complexity of sorting
Sorting on a mesh-connected parallel computer
Foundations of Vision
Algorithms for sorting arbitrary input using a fixed-size parallel sorting device
--TR
parallel algorithms;VLSI-optimality;lower bounds;sorting;meshes with multiple broadcasting;time-optimality