arXiv:1712.00870v1 [cs.DS] 4 Dec 2017

The Saukas-Song Selection Algorithm and Coarse
Grained Parallel Sorting
Laurence Boxer

∗

Abstract
We analyze the running time of the Saukas-Song algorithm for selection
on a coarse grained multicomputer without expressing the running time
in terms of communication rounds. We derive sorting algorithms that
are asymptotically optimal for restricted ranges of processors on coarse
grained multicomputers.
Key words and phrases: selection problem, coarse grained multicomputer, mesh, PRAM

∗ Department of Computer and Information Sciences, Niagara University, Niagara University, NY 14109, USA; and Department of Computer Science and Engineering, State University
of New York at Buffalo. E-mail: boxer@niagara.edu

1

1

Introduction

enough local memory to store the ID
number of every other processor. For
The paper [10], by Saukas and Song, more information on this model and aspresents an efficient algorithm to solve sociated operations, see [7].
the Selection Problem on coarse grained
parallel computers. The analysis of the
2.2 Terminology and notaalgorithm is presented in terms of the
tion
amount of time spent in local sequential operations and the number of com- We say an array list[1 . . . n] is evenly
munications rounds. In the current pa- distributed in a CGM (n, p) if each proper, we replace analysis of the num- cessor has Θ(n/p) members of the arber of communications rounds with an ray.
analysis of the running time of the entire algorithm. We also use the Saukas2.3 Data movement operaSong algorithm to obtain algorithms
tions
for sorting on coarse grained parallel
computers.
In the literature of CGM algorithms,
many papers, including [10], analyze
an algorithm by combining the run2 Preliminaries
ning time of sequential computations
with the number of “communications
2.1 Model of Computation
rounds,” the latter in which data is
Material in this section is quoted or communicated among the processors.
A communications round is described
paraphrased from [6].
The coarse grained multicomputer in [10] as an operation in which each
model, or CGM (n, p), considered in this processor of a CGM (n, p) can exchange
paper, has p processors with Ω(n/p) lo- O(n/p) data with other processors.
However, this definition does not
cal memory apiece - i.e., each processor
has Ω(n/p) memory cells of Θ(log n) lead to a clear understanding of the
bits apiece. The processors may be asymptotic running time of a CGM alconnected to some (arbitrary) intercon- gorithm. E.g., a communication round
nection network (such as a mesh, hy- could require a processor to send Θ(1)
percube, or fat tree) or may share global data to a neighboring processor, which
memory. A processor may exchange can be done in Θ(1) time; or, a commessages of O(log n) bits with any im- munication round could require commediate neighbor in constant time. In munication of Θ(1) data between diadetermining time complexities, we con- metrically opposite processors of a linsider both local computation time and ear array, which requires Θ(p) time.
Further, there is a sense in which
interprocessor communication time, in
standard fashion. The term “coarse the notion of a communication round
grained” means that the size Ω(n/p) of is not well defined. Consider again the
each processor’s memory is “consider- example of communication of Θ(1) data
ably larger” than Θ(1); by convention, between diametrically opposite proceswe assume n/p ≥ p (equivalently, n ≥ sors of a linear array. This could be rep2 ). Thus, each processor has at least garded as a single communication round

2

according to the description of communication rounds given above; or as p−1
communications rounds, in the ith of
which processor Pi sends Θ(1) data to
processor Pi+1 , 1 ≤ i < p.
Now that more is known about the
running times of communications operations in CGM than when [10] appeared, we can fully analyze the running time of the algorithm. In the remainder of this section, we discuss running times of communications operations used in the Saukas-Song algorithm.

Let X = {xj }nj=1 be a set of data
values and let ◦ be a binary operation
on X. A parallel prefix operation computes all of
x1 , x1 ◦ x2 , . . . , x1 ◦ x2 ◦ . . . ◦ xn .
Theorem 2.4. [3] Let X = {xj }nj=1 be
a set of data values distributed Θ(n/q)
per processor in a CGM (n, q). Then
the parallel prefix computation of
x1 , x1 ◦ x2 , . . . , x1 ◦ x2 ◦ . . . ◦ xn .

Theorem 2.1. [3] A unit of data can can be performed in Θ(n/q) time. At
be broadcast from one processor to all the end of this algorithm, the processor
other processors of a CGM (n, p) in O(p) that holds xj also holds x1 ◦ . . . ◦ xj . 
time. 

3

Let S be a set of data values distributed, not necessarily evenly, among
the processors of a parallel computer.
A gather operation results in a copy of
S being in a single processor Pi , and
we say S has been gathered to Pi [3, 9].
We have the following.

Analysis of the SaukasSong algorithm

The algorithm of [10] is given in Figure 1. We will refer to the steps of
the algorithm as labeled in this figure.
For convenience, we will take c = 1 in
step (2).

Theorem 2.2. [3] Let S be a nonempty
set of N elementary data values distributed among the processors of G, a
CGM (n, p), such that N = Ω(p) and
N = O(n/p). Then S can be gathered
to any processor of G in Θ(N ) time.

Let S be a set of data values distributed one per processor in a parallel
computer. A multinode broadcast operation results in every processor having
a copy of S.
Theorem 2.3. [3] Let S be a set of elementary data distributed one per processor in a CGM (n, p). Then a multinode broadcast operation, at the end of
which every processor has a copy of S,
can be performed in O(p2 ) time.

3

Figure 1: The Saukas-Song algorithm of [10]

4

Theorem 3.1. [10] After each performance of the body of the loop in step (2),
the number of elements remaining under consideration is reduced by at least
one quarter. 
Corollary 3.2. The number of performances of the body of the loop in
step (2) is O(log p).

distributed among the processors throughout the repetitions of the loop body. In
the worst case, some processor could have Θ(n/p) data
in each iteration of the loop
body. Therefore, this step
executes in O(n/p) time.
2. Step (2.2) is performed by a
gather operation. By Theorem 2.2, this can be done
in O(p) time. In the worst
case, the time required is Θ(p);
this is the case for an architecture such as a linear array of p processors.

Proof. It follows from Theorem 3.1 that
after k performances of the body of
the loop, the number of elements remaining under consideration is at most
(3/4)k n. Since step (2) terminates in
the worst case when the number of elements remaining under consideration
is at most n/p, termination requires,
in the worst case, (3/4)k n ≤ n/p, or
p ≤ (4/3)k . The smallest integer k
satisfying this inequality must therefore satisfy k = Θ(log p). Since the
loop could terminate after as little as 1
performance of its body, the assertion
follows.

3. Step (2.3) is performed in
Θ(p) time.
4. Step (2.4) is performed by
a broadcast operation. By
Theorem 2.1, this requires
O(p) time.
5. Step (2.5) is performed by
sequential semigroup (counting) operations performed by
all processors in parallel, in
linear time [8]. As noted above,
in the worst case a processor could have Θ(n/p) data
in each iteration of the loop
body. Therefore, this step
executes in O(n/p) time.

Theorem 3.3. The Saukas-Song algorithm for the Selection Problem runs in
p
Θ( n log
p ) time on a CGM (n, p) in the
worst case. In the best case, the running time is Θ(n/p). We may assume
that at the end of the algorithm, every
processor has the solution to the Selection Problem.
Proof. We give the following argument.
• Clearly, step (1) executes in Θ(1)
time.
• We analyze step (2) as follows.
1. Step (2.1) is executed by a
linear-time sequential algorithm [1, 8]. As Saukas and
Song observed, our algorithm
does not guarantee that the
data being considered are evenly
5

6. Step (2.6) is performed by a
gather operation. As above,
this can be done in O(p) time.
In the worst case, the time
required is Θ(p); this is the
case for an architecture such
as a linear array of p processors.
7. Step (2.7) is executed by semigroup operations in Θ(p) time.
8. Step (2.8) is performed by a
broadcast operation in O(p)

time. In the worst case, as
In the worst case, there is a procesabove, the time required is sor Pj that has the n/p smallest list
Θ(p).
elements, or the n/p largest list elements.
In this case, Pj has n/p el9. In the worst case, Step (2.9)
ements
during
Θ(log p) performances
requires each processor Pi to
of
the
body
of
the loop of step (2),
discard O(n/p) data items.
p
so
step
(2)
executes
in Θ( n log
p ) time,
This can be done as follows.
the algorithm executes in
In parallel, each processor andn therefore
log p
)
time.
Θ(
p
P rearranges its share of the
i

data so that the undiscarded
items are at the beginning
of the segment of (a copy of)
list stored in Pi , using a sequential prefix operation in
O(n/p) time.

4

Applications to sorting

4.1

Sorting on a general CGM

Theorem 4.1. Given a list of n data
evenly distributed among the processors
of a CGM (n, p), the list can be sorted
n
in O(n log p + n log
) time.
p

Thus, the time required for one
performance of the body of the
loop of step (2) is O(n/p + p) =
O(n/p). By Corollary 3.2, the
loop executes its body O(log p)
times. Thus, the loop executes
all performances of its body in
p
O( n log
p ) time.

Proof. For simplicity, we assume in the
following that every processor Pi has
n/p list entries. Consider the following algorithm for sorting list[1 . . . n],
evenly
distributed in a CGM (n, p).
• Step (3) is performed by a gather
operation. Since we now have
1. In parallel, each processor Pi sorts
N ≤ n/p, this is done in O(n/p)
its entries of list. The time retime.
quired is Θ( n log n ).
p

• Step (4) uses a linear time sequential algorithm to solve the
problem in Θ(N ) = O(n/p) time.
• Additionally, processor 1 can broadcast its solution to all other processors. By Theorem 2.1, this requires O(p) time.
p
Thus, the algorithm uses O( n log
p )
time.
In the best case, the loop of step (2)
executes its body once, when in step (2.9)
it is found that L < k ≤ L + E. In this
case, step (2) executes in Θ(n/p) time,
and the algorithm executes in Θ(n/p)
time.

6

2. For i = 1 to p − 1, compute the
in/p-th smallest member si of the
list and broadcast si to all processors. By Theorem 3.3, the running time of this step is O(n log p).
3. For elements of {i}pi=1 , let Si be
a set of elements that eventually
will be sent to Pi . The set Si is
computed as follows. (Note if it
is known in advance that the list
has no duplicate values, the steps
discussed below for partitioning
among the sets Si multiple list
values that equal some sk can be
omitted.)

• In parallel, each processor
Pi initializes ni,j = 0 for 1 ≤
j ≤ p. This requires Θ(p)
time.
• In this step, we determine
members of the Si that do
not equal any si . Let S1
be the set of at most n/p
members of list that are less
than s1 . For i ∈ {2, . . . , p},
let Si = {x ∈ list | si−1 <
x < si }. In parallel, each
processor Pi does the following. For each x ∈ list that
is in Pi , assign x a tag with
the value j if x ∈ Sj , and increment ni,j by 1. This can
be done for each x via binary search in O(log(n/p)) =
O(log n) time. Therefore, this
n
step requires O( n log
) time.
p
At the end of this step, ni,j
is the number of list entries
in Pi that, so far, have been
tagged for Sj .
• For 1P≤ j ≤ p, compute
p
nj = i=1 ni,j , the number
of list entries tagged so far
for Sj . Each such sum nj
can be computed by gathering the ni,j to Pj in Θ(p)
time and computing a sequential total in Pj in Θ(p) time;
in an additional Θ(p) time,
nj can be broadcast to all
processors. Therefore, doing the above for all j requires Θ(p2 ) = O(n) time.
• Since there may be multiple
list entries that equal si , do
the following.
For i = 1 to p
(a) In parallel, each processor Pj finds the first and
last of its list entries x,
7

respectively listuj and
listvj , such that x = si
and x was not previously
tagged for some Sk . Note
it may be that there are
no such list values in Pj .
Since the list entries in
Pj are sorted, this can
be achieved using binary
searches in O(log n) time.
(b) If i > 1, perform a parallel prefix operation to
tag for Si the first, at
most, n/p−ni list members that are equal to
si−1 and were not previously tagged for some
Sk , incrementing ni by
1 for each member tagged
for Si in this step. Note
the first and last values
in each processor operated upon by parallel prefix can be found in Θ(1)
time from the indices uj
and vj . Therefore, this
parallel prefix can be performed in O(n/p) time,
by Theorem 2.4. Note
at the end of this step,
ni again is the number
of list elements tagged
for Si .
(c) Perform a parallel prefix operation to tag for
Si the first n/p − ni list
members that are equal
to si and are not previously tagged. As above,
this requires O(n/p) time.
End For.
One performance of the loop
body requires O(n/p) time,
so the loop requires O(n) time.
4. For i = 1 to p, gather Si (which is

now the set of list entries tagged
i) to the processor Pi . By Theorem 2.2, this takes Θ(p × n/p) =
Θ(n) time.

Lemma 4.4. Suppose a CGM (n, p) is
a linear array and has a list of n entries stored in its processors, not necessarily evenly distributed. Then the
members of the list can be redistributed
5. In parallel, each processor Pi sorts so that the list is evenly distributed among
Si . At the end of this step, the the processors, in O(n) time.
list is sorted. The time for this
step is
Proof. This can be done by a rotation
of the data through the processors, in
n log n
Θ((n/p) log(n/p)) = Θ(
). which only excess data from processors
p
with more than n/p entries is rotated,
and a data value stops its participation
Thus, the running time of this al- in the rotation upon reaching a procesn
gorithm is O(n log p + n log
).
sor with less than n/p entries.
p
Remark 4.2. When log p ≤ logp n , or
equivalently, pp ≤ n, the running time
n
of this algorithm reduces to Θ( n log
),
p
which is asymptotically optimal, since
optimal time for sequential sorting is
Θ(n log n). The condition pp ≤ n is
very common, e.g., for personal computers, laptops, smartphones, game machines, embedded systems, etc. 

In the following, we assume some
extra memory, as the algorithm may
have intermediate states in which the
list is not evenly distributed.

Theorem 4.5. Let a CGM (np1/2 , p)
be a mesh with a list of n entries stored
in its processors, evenly distributed. Then
the list can be sorted in


n log p n log n
Remark 4.3. When log p ≥ logp n , or
+
Θ
p
p1/2
equivalently, pp ≥ n, our algorithm’s
running time reduces to O(n log p). This time.
is asymptotically faster than sequential
sorting time, although it seems reason- Proof. For simplicity, we assume that
able to hope for further improvement. the list items are all distinct. In the
more general case, we can determine

which members of the list go to any
4.2 Coarse grained sorting processor by accommodating duplicate
values as in the proof of Theorem 3.3.
on a mesh with extra
We also assume that the processors are
memory
numbered in row-major order [8]. ConIn this section, we obtain an algorithm sider the following algorithm.
for sorting on a CGM with a mesh ar1. For i = 1 to p1/2 , compute the
chitecture and extra memory. Our alip1/2 -th smallest list member ti
gorithm is asymptotically faster than
and broadcast ti to all procesthat of Theorem 4.1.
sors. By Theorem 3.3, this can
Since the rows and columns of a
be done in
mesh are linear arrays, the following
p
n log p
Θ(p1/2 × n log
will be useful.
p ) = Θ( p1/2 ) time.

8

2. The set Ri of list members that
must be sent to the processors of
row i is
R1 = {listj | listj ≤ t1 };
Ri = {listj | ti−1 < listj ≤ ti }
for 2 ≤ i ≤ p1/2 .
In parallel, all processors Pm determine, for each of their list members x, to which Ri x belongs, by
conducting binary searches for x
p1/2
among the values of {ti }i=1
. This
n
)
time.
requires O( n log
p
3. In parallel, each column j of the
mesh performs a column rotation
of its list members so that if x
is a list entry such that x ∈ Ri ,
then x finishes the rotation in Pi,j ,
the processor in row i and column j. In the worst case, for
some i, j we have all n/p1/2 list
entries of column j belonging to
Ri . Thus, this step takes O(n/p1/2 )
time. At the end of this step,
each list member is in the correct
row of the mesh for our ordering
of the data.
4. In a CGM (np1/2 , p), each processor can hold Ω(n/p1/2 ) data.
This is necessary as, in the worst
case, some processor has received
all the n/p1/2 list entries of its
column. In parallel, each row i
of the mesh does the following.

• For j = 1 to p1/2 , compute
the jp1/2 -th smallest list member ui,j in row i and broadcast ui,j to all processors of
the row. By Theorem 3.3,
this can be done in
!
n
log p1/2
p1/2
1/2
=
O p ×
p1/2
O



n log p
p1/2



time.

• Let Ui,1 be the set of list
members in Ri that are less
than or equal to ui,1 , and let
Ui,j be the set of list members in Ri that are greater
than ui,j−1 and less than or
equal to ui,j . Perform a row
rotation of the list members
of row i so that a list member x that belongs to Ui,j
stops its participation in the
rotation upon reaching Pi,j .
Since row i has n/p1/2 list
members, the time required
is O(n/p1/2 ). At the end of
this step, every list member
is in the correct processor
for the ordering of the list.
End parallel
5. In parallel, every processor Pi,j
sorts its list members in


n log n
Θ(n/p log(n/p)) = Θ
p

• Redistribute the list entries
time. This completes the sort.
of the row so that each processor Pi,j has n/p list memClearly, the
 running time of the aln
p
bers of Ri . The row has the gorithm is Θ n log
+ n log
.
p
p1/2
n/p1/2 list entries, so this
requires O(n/p1/2 ) time, by
Notice the following.
Lemma 4.4.

9

Remark 4.6. When

log p
p1/2

≤

log n
p ,

or,

References

p1/2

equivalently, p
≤ n, the running
time of our algorithm reduces to opn
), which is optimal. 
timal Θ( n log
p
Remark 4.7. When

log p
p1/2

≥

log n
p ,

or,

p1/2

[1] M. Blum, R.W. Floyd, V. Pratt,
R. L. Rivest, and R. E. Tarjan,
Bounds for selection, Journal of
Computer and System Sciences 7
(1973), 448461.

equivalently, p
≥ n, this algorithm’s
p
[2] L. Boxer, Efficient coarse grained
running time reduces to Θ( nplog
1/2 ), which
permutation exchanges and mais somewhat better than the running
trix multiplication, Parallel Protime for the non-optimal case for the
cessing Letters 19 (3), 2009, 477general architecture discussed at Re484.
mark 4.3. 
Corollary 4.8. A CGM (n, p) with a
PRAM
architecture
 can sort n data in

n log n
p
+
time.
Θ nplog
1/2
p

Proof. A PRAM can execute the algorithm of Theorem 4.5 without need for
the extra memory.

5

Further remarks

We have given an asymptotic analysis
of the running time of the Saukas-Song
selection algorithm for coarse grained
parallel computers. We have used this
algorithm to obtain efficient algorithms
for coarse grained parallel sorting.
There are many CGM algorithms
in such papers as [7, 5, 6] for which
running times are analyzed in terms
of Tsort (n, p), the time to sort Θ(n)
data on a CGM (n, p), where the expression Tsort (n, p) is used as an unevaluated primitive. For many of these
algorithms, we can use results of this
paper so that the running time of the
algorithm can be expressed without using Tsort (n, p) as an unevaluated primitive.
One can find experimental results
for the Saukas-Song selection algorithm
in [10].

10

[3] L. Boxer and R. Miller, Coarse
grained gather and scatter operations with applications, Journal
of Parallel and Distributed Computing 64 (11) (2004), 1297-1310.
[4] L. Boxer and R. Miller, Efficient
Coarse Grained Data Distributions and String Pattern Matching, International Journal of Information and Systems Sciences 6
(4) (2010), 424-434.
[5] L. Boxer, R. Miller, and A. RauChaplin, Scaleable parallel algorithms for lower envelopes with
applications, Journal of Parallel and Distributed Computing 53
(1998), 91-118.
[6] L. Boxer, R. Miller, and A.
Rau-Chaplin, Scalable parallel algorithms for geometric pattern
recognition, Journal of Parallel
and Distributed Computing 58
(1999), 466-486.
[7] F. Dehne, A. Fabri, and A. RauChaplin, Scalable parallel geometric algorithms for multicomputers, Int. Journal of Computational Geometry and Applications
6 (1996), 379-400.

[8] R. Miller and L. Boxer, Algorithms Sequential and Parallel, A
Unified Approach, 3rd ed., Cengage Learning, Boston, 2013.
[9] R. Miller and Q.F. Stout, Parallel Algorithms for Regular Architectures: Meshes and Pyramids,
The MIT Press, Cambridge, MA,
1996.
[10] E.L.G. Saukas and S.W. Song,
A note on parallel selection on
coarse-grained multicomputers,
Algorithmica 24 (1999), 371380.

11

