Universal Wormhole Routing.
AbstractIn this paper, we examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in $O\left( {cd\eta +cL\eta \,\,{\rm log}\,\,P} \right)$ time with high probability, where L is the number of flits in a packet, and only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area (A) can simulate wormhole routing on any network of comparable area with O(log3A) slowdown, when all worms have the same length. Variable-length worms are also considered. We run some simulations on the fat-tree which show that not only does wormhole routing tend to perform better than the more heavily studied store-and-forward routing in this context, but that performance superior to our provable bound is attainable in practice.
Introduction
An efficient routing algorithm is critical to the design of
most large-scale general-purpose parallel computers. One
must move data between different locations in an appropriate
routing network as quickly as possible and with as little
queuing hardware as possible. Store-and-forward routing
is the most extensively studied model and many asymptotically
efficient algorithms have been proposed for this
model (e.g., [15] and the references therein). Recently, increasing
attention has been devoted to the wormhole routing
model [3], since it can lead to a reduction in routing
time and the storage requirements of intermediate nodes.
In this model, packets (or worms) are composed of flits or
flow control digits, and packets snake through the network
one flit after another.
Few works have performed any theoretical analysis of
This work was supported in part by the National Science Foundation
under grants CCR-9109550and CCR-9321388and by a Summer Research
Award from the University of Maryland Office of Graduate Studies and
Research.
R. I. Greenberg is with the Department of Mathematical and Computer
Sciences Loyola University, 6525 N. Sheridan Rd., Chicago, IL 60626,
rig@math.luc.edu.
H-C. Oh is with the Department of Information Engineering, Korea
University, Chochiwon, Korea, hyeong@tiger.korea.ac.kr.
wormhole routing or similar schemes. Leighton [17] performs
average-case analysis of greedy cut-through routing
on meshes. But cut-through routing [13] differs from
wormhole routing in that it uses buffers that can store at
least one full packet rather than a few flits. Makedon and
Simvonis [20] give worst case bounds for cut-through routing
of permutations on the mesh and the torus. Aiello,
Leighton, Maggs, and Newman [1] give an efficient algorithm
for wormhole routing of permutations on a dilated
butterfly. Their algorithm is nonoblivious (may use information
about other packets when routing a given packet).
More recently, Felperin, Raghavan, and Upfal [6] have obtained
a simple, oblivious algorithm for wormhole routing
of permutations on the butterfly and the mesh. Some other
works have described iterative methods for estimating the
performance of certain networks under certain probabilistic
models of message generation [4, 11, 2].
While the above analyses of wormhole routing have been
applicable only to specific networks and/or specific message
patterns, this paper takes a more general approach based
on summary measures of the message traffic, as in [16, 15].
We require only that any two paths in the network intersect
in at most a constant number of contiguous sequences
of edges, a condition that is met by many networks used
in practice. Recently, an intermediately broad class of networks
has been considered by Ranade et. al. with particular
application to improved routing of certain message distributions
on the butterfly [26].
After deriving general bounds for wormhole routing, we
apply the results to the construction of area-universal net-
works. In particular, when worms have a fixed length,
a bounded-degree network (the butterfly fat-tree [9]) of
area using wormhole routing can simulate (on-line)
any network of comparable area with O(log 3
Though it has been proven that O(logA) slowdown suffices
in the store-and-forward routing model [15], such an
approach requires the universal network to queue full packets
at each intermediate node and similarly limits the type
of competing network that is considered. Also, the circuit-switching
scheme of [9] could actually be used as a wormhole
routing scheme, but with poorer overhead than we
show here, since the earlier scheme locks down a routing
path for more than the time required for a worm to pass.
We also extend the universality analysis to the case in
which worms have varying lengths. In this case, each processor
continuously generates and sends packets, where the
packet length L is a random variable with mean
and maximum value LM . With mild restrictions, we show
that a fat-tree network of area \Theta(A) can simulate any
network of comparable area with O
L) log 3 A

Before proceeding with the promised results, we give
more detail on the model and terminologies used through-out
this paper. We consider the routing of a set of P pack-
ets, each consisting of L flits. We follow the usual graph-based
processors and switches are nodes in
the graph and communication channels are represented by
edges. We make the usual assumption that unit time suffices
for a flit to cross any edge in the network (though
it would also be desirable to extend the analysis to general
edge delays as done in [10] for the store-and-forward
model). A flit is an atomic object, which at each time
step, either waits in a queue, or crosses an edge and enters
the edge queue at the end of that edge. (In store-and-
forward routing, packets are the atomic objects.) We call
this unit time step a flit-step, while the corresponding unit
time step for store-and-forward routing is a packet-step.
We restrict attention to bounded-degree networks, so the
time to make routing decisions at any given node does not
affect the asymptotic time bounds.
We may view the packet routing problem as being comprised
of two tasks, selecting a path through the network
for each packet and setting a schedule for when packets
move and wait. In the next section of this paper, we focus
on the second task. Of course, the selection of paths affects
the required routing time. For example, the maximum distance
d, in number of edges, traveled by any packet is a
lower bound on the routing time; this distance is often referred
to as the dilation in the literature. (It may be noted
that the dilation is typically at most as large as the network
diameter, but this is not necessarily so if some packets do
not traverse shortest paths.) Similarly, the routing time is
lower bounded by cL, where the congestion c is the maximum
over all edges of the number of packets that must
traverse the edge over the entire course of the routing.
Once the set of packet paths has been determined, we
can define a graph, D, which has a vertex for each edge of
the network and an edge (u; v) whenever there is a packet
path in which network edge v immediately follows network
edge u. We refer to this graph as the dependency graph.
We ensure that deadlock cannot occur by assuming that
the dependency graph of the paths is acyclic [3]. (Many
networks, e.g., leveled networks [15], have no cycle in D
for any set of packets, and there also are techniques for
breaking cycles [3]. In addition, there are adaptive routing
techniques for avoiding deadlock (e.g., see [5] and the references
therein), and our analysis can be applied to the set
of packet paths generated by such a technique.)
II A Simple wormhole routing algorithm
In this section, we give a simple delayed-greedy wormhole
routing algorithm and its theoretical analysis, when
all worms have the same length, L. Throughout this sec-
tion, we only consider a set of paths such that the channel
dependency graph is acyclic. We also assume that any two
paths in the network intersect in at most one contiguous
sequence of edges. (It will be easily seen that the results
are also valid as long as any two paths intersect in at most
a constant number of contiguous sequences of edges.) Each
node has a queue, for each input edge, which can store at
most one flit. It is sufficient for our analysis to have each
node scan its input queues in a fixed order and send out a
flit whenever the relevant outgoing edge is not occupied by
another worm.
We say that a worm W 0 blocks W at t if the edge to which
the head of W has to proceed at t is taken by W 0 . Worm
worm W at t, if at t, there is a delay chain of
W i is blocking worm W
other worm in the chain can move. Since we exclude any
possibility of deadlock, any blockage will end at some time.
Also, once worm W 0 delays worm W for at most L steps
(not necessarily consecutive), W 0 will not delay W again
because of our assumption that packet paths intersect in
at most one contiguous sequence of edges.
The basic routing algorithm we use is a delayed-greedy
approach similar to that of Felperin, Raghavan, and Upfal
[6]. The analysis here simplifies, clarifies, and generalizes
their argument. We begin with a worst-case bound on
routing time that holds with high probability and then give
a tighter bound on the expected time. (Throughout this
paper we use the term "high probability" in the standard
fashion that for any constant m, we can achieve probability
is an appropriate measure of problem
size. In particular we focus on achieving time bounds for
routing P packets with probability
for network simulation using networks of area A that hold
with probability O(1=A).) The starting point for both
results is the following core routing procedure, expressed
in terms of parameters k and T to be determined later:
Algorithm A Assign each packet an integral delay randomly
and uniformly from the interval [0; kcL \Gamma 1]. A
packet that is assigned delay i waits in its initial queue
for iT steps and then proceeds to its destination. We refer
to the time between (i \Gamma 1)T and iT in as the i-th phase. In
what follows, we assume T is large enough that worms dispatched
in different phases do not interfere with each other
and we analyze how large T needs to be for the worms dispatched
in a phase to actually get delivered before the end
of the phase.
We begin with a key lemma for bounding the tail of a
binomial distribution:
independent Bernoulli trials, each
with probability p of success. The probability that the number
of successes s is larger than the expectation p- is at
most
Proof. The probability is at most
s
s and the Lemma
follows through the use of Stirling's approximation to the
Now, we can prove a general lemma about the number of
delaying worms encountered during a specified set of edge
traversals of some set of worms:
Consider a set of worm paths comprising a total
of y edge traversals (by worm heads) that need to be accomplished
in some phase of Algorithm A, and let P (x; y)
be the probability that delays by x worms interfere with
that set of traversals. Then P (w; x) -
2.
Proof. We use induction on x and prove the result for each
value of x by using induction on y. The base cases are
trivial. For the induction step, we first consider y ? L and
focus on the first L edge traversals of a particular worm;
notice that they can be blocked by at most cL worms. If
none of those worms is launched in the current phase, then
just equal to P (x; y \Gamma L). Otherwise, let S be the
set of such worms launched in the current phase, and note
that there is a probability of at most
contains
worms, by using
kcL , and
In the worst case, all the worms in S could act as delaying
worms, and we must also worry about delays encountered
by those worms during traversal of up to
have not already been considered. (We need not consider
more than new edges for each worm in S, because
once a worm has traversed so many edges not already under
consideration, it has digressed far enough from the paths
originally under consideration as to have no further effect.)
Thus, for the induction step, we have
cL
cL
cL
For y - L, the additive term preceding the summation
above disappears, and we replace P
the final result still holds.
Now we can analyze the time after a worm is dispatched
in Algorithm A that is required to traverse all d of its links:
be the probability that a given worm
W requires at least 2d+Lz time to reach its destination under
Algorithm A. Then, P 0 (z) -
2.
Proof. For W to require 2d + Lz time to reach its desti-
nation, it must be delayed by d
z worms since any one
worm can delay W for at most L steps. The result follows
from Lemma 2.
We are now ready for the main analytical result:
Theorem 4 With any set of P packets
can be routed in O (cdj
probability.
Proof. We consider first the case of L - d. In this case,
we simply run Algorithm A with
the probability is
given worm is not delivered during the
phase in which it is dispatched (under the assumption that
all worms dispatched in previous phases have been deliv-
ered). This yields an overall probability of O(1=P ) that
there exists any worm that does not get delivered. (The
failure probability can be changed to any constant power
of 1=P by changing the constant k.) The total time for
the kcL phases of the algorithm is O(cdL+cL 2 log P ). For
use a modified version of Algorithm A with kcd
phases. Lemmas 2 and 3 still go through by replacing some
appearances of L with d in the proofs, so we can proceed
as above with and the
total routing time is O(cdL log P ) with high probability.
It is interesting to note that we can also obtain a better
expected routing time as well as the high probability result
above.
Theorem 5 Any set of packets can be routed in O(cdL)
expected time.
Proof. As in the proof of Theorem 4, we actually use
O(32ecj) phases in Algorithm A, where
Also, we initially run the algorithm with
and then run the whole algorithm through again with
etc. The high probability
result of Theorem 4 still holds because we at most double
the routing time through the process of building up
towards a high enough value of T . In addition, the expected
time per phase is at most
Lemma 3, which is O(d L). So the total expected time
is O(cj(d
We also have the following corollary to Theorem 4, which
is useful in Section A:
Corollary 6 When d - log P , any set of P packets can be
routed in O
flit-steps with high probability.
III Wormhole routing on fat-trees
Fat-trees constitute a class of routing networks for hard-
ware-efficient parallel computation [18, 9, 15]. Figure 1
shows a layout of one fat-tree variant using switches of
constant size. A fat-tree in this style is usually referred as
a butterfly fat-tree, of which a variation has been adopted
in the CM-5 supercomputer of Thinking Machines Corporation
[19]. In Figure 1, a set of N processors are placed at
the leaves, represented by circles; the squares are switches.
Each connection drawn between a pair of switches or a processor
and a switch represents a pair of oppositely directed
Fig. 1. A butterfly fat-tree.
links, each capable of transmitting one flit in unit time. We
call the link from parent to child a down link, and the other
an up link. The underlying structure of Figure 1 is a complete
4-ary tree. Each edge of the underlying tree consists
of a group of links, called a channel. We call the channel
from parent to child a down channel, and the other an up
channel. The number of links in a channel is called its ca-
pacity. An important measure of the difficulty of routing a
set of packets on a fat-tree is the load factor, the maximum
ratio of the number of packets traversing a channel to the
capacity of the channel. The load factor - is closely related
to the congestion c. We can always choose packet paths so
that
We select a shortest path for each packet. The dependency
graph for the paths selected in this way is free from
cycles, because no shortest path proceeds from a down
channel to any up channel. In fact, we can view the net-work
as being partitioned into two halves, a network of
up channels and a network of down channels, by duplicating
each switch. In the network comprised of these two
halves, any two paths intersect in at most two contiguous
sequences of edges. Hence the result of Section II can be
applied. (The bound on the number of steps during which
a given worm can delay another given worm only increases
from L to 2L.)
A Area-universality of fat-trees
A.1 worms with a fixed length
The algorithm analyzed in Section II allows us to extend
to the wormhole routing problem universality theorems
from [18, 9, 15, 7] which state that a universal fat-tree
of a given area (volume) can simulate (using circuit switching
or store-and-forward packet routing) any other routing
network of equal area (volume) with only a polylogarithmic
factor increase in the time required. Throughout this
section, we assume that all worms have a fixed length, L.
We construct a fat-tree on unit-size processors, which occupies
area linear in the number of processors, as in [7]. (It
is actually more reasonable to consider processors that are
larger than constant-size, but we bypass this complication,
since it can be handled as in [7, 8].) Then, a very simple
one-to-one mapping of a competing network's processors
to those of the fat-tree guarantees that any set of packets
delivered in one packet-step by a competing network of
comparable area does not induce too great a congestion on
the fat-tree, as is shown by the following lemma, adapted
from [7, Lemma 2.1]. (For example, in area A, we can construct
a mesh or H-tree on O(A) processors or a butterfly
on O(
A lg nodes and do a straightforward geometric
mapping to a fat-tree with A processors and appropriate
channel capacities.)
Lemma 7 Consider networks with unit-sized processors,
and let R be the set of all networks of area A. Then, there
exists a fat-tree F of area \Theta(A) such that any set of packets
delivered in one packet-step by a network in R induces a
congestion of O (log A) on F .
We can immediately extend this lemma to the case in
which the competing network uses wormhole routing; the
set of packets that move during any window of L flit-steps
in the competing network induce a congestion of O (log A).
Then we can state our universality result for wormhole
routing:
Theorem 8 A fat-tree F of area \Theta(A) can simulate any
network of area A with a factor of O
log 3 A
\Delta loss of run-time
efficiency, using on-line wormhole routing with high
probability.
Proof. Consider the set of packets that moves during L
flit steps in a competing network of area A. By extending
Lemma 7 as suggested above, we know that the congestion
created by this set of packets on a fat-tree of area \Theta(A) is
O (log A). Next we can restate Corollary 6 by substituting
A for P as long as the number of packets is polynomial in
A, as is true here. For a fat-tree, so the set
of packets can be delivered by F in O
flit-steps.
It should be noted that under some circumstances, we
can obtain an asymptotic bound that appears better than
the above by splitting each packet into flits and essentially
treating these flits as independent packets. Of course, we
must then attach complete addressing information to each
flit. If a flit is big enough to carry a full address, then we
can think of each flit as being transformed into a packet
of two flits and we could use the store-and-forward routing
scheme for leveled networks of Leighton et. al. [15] to
route the packets in O (cL
O (log A) overhead for fat-tree simulation. Of course, it is
unfair to compare this result with Theorem 8, because this
independent-flit approach would induce additional overhead,
such as increased storage in the intermediate nodes and the
overhead of splitting and reconstructing the packets.
A.2 worms with variable lengths
In this section, we consider the situation in which each
processor continuously generates and sends packets, where
the packet length L is a random variable with mean -
L,
variance oe 2
L , and maximum value LM .
The following lemma shows that, with realistic restric-
tions, the total length of a set of n packets is unlikely to
greatly deviate from its expected value.
Lemma 9 Let X be a random variable, with mean - and
variance oe 2 , and let Sn be the sum of n independent random
variables distributed as X. If 0 ! oe - ffl-, where ffl is a
constant and 0
at least
n .
Proof. The proof follows from the Tchebycheff inequality
Next, we note a simple corollary to Corollary
set of packets can be
routed, in O
flit-steps with high probability.
We assume that the standard deviation of the packet
length satisfies
L, for some constant ffl such that
1. This assumption is satisfied by the packet-
length distributions, generated in typical concurrent computing
applications, presented in the literature, e.g. [21].
When packets have varying lengths, the simulation overhead
becomes more complicated to analyze, because the
number of packets crossing a wire in competing networks
may vary from wire to wire during an interval of time. We
consider the situation in which each processor continuously
generates and sends packets during a time interval of length
L. In the following theorem, we extend the result of
Theorem 8 to this general setting:
Theorem 11 Consider competing networks with area A
in which processors continuously generate and send packets
during a time interval of length at least A -
L, and let LM be
bounded above by a polynomial in A. Then a fat-tree F of
area \Theta(A) can simulate any such network with a factor of
O
L) log 3 A
\Delta loss of runtime efficiency, using on-line
wormhole routing with high probability.
Proof. We break up the overall time period under consideration
and consider separately the worms delivered by the
competing network in consecutive time intervals of length
L. Then we determine the overhead with which any
set of message routed by any network during an interval I
of length T can be delivered by a fat-tree of comparable
area.
We construct a fat-tree on unit-size processors, as in Section
A.1. Next we recursively bisect the competing network
in the straightforward geometric fashion, as in [7, 8], and
match the parts obtained in this bisection to pieces of F
in accordance with the obvious recursive bisection of F .
We consider a piece, C, of area A 0 in the competing net-
work. Our construction of F guarantees that the channel
capacity, in F , corresponding to the perimeter of C is
O
We now consider the set of wires, S, connecting C to
the remaining part of the competing network. Let P 0 denote
the maximum, over all the wires in S, of the number
of worms crossing the wire during I. Since the sum
of the lengths of the P 0 packets cannot exceed T , we know
from Lemma 9 that P
with probability at least
A . Since the perimeter of C is O
the total number of worms crossing the wires in S during
T is O
. Thus the congestion induced, on
the channel in F , by the worms crossing the wires in S
is O (P 0 log A). By Corollary 10, all the worms routed by
the competing network during I can be delivered by F in
O
is the total number
of worms to be delivered.
by a polynomial in A, from which the theorem follows.
Simulation
This section investigates the practical performance of
wormhole routing algorithms on butterfly fat-trees. For
simplicity, we focus on the case in which all worms have a
fixed length L. (The overhead for fat-trees simulating other
networks is not much worse with variable length worms in
terms of provable bounds, and we expect the same to be
true in practice.)
B.1 Description of the butterfly fat-tree
We use the butterfly fat-tree with N processors in the
style of Figure 1. Each node has an address which is
expressed as a pair (l; a) of integers, where l represents
the level of the node in the butterfly fat-tree and a represents
the address of the node in that level. Let the
level of a node be its distance from the leaves. At the
0-th level (l = 0) are N processors which are addressed
from 0 to N \Gamma 1. In Figure 1, we arrange the processors
in a similar fashion to the shuffled row-major indexing
in [27]. These processors are connected to N=4 switches
at the 1-st level such that the processor at (0; a) is connected
to the switch (1; ba=4c). At the l-th level, for
switches. The connections
of a switch are determined by the switch's address as
follows: (l; a) is connected to (l
\Xi a
and (l
\Xi a
B.2 Routing algorithms and strategies
Algorithm STORE is a (delayed) greedy store-and-for-
ward routing algorithm. Each packet chooses an integral
delay randomly and uniformly from the interval [0; R \Gamma 1].
A packet that is assigned delay x waits in its initial queue
for x time steps and then proceeds to its destination. At
each step, each node scans its input queues once and sends
out available packets greedily (whenever the corresponding
output edge is idling and the queue at the end of that edge
is not full).
Algorithm WORM is a (delayed) greedy wormhole routing
algorithm. Each packet consists of L flits. Each packet
chooses an integral delay randomly and uniformly from the
interval packet that is assigned delay x waits in
its initial queue for xL log N time steps and then proceeds
to its destination. At each flit step, each node scans its
input queues once. If the flit is a head flit, the node sends
it out according to the flit's path only when the output
edge is not being used by any other packet and the queue
at the end of that edge is not full. If the flit is not a head
flit, the node sends it out to where the flit's head was sent
out, whenever the queue at the end of that edge is not full.
Algorithm UNIV is the universal store-and-forward routing
algorithm of [15] for leveled networks. In this scheme
packets choose a random priority from [1; R] that is used
to order the passage of packets through any given switch.
Algorithm SPLIT uses the independent-flit approach.
Each packet is split into flits which are treated as independent
packets and routed as in STORE . This approach
is also called the multipacket routing approach [14]. Note
that this approach requires a replication of addressing information
so that each of the independent packets can be
routed to the correct location.
In the butterfly fat-tree, there is more than one shortest
path between a pair of leaves. More specifically, at a
switch, a packet can take any one of two up links, when its
destination is not one of the leaves of the subtree rooted at
the switch. (There is no redundancy for down links.) We
can use this redundancy in selecting paths.
ffl Fixed-Path (FP) selection: For each packet, we select
a shortest path randomly and uniformly before the
packet leaves its source.
ffl Random-Path (RP) selection: When a packet needs
to go up, it selects an up link randomly. If the link is
blocked, the packet waits. The selection is oblivious,
i.e., each time a packet seeks to go up, it makes a
selection randomly.
ffl Greedy-Path (GP) selection: The packet seeking to go
up scans up links and chooses the first one which is not
blocked.
When more than one incoming packet is to be routed to
an outgoing link, the way of selecting one may affect the
results. The following schemes have been tested:
ffl Fixed-Order (FO) scan: At each time step, a switch
scans its incoming links in a fixed order and chooses
the first pertinent packet for each outgoing link.
ffl Random Round-robin (RR) scan: This scheme is similar
to FO scan, except that a switch selects the first
incoming link randomly and scans around from that
link.
ffl Farthest-First (FF) selection: In this scheme, a switch
scans its input queues in a RR fashion, except that priority
is given to packets heading to the farthest destinations
for up links, and packets from the farthest
sources for down links.
B.3 Simulation results
Since most real parallel computations tend to be dominated
by communication time, and algorithms typically can
be viewed as consisting of alternating phases of computation
and communication, we focus on the static injection
model. Here each processor has a fixed number of packets
to send, and we measure the time to deliver the full
set of messages. This scenario corresponds to the situation
analyzed theoretically in Section A.1, to which we compare
our empirical results, and constitutes an important
general model as argued in [28], for example. We consider
three communication patterns representative of the range
of likely patterns in real parallel computations:
ffl Random Instance: Each packet chooses a destination
randomly and uniformly.
Complement Permutation: Each processor (0; a) sends
a packet to processor (0; permutation
induces as high a congestion on the fat-tree as any
other permutation. The congestion created by this
permutation is
N=2.
ffl Many-to-1 Instance: Packets are sent from processors
processor (0;
and packets from processors (0;
are sent to processor (0; 0). This pattern gives us a
high congestion with the same number of
packets as for a permutation.
The random pattern is probably the most common in other
simulation studies and arises in many practical contexts.
For example, a recently studied variation on sample sort
begins by randomly redistributing the keys to be sorted [12].
We focus on this pattern in the graphical results presented
below. Permutations have also been included in our stud-
ies, however, since they comprise a common communication
primitive, but some are trivial, whereas the complement
is a natural permutation that presents a high conges-
tion. Finally, the many-to-1 pattern models the common
operations of broadcast or census, which involve "hot-spot
contention" that can give substantially different behavior
than more uniform traffic patterns [25].
Five network sizes have been considered:
256, 1024, 4096. For each run, we measure the maximum
communication latency which is the time elapsed after the
routing has begun until the tail of the last packet arrives at
its destination. In figures 2 - 5, each point represents the
average of runs. Error bars showing the 99% confidence
interval for the true average value of the maximum latency
are also included in Figure 2, but they are omitted from the
other plots to ease readability. In all cases where we draw
distinctions in performance, there is little or no overlap of
the error bars. We describe these plots and the principle
conclusions below; additional plots including other combinations
of routing strategies, different parameters (such as
queue size and worm size), and error bars can be found
in [22].
The queue size q of WORM was chosen experimentally.
For random instances, little was gained by increasing the
queue size beyond 2 flits, and this choice generally yielded
better performance than STORE with queues of any size
tested. In the following, we use queues for 2 flits in WORM ,
and queues for 1 packet in STORE . (STORE improves
somewhat with larger queues, but we are already using
more buffer space than for WORM .)
First, we compare STORE with UNIV . Even though
UNIV is known to achieve an asymptotically optimal time
of on fat-trees, the delayed greedy routing
algorithm STORE performed better than UNIV , for all of
the communication patterns considered. A comparison on
random instances is shown in Figure 2. The marked difference
here is somewhat surprising since both algorithms
use the same value of R and the use of random priorities
in UNIV seems intuitively somewhat similar to imposing
random initial delays.
We tested the effects of initial delays on the latency of
STORE and WORM . We found that the initial random
delays can decrease the latency, but we did not find any
cases in which they provided much advantage, so we do
not use them henceforth.50150250350450
max.
latency
Fig. 2. Performance of STORE (with RP and RR): Comparison with
UNIV . Both algorithms used
We also found that the average latency tends to depend
linearly on the worm size L. This is consistent with the observation
that the total number of packets which may delay
a given packet is not a function of L once L - d. There-
fore, except where otherwise noted, we do experiments for
only one worm size typical value in the
literature [24].

Figure

3 compares the path selection schemes for both
store-and-forward routing and wormhole routing. Adaptive
schemes significantly outperform the fixed-path scheme
for the cases we considered. Similar results were obtained
with the other packet selection schemes.
Using the best path selection scheme, RP, Figure 4 compares
the packet selection schemes. It shows that RR
slightly outperforms FO (by 4-8% for most cases). (FF
performed similarly to FO.) We henceforth show most of
our results with the RR and RP routing schemes. (The
GP-FO combination may also be a good choice, though
RP-RR outperforms it by 5-9% for STORE and 12-15%
for WORM with
we don't have to worry about the difficulty of implementing
good randomization schemes, and some programmers
prefer deterministic systems.)

Figure

5 compares two approaches for treating the flits in
a packet: ordinary wormhole and independent-flit (SPLIT )
approaches. The performance of SPLIT is pretty sensitive
to the selection of routing schemes. For example,
SPLIT with GP-FF uniformly outperforms SPLIT with
max.
latency
Fig. 3. Comparison of routing schemes on selecting paths in STORE and
WORM with RR scan.10002000300016 64 256 1024 4096
max.
latency
Fig. 4. Comparison of routing schemes on scanning input queues in
STORE and WORM with RP selection.
RP-FO, which was not observed for STORE . We found
that WORM with RP-RR outperforms SPLIT with RP-4008001200
max.
latency
Fig. 5. Comparison of routing schemes on treating flits: WORM (with
RP and RR) and SPLIT (with various strategies).
FO and SPLIT with GP-FF, and SPLIT with RP-RR performs
slightly better than WORM with RP-RR. This comparison
is, however, made without considering the addressing
information to be added to each individual flit in the
original packet. From Figure 5, we can expect that even a
slight increase in the number of flits sent by SPLIT (due
to the replication of addressing information) would cause
WORM to outperform SPLIT .

Table

I compares the average latencies of WORM and
STORE for various conditions. For all cases considered,
WORM outperforms STORE .
Finally, we investigated the experimental upper bound of
the (maximum) latency for WORM with RP-RR. Table II
summarizes, for the random instances, the average values
over runs of c and of latency divided by c. We sought
the best least-squares fit to the latency divided by c, in the
form of k log p
4 N for constants k and p. The best fit was
obtained with p - 0:22. It would be rash to conclude that
latency fits very closely to \Theta(cL log 0:22 N ), since we have
neglected lower order terms, and the network sizes used
may be too small to observe the proper asymptotic bound.
Nonetheless, it appears that performance superior to our
provable bound in Corollary 6 and close to the obvious
lower
is attainable for random instances
STORE-RP-RR WORM-RP-RR
random complement many-to-1 random complement many-to-1

Table

I. Average latency, in flit-steps, of the greedy store-and-forward (STORE with and the greedy wormhole (WORM with
and algorithms. Each value represents an average of independent experiments.
34.3 46.4

Table

II. The average values of c and of the latency divided by c, for
WORM with RP-RR. Each value represents independent experiments
with
in practice.



--R

Fast algorithms for bit-serial routing on a hypercube
Performance analysis of k-ary n-cube interconnection networks

A comprehensive analytical model for wormhole routing in multicomputer systems.
A necessary and sufficient condition for deadlock-free adaptive routing in wormhole networks
A theory of wormhole routing in parallel computers.
The fat-pyramid: A robust net-work for parallel computation
The fat-pyramid and universal parallel computation independent of wire delay
Randomized routing on fat-trees
Packet routing in networks with long wires.
A Performance Study of Wormhole Routed Networks Through Analytical Modeling and Experimentation.
A parallel sorting algorithm with an experimental study.
Virtual new computer communication switching technique

Randomized routing and sorting on fixed-connection networks
Packet routing and job-shop scheduling in O(congestion
Average case analysis of greedy routing algorithms on arrays.
Fat-trees: Universal networks for hardware-efficient supercomputing
The network architecture of the connection machine CM-5

A framework for adaptive routing in multicomputer networks.
Efficient Communication Schemes for massively Parallel Computers.

A critique of adaptive routing.
Hot spot contention and combining in multistage interconnection networks.
Nearly tight bounds for wormhole routing.
Sorting on a mesh-connected parallel computer
A bridging model for parallel compu- tation
--TR

--CTR
Cicerone , Gabriele Di Stefano , Michele Flammini, Static and dynamic low-congested interval routing schemes, Theoretical Computer Science, v.276 n.1-2, p.315-354, April 6, 2002
wormhole routing;packet routing;greedy routing;fat-tree interconnection network;area-universal networks;randomized routing