Generalized Algorithm for Parallel Sorting on Product Networks.
AbstractWe generalize the well-known odd-even merge sorting algorithm, originally due to Batcher [2], and show how this generalized algorithm can be applied to sorting on product networks.If G is an arbitrary factor graph with N nodes, its r-dimensional product contains $N^r$ nodes. Our algorithm sorts $N^r$ keys stored in the r-dimensional product of G in $O(r^2F(N))$ time, where F(N) depends on G. We show that, for any factor graph G, F(N) is, at most, O(N), establishing an upper bound of $O(r^2\,N)$ for the time complexity of sorting $N^r$ keys on any product network.For product networks with bounded r (e.g., for grids), this leads to the asymptotic complexity of O(N) to sort $N^r$ keys, which is optimal for several instances of product networks. There are factor graphs for which $F(N)=O({\rm log}^2\,N),$ which leads to the asymptotic running time of $O({\rm log}^2\,N)$ to sort $N^r$ keys. For networks with bounded N (e.g., in the hypercube the asymptotic complexity becomes $O(r^2).$We show how to apply the algorithm to several cases of well-known product networks, as well as others introduced recently. We compare the performance of our algorithm to well-known algorithms developed specifically for these networks, as well as others. The result of these comparisons led us to conjecture that the proposed algorithm is probably the best deterministic algorithm that can be found in terms of the low asymptotic complexity with a small constant.
Introduction
Recently, there has been an increasing interest in product networks in the literature. This is
partly due to the elegant mathematical structure of product networks and partly due to the
fact that several well-known networks, such as hypercubes, grids, and tori, are instances of the
family of product networks. Many other instances of product networks have been proposed
recently, such as products of de Bruijn networks [9, 28], products of Petersen graphs [25],
and mesh-connected trees [8] (which are products of complete binary trees). As a general
class, routing properties of product networks have been studied in [4, 10]. Topological and
embedding properties of product networks have been analyzed in [9].
These papers aside, there has been no general study of algorithms for this important class
of networks. This paper makes an attempt towards filling this gap by presenting a generalized
sorting algorithm for product networks. A first version of the algorithm presented here, as
well as other generalized algorithms for several different problems, has been proposed in [11].
We expect that other researchers will eventually develop a variety of additional algorithms
for product networks.
In [2], Batcher presented two efficient sorting networks. Algorithms derived from these
networks have been presented for a number of different parallel architectures, like the shuffle-
exchange network [30], the grid [22, 31], the cube-connected cycles [27], and the mesh of trees
[24].
One of Batcher's sorting networks has, as main components, subnetworks that sort bitonic
sequences. A bitonic sequence is the concatenation of a non-decreasing sequence of keys with
a non-increasing sequence of keys, or the rotation of such a sequence. Sorting algorithms
based on this method are generally called "bitonic sorters." Several papers have been devoted
to generalizing bitonic sorters [3, 17, 21, 23].
The main components of the other sorting network proposed by Batcher in [2] are sub-networks
that merge two sorted sequences into a single sorted sequence. He called these
"odd-even merging" networks. Several papers generalized this network to merging of k
sorted sequences, where k ? 2. These are generally called k-way merging networks. Examples
are Green [12] who constructed a network based on 4-merge, and Drysdale and Young
Tseng and Lee [32], Parker and Parberry [26], Lisza and Batcher [20],
and Lee and Batcher [16] who constructed networks based on multiway merging.
Similarly, other algorithms based on a multiway-merge concept have been presented the
most commonly known being Leighton's Columnsort algorithm [19]. Initially, the objective
of this algorithm was to show the existence of bounded-degree O(n)-node networks that can
in O(log n) time. In this network the permutations at each phase are hard-wired
and the sortings are done with AKS networks, which limits its applicability for practical
purposes. However, Aggarwal and Huang [1] showed that it is possible to use Columnsort
as a basis and apply it recursively. Parker and Parberry's network cited above is also based
on a modification of Columnsort. These algorithms behave nicely when the number of keys
is large compared with the number of processors.
In this paper we develop another multiway-merge algorithm that merges several sorted
sequences into a single sorted sequence of keys. From this multiway-merge operation we
derive a sorting algorithm, and we show how to use this approach to obtain an efficient sorting
algorithm for any homogeneous product network. In its basic spirit, our multiway-merge
algorithm is somehow similar to a recent version of Columnsort [18, page 261] (although both
were developed independently), but ours outperforms Columnsort due to some fundamental
differences in the interpretation of this basic concept. First, our algorithm is based on a
series of merge processes recursively applied, while Columnsort is based on a series of sorting
steps. The only time we use sorting is for N 2 keys. Columnsort, on the other hand, uses
several recursive calls to itself in order to merge. Second, by observing some fundemental
relationships between the structural properties of product networks, and the definition of
sorted order we are able to avoid most of the routing steps required in the Columnsort
algorithm.
Among the main results of this paper, we show that the time complexity of sorting
N r keys for any N r -node r-dimensional product graph is bounded above as O(r 2 N ). We
also illustrate special cases of product networks with running times of O(r 2 ), O(N ), and
O(log 2 N) to sort N r keys.
On the grid and the mesh-connected trees [8, 9] with bounded number of dimensions
the algorithm runs in asymptotically-optimal O(N) time. On the r-dimensional hypercube
the algorithm has asymptotic complexity O(r 2 ), which is the same as that of Batcher odd-even
merge sorting algorithm on the hypercube [2]. Although there are asymptotically-
faster sorting algorithms for the hypercube [6], they are not practically useful for reasonable
number (less than 2 20 ) of keys [18]. We note, however, that there are randomized algorithms
which perform better on hypercubic networks than the Batcher algorithm in practice [5].
Adaptation of such approaches for product networks appears to be an interesting problem
for future research.
For products of de Bruijn networks [9, 28], our approach yields the asymptotic complexity
of O(r 2 log 2 N) time to sort N r keys, which reduces to O(log 2 N) time when the number of
dimensions is fixed. The same running time can be obtained for products of shuffle-exchange
networks also, because products of shuffle-exchange networks are equivalent in computational
power (i.e. in asymptotic complexity of algorithms) to products of de Bruijn networks [9].
This running time is same as the asymptotic complexity of sorting N r keys on the N r -node
de Bruijn or shuffle-exchange network by Batcher algorithm.
Finally, we can summarize the main contributions of this paper as to:
Effectively implement a sorting algorithm for homogeneous product networks,
ffl Obtain generalized upper bounds on the running time required for sorting on any
homogeneous product network, regardless of the topology of the factor network used
to build it,
ffl Show that, for several important instances of homogeneous product networks, the upper
bound derived matches the running time of the most-popular algorithms developed
specifically for these networks.
This paper is organized as follows. In Section 2 we present the basic definitions and the
notation used in this paper. In Section 3 we present our multiway-merge algorithm and
show how to use it for sorting. In Section 4 we show how to implement the multiway-merge
sorting algorithm on any homogeneous product network and analyze its time complexity. In
Section 5 we apply the algorithm to several homogeneous product networks and we obtain
the corresponding time complexity. The conclusions of this paper are given in Section 6.
Figure

1: Recursive construction of multi-dimensional product networks: (a) the factor
two-dimensional product; (c) three-dimensional product.
Definitions and Notation
2.1 Definitions and Notation Relating to Product Networks
Let G be an N-node connected graph, we define its r-dimensional homogeneous product as
follows.
Given a graph G with vertex set arbitrary edge set
EG , the r-dimensional homogeneous product of G, denoted PG r , is the graph whose vertex
set is V whose edge set is E PGr , defined as follows: two vertices
are adjacent in PG r if and only if both of the following
conditions are true:
1. x and y differ in exactly one symbol position,
2. if i is the differing symbol index, then
In this paper we assume that the r-tuple label for a node of PG r is indexed as 1 \Delta \Delta \Delta r, with
1 referring to the rightmost position index and r referring to the leftmost position index.
At a more intuitive level, the construction of PG r from PG G, can be
described by referring to Figure 1. Let x be a node of PG r\Gamma1 , and let [u]P G r\Gamma1 be the graph
obtained by prefixing every vertex x in PG r\Gamma1 by u, so that a vertex x becomes ux. First,
place the vertices of PG r\Gamma1 along a straight line as shown in Figure 1. Then, draw N copies
of PG r\Gamma1 such that the vertices with identical labels fall in the same column. Next extend
the vertex labels to obtain [u]P G r\Gamma1 , for Finally, connect the columns
in the interconnection pattern of the factor graph G, such that ux is connected to u 0 x if and
only if (u;
In this construction, we use [u]P G r\Gamma1 to refer to the uth copy of PG r\Gamma1 . What is not
explicitly stated here is the fact that [u]P G r\Gamma1 is the uth copy at dimension r. We can further
extend this notation to allow us to add a new symbol at any position of the vertex labels.
For this purpose, we use [u]P G i
to mean that the vertex labels of PG are extended by
inserting the value u at position i. As a result, the symbol at position j moves to position
allows us to observe that the construction of the
preceding paragraph could be re-stated for [u]P G i
for any position i, not just the leftmost
position.
Conversely, we can obtain the [u]P G i
subgraphs, for erasing all
the dimension-i edges in PG r . This process can be repeated recursively, and described by
a simple extension of our notation: we use [u; v]PG i;j
r\Gamma2 to refer to subgraphs isomorphic to
PG r\Gamma2 obtained by erasing the connections at dimensions i and j from PG r . A particular
subgraph so obtained can be distinguished by its unique combination of [u; v] values at
index positions i and j, respectively. The notation is similarly extended for erasing arbitrary
number of dimensions, and the order of the values in square brackets corresponds to the
order of the superscripts.
2.2 Definition and Properties of the Sorted Order
For an arbitrary factor graph G, the vertex labels 0; define the ascending order
of data when sorted. However, we need to define an order for the nodes of PG r , which will
determine the final location of the sorted keys. The order defined is known as snake order.
for the r-dimensional product graph PG r :
1. If the snake order corresponds to the order used for labeling the nodes of G.
2. If r ? 1, suppose that the snake order has been already defined for PG r\Gamma1 . Then,
(a) [u]P G r
has the same order as PG r\Gamma1 if u is even, and reverse order if u is odd.
(b) if any value in [u]P G r
precedes any value in [v]P G r
.
The snake order for product graphs is closely related to Gray-code sequences, which have
the fundamental property that any two consecutive terms in the sequence differ in exactly
one bit. Here we are dealing with N-ary symbols instead of binary symbols. Therefore we
need to use N-ary Gray-code sequences.
First recall the definition of Hamming distance and Hamming weight. Let s; z be r-tuples
from f0; then the Hamming distance between s and z is D(s;
is the absolute value of s . The Hamming weight of an r-tuple s is
Here we allow one or more of the elements of the r-tuples to be the special
"all" symbol  , which will be defined later. If any of the symbols in the r-tuple is the "all"
symbol then its index position is omitted whenever the r-tuple is involved in the computation
of Hamming distances and Hamming weights.
We say that a sequence Q r is an N-ary Gray-code sequence of order r, if its elements
are all the r-tuples in f0; any two consecutive elements in it have unit
Hamming distance. Consequently, the Hamming weights of two consecutive terms will have
different parity. We use R(Q r ) to denote the sequence obtained by listing the elements of
Q r in reverse order.
The definition below shows one way to construct N-ary Gray-code sequences of arbitrary
order recursively. Let [u]Q k denote the sequence obtained by prefixing each element of Q k
with the symbol u if u is even, or by prefixing each element of R(Q k ) with u, if u is odd.
Definition 3 An N-ary Gray-code sequence of order r, denoted Q r , can be obtained as
1.
2. concatenation
of the sequences inside the curly brackets.
Note that Q r is in fact the snake order defined on the vertices of the r-dimensional
product network PG r .
Example: If the 3-ary Gray-code sequences of order r, for are:
112, 102, 101, 100, 200, 201, 202, 212, 211, 210, 220, 221, 222g,
Note that Q r could have been defined for inserting the value u at any position in the
above definition, rather than the leftmost position. This observation allows us to use [u]Q i
to denote the subsequence of Q r that contains the value u in position i. We are especially
interested in the subsequences [u]Q 1
1. For given u, the elements of
this subsequence are in positions u, u, and so on, in
Given this observation, and the identity relationship between Q r and the snake order for
the nodes of PG r , it follows that if PG r contains a sequence of keys sorted in snake order,
the keys on the subgraph [u]P G 1
are also sorted in snake order, and are in the positions
u, etc., of the whole sequence.
Consider now dividing Q r into N r\Gamma1 subsequences of N consecutive elements each. We
observe from Definition 3 that any two elements within the same subsequence would differ in
their rightmost symbols only. Thus, we can distinguish a particular subsequence of elements
with the common symbols they have at positions 2; use [
to denote the
group sequence obtained from Q r in this fashion, where   stands for all of 0;
For example, given Q 3 as above, its group sequence is
where   stands for all of 0, 1, and 2. Thus, more explicitly, we can write
Here, an element g of [
is of the form if the Hamming weight
of g is even, or of the form if the Hamming weight of g is odd.
Moreover, two successive elements of [
still have unit Hamming distance.
Given the relation between Q r and PG r , an element g of [
identifies a dimension-1
G-subgraph of PG r . This is because in such a G-subgraph of PG r all node labels have the
same values at symbol positions 2; We say that a G-subgraph is even (resp. odd)
if the Hamming weight for its corresponding element of [
is even (resp. odd). We
can extend the above notation and write [ ;  ]Q 2;1
r\Gamma2 to identify the set of PG 2 -subgraphs at
dimensions f1; 2g. Two consecutive elements of [ ;  ]Q 2;1
r\Gamma2 will again have unit Hamming
distance, and thus the elements of [ ;  ]Q 2;1
r\Gamma2 will be ordered in Gray-code sequence. Again,
an element
r\Gamma2 can have even or odd Hamming weight, and the corresponding
subgraph can be said to be even or odd.
3 Multiway-Merge Sorting Algorithm
This section develops the basic steps of the proposed sorting algorithm without regard to
any specific network. For this discussion, it does not even matter whether the algorithm is
performed sequentially or in parallel. The subsequent sections will give the implementation
details for product networks.
A sorted sequence is defined as a sequence of keys (a
a . The multiway-merge algorithm combines N sorted sequences A
(a into a single sorted sequence
Since this will be the case when we implement the algorithm on product networks, we will
assume m to be some power of N , hence the resulting sorted
sequence, J , will contain N k keys.
The heart of the proposed sorting algorithm is the multiway-merge operation. Thus, we
will spend much of our time discussing this merging process. In order to build an intuitive
understanding of the basic idea of the merge operation, we assume that the keys to be
sorted are placed on a two-dimensional block, as shown in Figure 2. This is not to imply
a two-dimensional organization of the data in product networks. When implementing the
algorithm in product networks, each row of data (containing
will be stored on a 1)-dimensional subgraph of the product graph. The two-dimensional
organization in Figure 2 is for the reader's convenience in visualizing what happens to the
data at various steps of the algorithm, so that we can use the terms "row" and "column" in
order to refer to groups of keys that are subjected to the same step of algorithm. Our use of
the terms "row" and "column" should not be interpreted to imply the physical organization
of data in a two dimensional array.
Subject to this clarification, we initially assume that each sorted sequence A i , is in a
different row (see Figure 2). We also assume the existence of an algorithm which can sort
We make no assumption about the efficiency of this algorithm as yet. In Section 5
we discuss several possible ways to obtain efficient algorithms for this purpose. The purpose
of this assumption is to maintain the generality of the discussions, independent of the factor
network used to build the product network.
To show the correctness of the algorithm we will use the zero-one principle due to Knuth
A
A
A
A
m=N

Figure

2: Initial situation before the merge process starts. Each sorted sequence is represented
as a horizontal block (a row).
[13]. The zero-one principle states that if an algorithm based on compare-exchange operations
is able to sort any sequence of zeroes and ones, then it sorts any sequence of arbitrary
keys.
3.1 Multiway-Merge Algorithm
Here we consider how to merge N sorted sequences, A
single large sorted sequence. The initial situation is pictured in Figure 2.
The merge operation consists of the following steps:
1: Distribute the keys of each sorted sequence A i among N sorted subsequences
1. The subsequence B i;j will have the form
is equivalent to writing the keys of each A i on a m
N \Theta N array in snake order (as shown in

Figure

and then reading the keys column-wise so that column j of the array becomes B i;j ,
1. Note that each subsequence B i;j is sorted, since the keys in it are in
the same relative order as they appeared in A i .

Figure

4 illustrates the situation after the completion of this process. Each of the N
rows contains N sorted subsequences B i;j , where each B i;j box in Figure 4 corresponds to a
column of keys in Figure 3 written horizontally.
Example: If for some i, A
Step 2: Merge the N subsequences B i;j found in column j of Figure 4 into a single sorted
sequence C j , for 1. This is done in parallel for all columns by a recursive call
to the multiway-merge process if the total number of keys in the column, m, is at least N 3 .
If the number of keys in a column of Figure 4 is N 2 , a sorting algorithm for sequences of
length N 2 is used (we already assumed the existence of such an algorithm above), because a
recursive call to the merge process would not make much progress when m is N 2 (this point
will be cleared at the end of this section). At the end of this step, we write the resulting
subsequences vertically in N columns of length m each. The situation after this step is
illustrated in Figure 5.
m/N

Figure

3: Distribution of the keys of A i among the N subsequences B i;j . The thick line
represents the keys of A i in snake order.
m/N

Figure

4: Situation after step 1: each sequence A i , has been distributed into N subsequences
. Each of the subsequences contains m=N elements and is still sorted.

Figure

5: Situation after merging the subsequences in each column. The keys are sorted
from top to bottom.
Step 3: Interleave the sequences C j into a single sequence
sequence D is formed simply by reading the m \Theta N array of Figure 5 in row-major order
starting from the top row. The sequence D is re-drawn in Figure 6 from the C j sequences of

Figure

5 with no change in the organization of data. Figure 6 is identical to Figure 5, except
that we regard it as one big sequence to be read in row-major order.
We prove below that D is now "almost" sorted. This situation is shown in Figure 6. If
the keys being sorted can only take values of zero or one, the shaded area represents the
position of zeroes and the white area represents the position of ones. As D is obtained by
reading the values in row-major order, the potential dirty area (window of keys not sorted)
has length no larger than N 2 . This fact will be shown in Lemma 1.
Step 4: Clean the dirty area. To do so we start by dividing the sequence D into m=N
subsequences of N 2 consecutive keys each. We denote these subsequences as
1. The ith subsequence has the form
the first N rows of keys in Figure 6 (or equivalently in Figure 5) are concatenated to obtain
the next N rows are concatenated to obtain E 2 , and so on (see Figure 7.(a)).
We then independently sort the subsequences (rows in Figure 7.(a)) in alternate orders by
using the algorithm which we assumed available for sorting N 2 keys. E i is transformed into
a sequence F i (see Figure 7.(b)), where F i contains the keys of E i sorted in non-decreasing
order if i is even or in non-increasing order if i is odd, for
Now, we apply two steps of odd-even transposition between the sequences F i , for
(i.e. in the vertical direction of Figure 7.(b)). In the first step of odd-even trans-
position, each pair of sequences F i and F i+1 , for i even, are compared element by element.
Two sequences G i and G i+1 are formed (not shown in the figure) where
and g. In the second step of the odd-even transposition, G i and G i+1
rows

Figure

Sequence D obtained after interleaving. The order goes from top to bottom by
reading successive rows from left to right. The shaded area is filled with zeroes and the white
area is filled with ones. The boundary area has at most N rows, as shown in Lemma 1.
for i odd are compared in a similar manner to form the sequences H i and H i+1 . Figure 7.(c)
shows the situation after the two steps of odd-even transposition.
Finally, we sort each sequence H i in non-decreasing order, generating sequences I i , for
Figure 7.(d)). The final sorted sequence J is the concatenation of the
sequences I i .
We need to show that the process described actually merges the sequences. To do so we
use the zero-one principle mentioned earlier.
sorting an input sequence of zeroes and ones, the sequence D obtained
after the completion of step 3 is sorted except for a dirty area which is never larger than N 2 .
Proof: Assume that we are merging sequences of zeroes and ones. Let z i be the number of
zeroes in sequence A i , for 1. The rest of keys in A i are ones. Step 1 breaks
each sequence A i into N subsequences B i;j , 1. It is easy to observe, from the
way step 1 is implemented, that the number of zeroes in a subsequence B i;j is bz
or 1. Therefore, for a given i, the sequences B i;j can differ from each
other in their number of zeroes by at most one.
At the start of step 2, each column j is composed of the subsequences B i;j for
1. At the end of step 2, all the zeroes are at the beginning of each sequence
. The number of zeroes in each sequence C j is the sum of the number of zeroes in B i;j
for fixed j and 1. Thus, two sequences C j can differ from each other by
at most N zeroes. In step 3 we interleave the N sorted sequences into the sequence D by
taking one key at a time from each sequence C j . Since any two sequences C j can differ in
their number of zeroes by at most N , and since there are N sequences being interleaved,
(a) (b) (c) (d)
F
F
I
Figure

7: Cleaning of the dirty area.
the length of the window of keys where there is a mixture of ones and zeroes is at most N 2 .
Now we can show how the last step actually cleans the dirty area in the sequence.
Lemma 2 The sequence J obtained (by concatenation of sequences I i in snake order) after
the completion of step 4 is sorted.
Proof: We know that the dirty area of the sequence D, obtained in step 3, has at most
length N 2 . If we divide the sequence D into consecutive subsequences,
the dirty area can either fit in exactly one of these subsequences or be distributed between
two adjacent subsequences.
If the dirty area fits in one subsequence E k , then after the initial sorting and the odd-even
transpositions, the sequences H i contain exactly the same keys as the sequences E i , for
1. Then, the last sorting in each sequence H i and the final concatenation of
the I i sequences yield a sorted sequence J .
However, if the dirty area is distributed between two adjacent subsequences, E k and
we have two subsequences containing both zeroes and ones. Figure 7.(a) presents an
example of this initial situation. After the first sorting, the zeroes are located at one side of
F k and at the other side of F k+1 (see Figure 7.(b)).
One of the two odd-even transpositions will not affect this distribution, while the other
is going to move zeroes from the second sequence to the first and ones from the first to the
second. After these two steps, H k is filled with zeroes or H k+1 is filled with ones (see Figure
7.(c)). Therefore, only one sequence contains zeroes and ones combined. The last step of
sorting will sort this sequence. Then the entire sequence J will be sorted (see Figure 7.(d)).
3.2 The Need for a Special Algorithm for N 2 Keys
The reader can observe that, at the end of step 3, the dirty area will still have length N 2 even
when we are merging N sequences of length N each. Thus, we do not make much progress
when we apply the multiway-merge process to this case. This is a fundamental property of
the merge process, and not a weakness of our algorithm. This difficulty can be overcome in a
number of ways to keep the running time low, depending on the application area of the basic
idea of the merge algorithm. For example, if we are interested in building a sorting network,
we can implement subnetworks based on recursively updating N to a smaller value M and
then merge M sequences of length M and repeat this recursion until
a single sequence is obtained.
In this paper our focus is developing sorting algorithms for product networks. Here
we assume the availability of a special sorting algorithm designed for the two-dimensional
version of the product network under consideration. In subsequent sections we discuss several
methods to obtain such algorithms as we consider more specific product networks. The
efficiency of that special algorithm has an important effect on the overall complexity of the
final sorting algorithm by the proposed approach. For all the cases considered here, it will
turn out that the resulting running time is either asymptotically optimal or close to optimal
when the number of dimensions is bounded.
3.3 Sorting Algorithm
Using the above algorithm, and an algorithm to sort sequences of length N 2 , it is easy to
obtain a sorting algorithm to sort a sequence of length N r , for r - 2.
First divide the sequence into subsequences of length N 2 and sort each subsequence
independently. Then, apply the following process until only one sequence remains:
1. Group all the sorted sequences obtained into sets of N sequences each as in Figure 1.
(If we are sorting N r keys, then initially there will be N r\Gamma3 groups, each containing N
sorted sequences of length N 2 .)
2. Merge the sequences in each group into a single sorted sequence using the algorithm
shown in the previous section. If now there is only one sorted sequence then terminate.
Otherwise go to step 1.
4 Implementation on Homogeneous Product Networks
Here we mainly focus on the implementation of the multiway-merge algorithm on a k-dimensional
product network PG k in detail. The sorting algorithm trivially follows from
the merge operation as described above. The initial scenario is N sorted sequences, of
stored on the N subgraphs [u]P G k
of PG k in snake order. Before the
sorting algorithm starts each processor holds one of the keys to be sorted. During the
sorting algorithm, each processor needs enough memory to hold at most two values being
compared. Throughout the discussions, the steps of implementation are illustrated by a
three-dimensional product of some graph G of nodes. The interconnection pattern of
G is irrelevant for this discussion.
Step 1: This step does not need any computation or routing. Recall from Section 2 that
each of the subgraphs [u; v]PG k;1
k\Gamma2 of [u]P G k
contains a subsequence of keys sorted in snake
dimension 3
dimension 2
dimension 1

Figure

8: Initial situation on the example 3-dimensional product graph.
(a)
dimension 1
dimension 3
dimension 2
(b)
dimension 1
dimension 3
dimension 2

Figure

9: Step 2 of the multiway-merge algorithm.
order, and that the positions of the keys in that subsequence with respect to the total sorted
sequence are v, Therefore, the sequence B u;v
is already stored on the subgraph [u; v]PG k;1
k\Gamma2 , sorted in snake order.
This is illustrated in Figure 8, where the three sequences to be merged are available
in snake order on the three subgraphs formed by removing the edges of dimension-3. The
subgraph [0]P G 3
(leftmost subgraph in Figure 8) contains A 0 , the subgraph [1]P G 3
(center
contains A 1 , and the subgraph [2]P G 3(rightmost subgraph) contains A 2 . In this
example, each B u;v contains only N keys, which fit in just one G subgraph. In general, B u;v
will be available in snake order on [u; v]PG k;1
k\Gamma2 . In this example, they are at [u; v]PG 3;1
which really correspond to G-subgraphs at dimension 2 (i.e. columns of Figure 8).
Step 2: This step is implemented by merging together the sequences on subgraphs [u; v]PG k;1
with the same u value into one sequence on [v]P G 1
2, the merging is done
by directly sorting with an algorithm for PG 2 . If step is done by a recursive
call to the multiway-merge algorithm, where each subgraph [v]P G 1
merges the sorted
dimension 3
dimension 2
dimension 1

Figure

10: Step 3 of the multiway-merge algorithm.
sequences stored on their [u; v]PG k;1
subgraphs.
We illustrate this step in Figure 9. For clarity, we first show the initial situation in

Figure

9.(a). This is same as the situation in Figure 8, but dimensions 1 and 3 are exchanged
to show the subsequences that will be merged together more explicitly. The B u;v sequences
to be merged together are the columns of Figure 9.(a). The result of merging is shown in

Figure

9.(b). Each C v is sorted in snake order and is found in the subgraph [v]P G 1Step 3: This step is directly done by reintroducing the dimension-1 connections of PG k
and reading the keys in snake order for the PG k graph. No movement of data is involved
in this step. We explicitly show the resulting sequence for our example in Figure 10 by
switching dimensions 1 and 3 in Figure 9.(b). The reader can observe from Figure 10 that
the keys now appear to be close to a fully sorted order (compare Figure 10 with Figure 11.d
which shows the final sorted order). In fact, we know from Lemma 1 that in the case of
sorting zeroes and ones, we are left with a small dirty area. This implies that every key is
within a distance of N 2 from its final position.
Step 4: This last step cleans the potential dirty area. Recall that the 2-dimensional
subgraphs
2 of PG k can be identified by the group sequences
that an element g of [ ;  ]Q 2;1
k\Gamma2 identifies a unique PG 2 subgraph at dimensions f1; 2g, and
that these PG 2 subgraphs are ordered by the corresponding group sequence which defines
the snake order between subgraphs. In this step we independently sort the keys in each
subgraphs at dimensions f1; 2g, where the sorted order alternates for "consecutive"
subgraphs. Each subgraph is sorted in snake order by using an algorithm which we assumed
available for two dimensions. The result of this step is illustrated in Figure 11.(a).
We now perform two steps of odd-even transposition between the subgraphs. In the first
step, the keys on the nodes of the "odd" PG 2 subgraphs are compared with the keys on the
corresponding nodes of their "predecessor" subgraphs. The keys are exchanged if the key in
the predecessor subgraph is larger. Figure 11.(b) shows the result of this first step in our
example. The keys 3 and 2 in nodes (1; 2; 1) and (1; 2; 2) have been exchanged with two keys
both with value 4 in nodes (0; 2; 1) and (0; 2; 2).
In the second step of odd-even transposition, the keys on the nodes of the "even" PG 2
subgraphs are compared (and possibly exchanged ) with those of their predecessor subgraphs.

Figure

11.(c) shows the result of this second step. In this figure, the key 5 in node (2,0,0)
has been exchanged with the key 6 in node (1,0,0).
(a)
dimension 3
dimension 1
dimension 2
dimension 3
dimension 1
dimension 2
(b)3 4 4
dimension 3
dimension 1
dimension 2
(c)
dimension 3
dimension 1
dimension 2
(d)

Figure

11: Step 4 of the multiway-merge algorithm.
Finally, a sorting within each of the 2-dimensional subgraphs ends the merge process

Figure

11.(d)).
One point which needs to be examined in more detail here is that, depending on the
graph G, the nodes holding the two keys that need to be compared and possibly
exchanged with each other may or may not be adjacent in PG k . If G has a Hamiltonian
path, then the nodes of G can be labeled in the order they appear on the Hamiltonian path
to define the sorted order for G. Then, the two steps of odd-even transposition are easy to
implement since they involve communication between adjacent nodes in PG k .
If, however, G is not Hamiltonian (e.g. a complete binary tree), the two nodes whose keys
need to be compared may not be adjacent, but they will always be in a common G subgraph.
In this case permutation routing within G may be used to perform the compare-exchange
step as follows: First, two nodes that need to compare their keys send their keys to each
other. Then, depending on the result of comparison, each node can either keep its original
key if the keys were already in correct order, or they drop the original key and keep the new
were out of order. To cover the most general case in the computation of running
time below, we will assume that G is not Hamiltonian, and thus we will implement these
compare-exchange steps by using permutation routing algorithms. We will see that whether
or not G is Hamiltonian only effects the constant terms in the running time complexity
function.
4.1 Analysis of Time Complexity
To analyze the time taken by the sorting algorithm we will initially study the time taken by
the merge process on a k-dimensional network. This time will be denoted as M k (N ). Also
denote the time required for sorting on PG 2 and R(N) denote the time required
for a permutation routing on G.
Lemma 3 Merging N sorted sequences of N k\Gamma1 keys on PG k takes M k
steps.
Proof: Step 1 does not take any computation time. Step 2 is a recursive call to the merge
procedure for dimensions, and hence will take M k\Gamma1 (N) time. Step 3 does not take any
computation time. Finally, step 4 takes the time of one sorting on PG 2 , two permutation
routings on G (for the steps of odd-even transposition), and one more sorting on PG 2 .
Therefore, the value of M k (N) can be recursively expressed as:
with initial condition
that yields
We can now derive the value of S r (N ).
Theorem 1 For any factor graph G, the time complexity of sorting N r keys on PG r is
Proof: By the algorithm of Section 3.2 the time taken to sort N r keys on PG r is the time
taken to sort in a 2-dimensional subgraph and then merge blocks of N sorted sequences into
increasing number of dimensions. The expression of this time is as follows:
r
never smaller than R(N ), the time obtained is S r
O(r
The following corollary presents the asymptotic complexity of the algorithm and one of
the main results of this paper.
Corollary 1 If G is a connected graph, the time complexity of sorting N r keys on PG r is
at most
Proof: To prove the claim, we first compute the complexity of sorting by our algorithm
on the r-dimensional torus. Then we refer to a result in [8] that showed that if G is a
connected graph, PG r can emulate any computation on the N r -node r-dimensional torus by
embedding the torus into PG r with dilation 3 and congestion 2. Since this embedding has
constant dilation and congestion, the emulation has constant slowdown [14]. (In fact, the
slowdown is no more than 6, and needed only when G does not have a Hamiltonian cycle).
Finally, we use these slowdown values to compute the exact running time for PG r
Now we compute the complexity of sorting on the r-dimensional torus. We basically
need a sorting algorithm from the literature that sorts N 2 keys in two-dimensional torus in
snake order. We also need an algorithm for permutation routing on the N-node cycle. For
example, we can use the sorting algorithm proposed by Kunde [15], which has complexity
It is also known that any permutation routing can be done on the N-node
cycle in no more than N=2 steps. Hence, we can sort on the N r -node r-dimensional torus in
at most 3(r \Gamma 1) steps.
Since the emulation of this algorithm by PG r requires a slowdown factor of at most 6, any
arbitrary N r -node r-dimensional product network can sort with complexity
5 Application to Specific Networks
In this section we obtain the time complexity of sorting using the multiway-merge sorting
algorithm presented for several product networks in the literature. To do so, we obtain upper
bounds for the values of S 2 (N) and R(N) for each network. Using these values in Theorem
will yield the desired running time.
Grid: Schnorr and Shamir [29] have shown that it is possible to sort N 2 keys on a N 2 -node
2-dimensional grid in 3N+o(N) time steps. It is also trivial to show that the time to perform
a permutation on the N-node linear array is at most R(N) These values of S 2 (N)
and R(N) imply that our algorithm will take at most 4(r \Gamma 1)
steps to sort N r keys on an N r -node r-dimensional grid. If the number of dimensions, r, is
bounded, this expression simplifies to O(N ).
This algorithm is asymptotically optimal when r is fixed since the diameter of the grid
with bounded number of dimensions is O(N ), and a value may need to travel as far as the
diameter of the network. If r is not bounded, then the diameter of the N r -node grid is
which means that the running time of our algorithm is off the optimal value by at
most a factor of r.
Mesh-connected trees (MCT): This network was introduced in [9] and extensively
studied in [8]. It is obtained as the product of complete binary trees. Due to Corollary 1 we
can sort on the N r -node r-dimensional mesh-connected trees in O(r 2 N) time steps. If r is
bounded, we again have O(N) as the running time.
This running time is asymptotically optimal when r is fixed, because the bisection width
of the N r -node r-dimensional MCT is O(N r\Gamma1 ), as shown in [8], and in the worst case we
may need to move \Omega\Gamma N r ) values across the bisection of the network. When r is not fixed,
the algorithm is off the bisection-based lower bound by a factor of r 2 . The diameter-based
lower bound used above for grids does not help to tighten this lower bound any further,
because the diameter of the MCT is logarithmic in the number of nodes [8]. It appears
interesting to investigate if it is possible to sort with lower running time than O(r 2 N) when
r is not bounded. If such an algorithm exists, it must use a completely different approach
than ours, because the value of S 2 (N) in Theorem 1 cannot be less than O(N) due to the
O(N) bisection width of the two-dimensional MCT network.
Hypercube: The hypercube has fixed 2. It is not hard to sort in snake order on
the two-dimensional hypercube in 3 steps. A permutation routing on the one-dimensional
hypercube takes only one step. Therefore, the time to sort on the hypercube with our
algorithm is running time is same as the running
time of the well-known Batcher odd-even merge algorithm for hypercubes. In fact, Batcher
algorithm is a special case of our algorithm.
Petersen Cube: The Petersen cube is the r-dimensional product of the Petersen graph,
shown in Figure 12. The Petersen graph contains 10 nodes and consists of an outer 5-cycle
and an inner 5-cycle connected by five spokes. Product graphs obtained from the Petersen
graph are studied in [25]. Like the hypercube, the product of Petersen graphs has fixed
N , and therefore the only way the graph grows is by increasing the number of dimensions.
Since the Petersen graph is Hamiltonian, its two-dimensional product contains the
two-dimensional grid as a subgraph. Thus, we can use any grid algorithm for sorting 100
keys on the two-dimensional product of Petersen graphs in constant time. Consequently,
the r-dimensional product of Petersen graphs can time. The constant
involved is not small, but it is not going to be unreasonably large either. It may very well

Figure

12: Petersen graph.
be possible to improve this constant by developing a special sorting algorithm for the two-dimensional
product of Petersen graphs. This is, however, outside the scope of this paper.
Product of de Bruijn and shuffle-exchange networks: To sort on their two-dimensional
instances we can use the embeddings of their factor networks presented in [9] which have
small constant dilation and congestion. In particular, a N 2 -node shuffle-exchange network
can be embedded into the N 2 -node 2-dimensional product of shuffle-exchange networks with
dilation 4 and congestion 2. Also a N 2 -node de Bruijn network can be embedded into the
2-dimensional product of de Bruijn networks with dilation 2 and congestion 2. Sorting
on the N 2 -node shuffle-exchange or de Bruijn networks can be done in O(log 2 n)
time by using Batcher algorithm [30]. Thus, we can sort on the N 2 -node 2-dimensional product
of shuffle-exchange or de Bruijn network by emulation of the N 2 -node shuffle-exchange
or de Bruijn network in S 2 steps. Using this in Theorem
1, our algorithm will take O(r 2 log 2 N) time steps to sort N r keys. Again, if r is bounded the
expression simplifies to O(log 2 N ). If r is not bounded, the running time of our algorithm is
asymptotically the same as the running time of sorting N r keys on the N r -node de Bruijn
or shuffle-exchange graphs by Batcher algorithm. Here again, we come across an interesting
open problem, to see if it is possible to sort on products of these networks in asymptotically
less time for unbounded number of dimensions.
6 Conclusions
In this paper we have presented a unified approach to sorting on homogeneous product
networks. To do so, we present an algorithm based on a generalization of the odd-even
merge sorting algorithm [2]. We obtain O(r 2 N) as an upper bound on the complexity of
sorting on any product network of r dimensions and N r nodes.
The time taken by the sorting algorithm on the grid and the mesh-connected trees with
bounded number of dimensions is O(N ), which is optimal. On the hypercube the algorithm
takes O(r 2 reaching the asymptotic complexity of the odd-even merge sorting
algorithm on the hypercube.
On other product networks our algorithm has the same running time as those of other
comparable networks. For instance, on the product of de Bruijn or shuffle-exchange graphs
the running time is O(r 2 log 2 N ). This is asymptotically the same as the running time of
Batcher algorithm on the N r -node shuffle-exchange or de Bruijn graphs.
From a theoretical point of view, it will be interesting to investigate if there are better
algorithms for product networks when r is not bounded. Several interesting alternatives
appear to be feasible, although we have not had the time to investigate them. For instance,
we could try to generalize the hypercube randomized algorithms for product networks.



--R

"Network Complexity of Sorting and Graph Problems and Simulating CRCW PRAMS by Interconnection Networks,"
"Sorting Networks and their Applications,"
"On Bitonic Sorting Networks,"
"A Unified Framework for Off-Line Permutation Routing in Parallel Networks,"
"A Comparison of Sorting Algorithms for the Connection Machine CM-2,"
"Deterministic Sorting in Nearly Logarithmic Time on the Hypercube and Related Computers,"
"Improved Divide/Sort/Merge Sorting Network,"
"Computational Properties of Mesh Connected Trees: Versatile Architecture for Parallel Computation,"
"Products of Networks with Logarithmic Diameter and Fixed Degree,"
"A General Framework for Developing Adaptive Fault-Tolerant Routing Algorithms,"
Homogeneous Product Networks for Processor Interconnection.
"Some Improvements in Non-Adaptative Sorting Algorithms,"
Searching and Sorting
"Work-Preserving Emulations of Fixed-Connection Networks,"
"Optimal Sorting on Multi-Dimensionally Mesh-Connected Computers,"
"A Multiway Merge Sorting Network,"
"On Sorting Multiple Bitonic Sequences,"
Introduction to Parallel Algorithms and Architectures: Arrays
"Tight Bounds on the Complexity of Parallel Sorting,"
"A Modulo Merge Sorting Network,"
"A Generalized Bitonic Sorting Network,"
"Bitonic Sort on a Mesh-Connected Parallel Computer,"
"K-Way Bitonic Sort,"
"Efficient VLSI Networks for Parallel Processing Based on Orthogonal Trees,"
"The Folded Petersen Network: A New Communication- Efficient Multiprocessor Topology,"
"Constructing Sorting Networks from k-Sorters,"
"The Cube-Connected Cycles: A Versatile Network for Parallel Computation,"
"Product-Shuffle Networks: Toward Reconciling Shuffles and Butter- flies,"
"An Optimal Sorting Algorithm for Mesh Connected Com- puters,"
"Parallel Processing with the Perfect Shuffle,"
"Sorting on a Mesh-Connected Parallel Computer,"
"A Parallel Sorting Scheme whose Basic Operation Sorts n Elements,"
"An Economical Construction for Sorting Networks,"
--TR

--CTR
Yuh-Shyan Chen , Chih-Yung Chang , Tsung-Hung Lin , Chun-Bo Kuo, A generalized fault-tolerant sorting algorithm on a product network, Journal of Systems Architecture: the EUROMICRO Journal, v.51 n.3, p.185-205, March 2005
Shan-Chyun Ku , Biing-Feng Wang , Ting-Kai Hung, Constructing Edge-Disjoint Spanning Trees in Product Networks, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.213-221, March
product networks;odd-even merge;algorithms;interconnection networks;sorting