Solving Fundamental Problems on Sparse-Meshes.
AbstractA sparse-mesh, which has PUs on the diagonal of a two-dimensional grid only, is a cost effective distributed memory machine. Variants of this machine have been considered before, but none are as simple and pure as a sparse-mesh. Various fundamental problems (routing, sorting, list ranking) are analyzed, proving that sparse-meshes have great potential. It is shown that on a two-dimensional $n \times n$ sparse-mesh, which has $n$ PUs, for h-relations can be routed in $(h steps. The results are extended for higher dimensional sparse-meshes. On a $d$-dimensional $n \times \cdots \times n$ sparse-mesh, with h-relations are routed in $(6 \cdot (d - 1) / \epsilon - steps.
Introduction
On ordinary two-dimensional meshes we must accept that, due to their small
bisection width, for most problems the maximum achievable speed-up with n 2
processing units (PUs) is only \Theta(n). On the other hand, networks such as hypercubes
impose increasing conditions on the interconnection modules with increasing
network sizes. Cube-connected-cycles do not have this problem, but are
harder to program due to their irregularity. Anyway, because of a basic theorem
from VLSI lay-out [18], all planar architectures have an area that is quadratic
in their bisection-width. But this in turn means that, except for several special
problems with much locality (the Warshall algorithm most notably), we must
accept that the hardware cost is quadratic in the speed-up that we may hope to
obtain (later we will also deal with three-dimensional lay-outs). Once we have
accepted this, we should go for the simplest and cheapest architecture achieving
this, and a good candidate is the sparse-mesh considered in this paper.
Network. A sparse-mesh with n PUs consists of a two-dimensional n \Theta n grid
of buses, with PUs connected to them at the diagonal. The horizontal buses are
called row-buses, the vertical buses are called column-buses. PU i ,
send data along the i-th row-bus and receive data from the i-th column-bus. In
one step, PU i can send one packet of standard length to an arbitrary PU j . The
packet first travels along the i-th row-bus to position (i; j) and then turns into
the j-th column-bus. Bus conflicts are forbidden: the algorithm must guarantee
that in every step a bus is used for the transfer of only one packet. See Figure 1
for an illustration.
In comparison to a mesh, we have reduced the number of PUs from n 2 to
saving substantially on the hardware cost. In comparison with other
Max-Planck-Institut f?r Informatik, Im Stadtwald, Saarbr-ucken, Germany, jopsi@mpi-
sb.mpg.de, http://www.mpi-sb.mpg.de/-jopsi/.

Figure

1: A sparse-mesh with 8 PUs and an 8 \Theta 8 network of buses. The large
circles indicate the PUs with their indices, the smaller circles the connections
between the buses.
networks, we have a very simple interconnection network that can be produced
easily and is scalable without problem. The sparse-mesh is very similar to the
Parallel Alternating Direction Machine, PADAM, considered in [2, 3] and the
coated-mesh considered in [10]. Though similar in inspiration, the sparse-mesh
is simpler. In Section 6 the network is generalized for higher dimensions.
Problems. Parallel computation is possible only provided that the PUs can
exchange data. Among the many communication patterns, patterns in which
each PU sends and receives at most h packets, h-relations, have attracted most
attention. An h-relation is balanced, if every PU sends h=n packets to each PU.
Lemma 1 On a sparse-mesh with n PUs, balanced h-relations can be performed
in h steps.
Unfortunately, not all h-relations are balanced, and thus there is a need for
algorithms that route arbitrary h-relations efficiently. Also for cases that the PUs
have to route less than n packets, the above algorithm does not work. Offline,
all h-relations can be routed in h steps. The algorithm proceeds as follows:
Algorithm offline route
1. Construct a bipartite graph with n vertices on both sides. Add an edge
from Node i on the left to Node j on the right for each packet going from PU i
to PU j .
2. Color this h-regular bipartite graph with h colors.
3. Perform h routing steps. Route all packets whose edges got Color t, 0 -
h, in Step t.
This coloring idea is standard since [1]. Its feasibility is guaranteed by Hall's
theorem. As clearly at least h steps are required for routing an h-relation, the
offline algorithm is optimal. This shows that the h-relation routing problem is
equivalent to the problem of constructing a conflict-free bus-allocation schedule.
In [3] routing h-relations is considered for the PADAM. This network is so
similar to the sparse-mesh, that most results carry over. It was shown that
for h - n, h-relations can be routed in O(h) time. Further it was shown that
1-optimality can be achieved for log log n). Here and in the
remainder we call a routing algorithm c-optimal, if it routes all h-relations in at
most c \Delta
Other fundamental problems that should be solved explicitly on any network,
are sorting and list ranking. With h keys/nodes per PU, their communication
complexity is comparable to that of an h-relation. In [3], the list-ranking problem
was solved asymptotically optimally for log log n).
New Results. In this paper we address the problems of routing, sorting and
list ranking. Applying randomization, it is rather easy to route n ffl -relations,
(2=ffl)-optimally. An intricate deterministic algorithm is even (1=ffl)-
optimal. This might be the best achievable. We present a deterministic sampling
technique, by which all routing algorithms can be turned into sorting algorithms
with essentially the same time consumption. In addition to this, we give an algorithm
for ranking randomized lists, that runs in 6=ffl steps for lists
with nodes per PU. Our generalization of the sparse-mesh to higher-
dimensions is based on the generalized diagonals that were introduced in [6]. At
least for three dimensions this makes practical sense: n 2 PUs are interconnected
by a cubic amount of hardware, which means an asymptotically better ratio than
for two-dimensional sparse-meshes. On higher dimensional sparse-meshes everything
becomes much harder, because it is no longer true that all one-relations
can be routed in a single step. We consider our deterministic routing algorithm
for higher dimensional sparse-meshes to be the most interesting of the paper.
All results constitute considerable improvements over those in [3]. The results
of this paper demonstrate that networks like the sparse-mesh are versatile, not
only in theory, but even with a great practical potential: we show that for realistic
sizes of the network, problems with limited parallel slackness can be solved
efficiently. All proofs are omitted due to a lack of space.
Randomized Routing
Using the idea from [19] it is easy to obtain a randomized 2-optimal algorithm
for large h. The algorithm consists of two randomizations, routings in which the
destinations are randomly distributed. In Round 1, all packets are routed to
randomly chosen intermediate destinations; in Round 2, all packets are routed
to their actual destinations.
Lemma 2 On a sparse-mesh with n PUs, h-relations can be routed in 2 \Delta h+o(h)
steps, for all log n), with high probability.
We show how to route randomizations for
n). First the PUs
are divided into
subsets of PUs, S then we do the following:
Algorithm random route
1. Perform
In Superstep t,
its packets with destination in S (j+t) mod
p n to PU i
in S (j+t) mod
2. Perform
In Superstep t,
n, sends all its packets with destination in PU (i+t) mod
n in S j to
their destinations.
This approach can easily be generalized. For log n), the algorithm
consists of 1=ffl routing rounds. In Round r, 1 - r - 1=ffl, packets are routed to
the subsets, consisting of n 1\Gammaffl\Deltar PUs, in which their destinations lie.
Theorem 1 On a sparse-mesh with n PUs, random route routes randomizations
with log n) in (h probability. Arbitrary
h-relations can be routed in twice as many steps.
List ranking is the problem of determining the rank for every node of a set of
to the final node of its list. h denotes the number of nodes per PU.
The edges of a regular bipartite graph of degree m can be colored by splitting
the graph in two subgraphs log m times, each with half the previous degree [4].
Lev, Pippenger and Valiant [11] have shown that each halving step can be performed
by solving two problems that are very similar to list ranking (determining
the distance to the node with minimal index on a circle). Thus, if list-ranking
is solved in time T , then bipartite graphs of degree m can be colored in time
In [3] list ranking on PADAMs is performed by simulating a work-
optimal PRAM algorithm. For coloring the eges of a bipartite regular graph, the
above idea was used:
Lemma 3 [3] On a sparse-mesh with n PUs, list ranking can be solved in O(h)
steps, for all h - n \Delta log log n. A bipartite regular graph with h \Delta n edges, can be
colored in O(log(h \Delta n) \Delta h) steps.
The algorithms are asymptotically optimal, but the hidden constants are quite
bad, and the range of applicability is limited to large h. In the following we
present a really good and versatile randomized list-ranking algorithm. It is based
on the repeated-halving algorithm from [14]. This algorithm has the unique
property, that not only the number of participating nodes is reduced in every
round, but that the size of the processor network is reduced as well. Generally,
the value of this property is limited, but on the sparse-mesh, where we need a
certain minimal h for efficient routing, this is very nice.
3.1 Repeated-Halving
It is assumed that the nodes of the lists are randomly distributed over the PUs.
If this is not the case, they should be randomized first. The algorithm consists of
log n reduction steps. In each step, first the set of PUs is divided in two halves,
. The nodes in S 0 with current successor in S 1 and vice-versa, are
called masters, the other nodes are non-masters. The current successor of a node
is stored in its crs field. Each PU holds nodes.
Algorithm reduce
1. Each non-master p follows the links until a master or a final node is reached
and sets crs(p) to this node.
2. Each master p asks
3. Each master p asks
In a full algorithm one must also keep track of the distances. After Step 2, each
master in S i , points to the subsequent master in S (i+1) mod 2 . Thus,
after Step 3, each master in S i , points to the subsequent master in S i itself. Now
recursion can be applied on the masters. This does not involve communication
between S 0 and S 1 anymore. Details are provided in [14]. The expected number
of masters in each subset equals h \Delta n=4. Thus, after log n rounds, we have n
subproblems of expected size h=n, that can be solved internally. Hereafter, the
reduction must be reversed:
Algorithm expand
1. Each non-master p asks
For Step 1 of reduce we repeat pointer-jumping rounds as long as necessary.
In every such round, each node p who has not yet reached a master or a final
node, asks and the distance thereto. Normally pointer-
jumping is inefficient, but in this case, because the expected length of the lists
is extremely short, the number of nodes that participates decreases rapidly with
each performed round [16].
Theorem 2 On a sparse-mesh with n PUs, list ranking can be solved in 14 \Delta h+
o(h) steps, for all log n), with high probability.
For smaller h, the average number of participating nodes per PU decreases to
less than 1. This is not really a problem: for such a case, the maximum number
of participating nodes in any PU can easily be estimated on O(log n), and the
routing operations can be performed in O(log 2 n). In comparison to the the
total routing time, the cost of these later reduction rounds is negligible. Using
Theorem 1, this gives
Corollary 1 On a sparse-mesh with n PUs, list ranking can be solved in 14=ffl \Delta
log n), with high probability.
3.2 Sparse-Ruling-Sets
The performance of the previous algorithm can be boosted by first applying the
highly efficient sparse-ruling-sets algorithm from [13] to reduce the number of
nodes by a factor of !(1). We summarize the main ideas.
Algorithm sparse ruling sets
1. In each PU randomly select h 0 nodes as rulers.
2. The rulers initiate waves that run along their list until they reach the next
ruler or a final element. If a node p is reached by a wave from a ruler p 0 , then
3. The rulers send their index to the ruler whose wave reached them.
By a wave, we mean a series of sending operations in which a packet that is
destined for a node p is forwarded to crs(p). Hereafter, we can apply the previous
list-ranking algorithm for ranking the rulers. Finally each non-ruler p asks mst(p)
for the index of the last element of its list and the distance thereof. Details can
be found in [13], particularly the initial nodes must be handled carefully.
Theorem 3 On a sparse-mesh with n PUs, list ranking can be solved in 6=ffl \Delta
log n), with high probability. Under the
same conditions, a bipartite regular graph with h \Delta n edges, can be colored in
O(log(h steps.
4 Faster Routing
Our goal is to construct a deterministic O(1=ffl)-optimal algorithm for routing
-relations. As in [3], we apply the idea from [17] for turning offline routing
algorithms into online algorithms by solving Step 2 of offline route after
sufficient reduction of the graph online. However, here we obtain much more
interesting results.
log n), and define f by log n) 1=2 . As in random
route, we are going to perform 1=ffl rounds. In Round r, 1 - r - 1=ffl, all
packets are routed to the subsets, consisting of n 1\Gammaffl\Deltar PUs each, in which their
destinations lie. We describe Round 1. First the PUs are divided in n ffl sub-
each consisting of n 1\Gammaffl PUs. Then, we perform the following
steps:
Algorithm determine destination
1. Each PU i , its packets on the indices of their destination
subsets. The packets going to the same S j , are filled into
superpackets of size f \Delta log n, leaving one partially filled or empty superpacket
for each j. The superpackets p, going to the same S j , are numbered consecutively
and starting from 0 with numbers a p . ff ij denotes the total number of
superpackets going from S i to S j .
2. For each j, 0 the PUs perform a parallel prefix on the ff ij , to
make the numbers A
available in PU i ,
3. For each superpacket p in PU i ,
dest
For each superpacket p with destination in S j , dest p gives the index of the PU
in S j , to which p is going to be routed first. Because the PUs in S j are the
destination of h \Delta n 1\Gammaffl =(f \Delta log n)+n superpackets, the bipartite graph with n nodes
on both sides and one edge for every superpacket has degree h=(f \Delta log n)
Its edges can be colored in o(h) time. If the edge corresponding to a superpacket
gets Color t, 1 - t ! h=(f \Delta log n)+n ffl , then p is going to be routed in superstep
t.
Lemma 4 On a sparse-mesh with n PUs, and log n) all packets can
be routed to their destination subsets of size n 1\Gammaffl in h steps.
Repeating the above steps 1=ffl times, the packets eventually reach their destinations

Theorem 4 On a sparse-mesh with n PUs, h-relations with
can be routed in (h steps.
Our algorithm is not entirely deterministic: the underlying list-ranking algorithm
is randomized. It is likely that deterministic list-ranking for a problem
with nodes per PU can be performed in O(h=ffl) time. But, for our main
claim, that n ffl -relations can be routed (1=ffl)-optimally, we do not need this: if
n) the size of the superpackets can be taken f \Delta log 2 n, and we can
simply apply pointer-jumping for the list-ranking.
5 Faster Sorting
On meshes the best deterministic routing algorithm is more or less a sorting
algorithm [9, 8]. For sparse-meshes the situation is different: the routing algorithm
presented in Section 4 is in no way a sorting algorithm. However, it can
be enhanced to sort in essentially the same time.
We first consider log n). This case also gives the final round in the
sorting algorithm for smaller h hereafter. Define
log(n). In [15] it is shown how to deterministically select a
high-quality sample. The basic steps are:
Algorithm refined sampling
1. Each PU internally sorts all its keys and selects those with ranks j \Delta h=m,
m, to its sample.
2. Perform log n merge and reduce rounds: in Round r, 0 - r ! log n, the
samples, each of size m, in two subsets of 2 r PUs are merged, and only the
keys with even ranks are retained.
3. Broadcast the selected sample M of size m to all PUs.
Lemma 5 On a sparse-mesh with n PUs, refined sampling selects a sample
of size m in o(h) steps. The global rank, Rank p , of an element p, with rank rank p
among the elements of M satisfies
Thus, by merging the sample and its packets, a PU can estimate for each of its
packets p its global rank Rank p with an error bounded by O(h
This implies that if we set
dest
for each packet p, where rank p is defined as above, that then at most h
packets have the same dest-value. Thus all packets can be routed to the PU given
by their dest-values in h steps. Furthermore, after each PU has sorted all
the packets it received, the packets can be rearranged in o(h) steps so that each
PU holds exactly h packets.
Lemma 6 On a sparse-mesh with n PUs, the sorting algorithm based on refined
sampling sorts an h-relation in h
For log n), we stick close to the pattern of the routing algorithm
from Section 4: we perform 1=ffl rounds of bucket-sort with buckets of decreasing
sizes. . For each round of the bucket sorting, we
run refined sampling with log(n). This sample selection
takes steps. In Round r, 1 - r - 1=ffl, the sample is used to guess
in which subset of size n 1\Gammar=ffl each packet belongs. Then they are routed to these
subsets with the algorithm of Section 4.
Theorem 5 On a sparse-mesh with n PUs, the sorting algorithm based on refined
sampling sorts an h-relation in (h+o(h))=ffl steps, for all
The remark at the end of Section 4 can be taken over here: n) is
required for making the algorithm deterministic, but this has no impact on the
claim that (1=ffl)-optimality can be achieved for
6 Higher Dimensional Sparse-Meshes
One of the shortcomings of the PADAM [2, 3] is that it has no natural generalization
for higher-dimensions. The sparse-mesh can be generalized easily.
subset of a d-dimensional n \Theta \Delta \Delta \Delta \Theta n grid is a diagonal, if the
projection of all its points on any of the (d \Gamma 1)-dimensional coordinate planes is
a bijection.
For this we need the following definition (a simplification of the definition in [6]):
Diag
Lemma 7 [6] In a d-dimensional n \Theta \Delta \Delta \Delta \Theta n grid, Diag d is a diagonal.

Figure

2: A three-dimensional 4 \Theta 4 \Theta 4 PUs, such that if they
were occupied by towers in a three-dimensional chess game, none of them could
capture another one.
The d-dimensional sparse-mesh, consists of the n d\Gamma1 PUs on Diag d , inter-connected
by d \Delta n d\Gamma1 buses of length n. The PU at position
denoted PU x0 ;:::;x
. The routing is dimension-ordered. Thus, after t substeps,
d, a packet traveling from PU x0 ;:::;x
to PU x 0;:::;x 0
has reached position
The scheduling should exclude
bus conflicts. Diag 3 is illustrated in Figure 2.
6.1 Basic Results
Now it is even harder to find a conflict-free allocation of the buses. Different from
before, it is no longer automatically true, that every one-relation can be routed
offline in one step (but see Lemma 10!). For example, in a four-dimensional
sparse-mesh, under the permutation
at the positions (0; 0; x pass through position
(0; 0; 0; 0). However, for the most common routing pattern, balanced h-relations,
this is no problem, because it can be written as the composition of n shifts.
A shift is a routing pattern under which, for all x the packets in
have to be routed to PU (x0+s0 ) mod n;:::;(x
given s
Lemma 8 A shift in which each PU contributes one packets can be routed in
one step.
Lemma 8 implies that the randomized routing algorithm from Section 2 carries
on with minor modifications. One should first solve the case of large
log n) and then extend the algorithms to smaller
Theorem 6 On a d-dimensional sparse-mesh with n d\Gamma1 PUs, the generalization
of random route routes randomizations with log n) in (d \Gamma 1)
steps, with high probability. Arbitrary h-relations can be routed in twice
as many steps.
The algorithm for ranking randomized lists of Section 3 has the complexity of
a few routing operations, and this remains true. The same holds for our technique
of Section 5 for enhancing a routing algorithm into a sorting algorithm with the
same complexity. The only algorithm that does not generalize is the deterministic
algorithms of Section 4, because it is not based on balanced h-relations.
6.2 Deterministic Routing
In this section we analyze the possibilities of deterministic routing on higher-dimensional
sparse-meshes. Actually, for the sake of a simple notation, we describe
our algorithms for two-dimensional sparse-meshes, but we will take care
that they consist of a composition of shifts.
For log n), we can match the randomized result. The algorithm
is a deterministic version of the randomized one: it consists of two phases. In
the first phase the packets are smoothed-out, in the second they are routed to
their destinations. Smoothing-out means rearranging the packets so that every
PU holds approximately the same number of packets with destinations in each
of the PUs. Let
Algorithm deterministic route
1. Each PU i , its packets on the indices of their
destination PU. The packets going to the same PU j ,
superpackets of size f \Delta log n, leaving one partially filled or empty superpacket
for each j.
2. Construct a bipartite graph with n nodes on both sides, and an edge from
Node i on the left to Node j on the right, for every superpacket going from
PU i to PU j . Color this graph with (f colors. A superpacket p with
Color dest
3. Perform shifts. In Shift t, routes the
dest to PU (i+t) mod n .
4. Perform shifts. In Shift t, routes the
with destination in PU (i+t) mod n to this PU.
The algorithm works, because the coloring assures that for each source and destination
PU there are exactly f +1 packets with the same dest-value. This implies
that both routings are balanced.
Theorem 7 On a d-dimensional sparse-mesh with n d\Gamma1 PUs deterministic
route routes h-relations with steps.
For smaller h, ideas from deterministic route are combined with ideas
from random route: the algorithm consists of rounds in which the packets
are smoothed-out and then routed to the subsets in which their destinations lie.
The fact that this second phase must be balanced, implies that the smoothing
must be almost perfect. Another essential observation is that if packets are
redistributed among subsets of PUs, and if this routing has to be balanced, that
then the number of subsets should not exceed h. Let log n), and set
. The PUs are divided in n ffl subsets S i of n 1\Gammaffl PUs each. Then all
packets are routed to the subset in which their destinations lie, by performing
Algorithm deterministic route
1. Each PU i , its packets on the indices of their
destination PU. The packets going to the same S j , are filled into
superpackets of size f \Delta log n, leaving one partially filled or empty superpacket
for each j.
2. Construct a bipartite graph with n ffl nodes on both sides, and an edge from
Node i on the left to Node j on the right, for every superpacket going from
S i to S j . Color this graph with (f colors. For a superpacket p with
Color
3. In each S i , the rank, rank p , of
each packet p with dest among the packets p 0 with dest
4. Rearrange the packets within the S i , , such that thereafter a
packet p with rank stands in PU j mod n 1\Gammaffl of S i .
5. Perform shifts. In Shift t,
routes the f dest to
PU i in S (j+t) mod n ffl .
6. In each S i , the rank, rank p ,
of each packet p with destination in S j among the packets with destination in
this subset.
7. Rearrange the packets within the S i , , such that thereafter a
packet p with rank stands in PU j mod n 1\Gammaffl of S i .
8. Perform shifts. In Shift t,
routes the f with destination in S (j+t) mod n ffl
to PU i in this subset.
The ranks can be computed as in Section 4 in O(n ffl \Delta log steps. The
coloring guarantees that
Lemma 9 After Step 4, for each j, 0 every PU holds exactly f
superpackets p with dest
holds exactly f with destination in S j .
The rearrangements within the subsets are routings with a large h as described
by Theorem 7 (the superpackets do not need to be filled into supersuperpackets!),
and thus they can be performed without further recursion.
Theorem 8 On a d-dimensional sparse-mesh with n d\Gamma1 PUs deterministic
route routes h-relations with log n) in (6
steps.
From an algorithmic point of view deterministic route is the climax of the
paper: all developed techniques are combined in a non-trivial way, to obtain a
fairly strong result. As in Section 4, n) is required for also making
the coloring deterministic.
6.3 Three-Dimensional Sparse-Meshes
Three-dimensional sparse-meshes are practically the most interesting generaliza-
tion. It is a lucky circumstance that for them even the results from Section 4
carry on, because of the following
On a three-dimensional sparse-mesh, each one-relation can be routed
in a single step.
Proof: The permutation is a composition of OE corrects the
ith coordinate. OE 0 maps a position Diag 3 to a position
The injectivity of the projection on the plane x carries over to OE 0 . Thus,
after OE 0 , no two packets stand in the same position. Analogously, it follows that
the inverse of OE 2 , is an injection. Thus, not even at the beginning of OE 2 , that is
after OE 1 , two packets may have been sharing a position.
leads to the following analogue of Theorem 4:
Theorem 9 On a three-dimensional n \Theta n \Theta n sparse-mesh, h-relations with
log n) can be routed in (2 steps.
The coated-mesh [10] can be trivially generalized for higher dimensions. How-
ever, whereas routing on a two-dimensional coated-mesh is almost as easy as on
a sparse-mesh, there is no analogue of Lemma 10 for three-dimensional coated-
meshes.
7 Conclusion
Our analysis reveals that the sparse-mesh has a very different character than the
mesh. Whereas on a mesh several approaches essentially give the same result, we
see that on a sparse-mesh, there is a great performance difference. For
column-sort performs poorly, because the operations in subnetworks are costly,
while on a mesh they are for free. On a mesh also the randomized algorithm
inspired by [19] performs optimal [12, 7], because there the worst-case time consumption
is determined by the time the packets need to cross the bisection. For
the sparse-mesh this argument does not apply, and our deterministic routing
algorithm is twice as fast.



--R

'A Unified Framework for Off-Line Permutation Routing in Parallel Networks,' Mathematical Systems Theory


'On Edge Coloring Bipartite Graphs,' SIAM Journal on Computing
An Introduction to Parallel Algorithms

'Randomized Multipacket Routing and Sorting on Meshes,' Algorithmica


'Work-Optimal Simulation of PRAM Models on Meshes,' Nordic Journal of Computing
'A Fast Parallel Algorithm for Routing in Permutation Networks,' IEEE Transactions on Computers
'k-k Routing, k-k Sorting, and Cut-Through Routing on the Mesh,' Journal of Algorithms



'From Parallel to External List Ranking,' Techn.
Permutation Routing and Sorting on Meshes with Row and Column Buses


--TR

--CTR
Martti Forsell, A parallel computer as a NOC region, Networks on chip, Kluwer Academic Publishers, Hingham, MA,
routing;theory of parallel computation;algorithms;meshes;sorting;networks;list-ranking