A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks.
The theoretical background for the design of deadlock-free adaptive routing algorithmsfor wormhole networks is developed. The author proposes some basic definitions and twotheorems. These create the conditions to verify that an adaptive algorithm isdeadlock-free, even when there are cycles in the channel dependency graph. Two designmethodologies are also proposed. The first supplies algorithms with a high degree offreedom, without increasing the number of physical channels. The second methodology isintended for the design of fault-tolerant algorithms. Some examples are given to show theapplication of the methodologies. Simulations show the performance improvement thatcan be achieved by designing the routing algorithms with the new theory.
Introduction
Multicomputers [1] rely on an interconnection network between processors to
support the message-passing mechanism. The network latency [1] can be defined
as the time from when the head of a message enters the network at the
source until the tail emerges at the destination. In first generation multicom-
puters, a store-and-forward mechanism has been used to route messages. Each
time a message reaches a node, it is buffered in local memory, and the processor
interrupted to execute the routing algorithm. Accordingly, the network
latency is proportional to the distance between the source and the destination.
However, second generation multicomputers are most distinguished by message
routing hardware that makes the topology of the message-passing network
practically invisible to the programmer. The message routing hardware uses a
routing mechanism known as wormhole routing [10]. As messages are typically
at least a few words long, each message is serialized into a sequence of parallel
data units, referred to as flow control units, or flits [9]. The flit at the head of
a message governs the route. As the header flit advances along the specified
route, the remaining flits follow it in a pipeline fashion. If the header encounters
a channel already in use, it is blocked until the channel is freed; the flow
control within the network blocks the trailing flits.
This form of routing and flow control has two important advantages over
the store-and-forward routing used in first generation multicomputers. Firstly,
it avoids using storage bandwidth in the nodes through which messages are
routed. Secondly, this routing technique makes the message latency largely
insensitive to the distance in the message-passing network. Since the flits move
through the network in a pipeline fashion, in the absence of channel contention,
the network latency equals the sum of two terms:
d is the time associated with forming the path through the network,
where T p is the delay of the individual routing nodes found on the path, and d
is the number of nodes traversed.
- L=B is the time required for a message of length L to pass through a
channel of bandwidth B.
In second generation multicomputers, the network latency is dominated by
the second term for all but very short messages.
Another improvement in message performance results from selecting the
optimal topology for the implementation on printed circuit boards or VLSI
chips. As message latency is dominated by the term L=B, more wirable net-work
topologies will increase the bandwidth B at the expense of increasing
the network diameter. An analysis [5, 7] shows that, under the assumption of
constant number of wires through the network bisection, a two dimensional net-work
minimizes latency for typical message lengths for up to 1024 nodes. For
larger sizes, a three dimensional network achieves better performance. Among
these networks, meshes are preferred because they offer useful edge connectiv-
ity, which can be used for I/O controllers. Also, meshes partition into units
that are still meshes, simplifying the design of routing algorithms that are independent
of the network size, as well as the implementation of space-sharing
techniques.
However, deadlocks may appear if the routing algorithms are not carefully
designed. A deadlock in the interconnection network of a multicomputer occurs
when no message can advance toward its destination because the queues of the
message system are full. The size of the queues strongly influences the probability
of reaching a deadlocked configuration. First generation multicomputers
buffer full messages or relatively large packets. By contrary, second generation
machines buffer flits, being more deadlock-prone. So, the only practical way
to avoid deadlock is to design deadlock-free routing algorithms.
Many deadlock-free routing algorithms have been developed for store-and-
forward computer networks [13, 15, 23]. These algorithms are based on a
structured buffer pool. However, with wormhole routing, buffer allocation cannot
be restricted, because flits have no routing information. Once the header
of a message has been accepted by a channel, the remaining flits must be accepted
before the flits of any other message can be accepted. So, routing must
be restricted to avoid deadlock.
Dally [10] has proposed a methodology to design static routing algorithms
under general assumptions. He defines a channel dependency graph and establishes
a total order among channels. Routing is restricted to visit channels in
decreasing or increasing order to eliminate cycles in the channel dependency
graph. This methodology has been applied to the design of routing chips for
multicomputers [9] and multicomputer nodes with integrated communication
support [2]. It has also been applied to systolic communication [21, 2].
The restriction of routing, although it avoids deadlock, can increase traffic
jams, especially in heavily loaded networks with long messages. In order to
avoid congested regions of the network, an adaptive routing algorithm can be
used. Adaptive strategies have been shown to outperform static strategies in
store-and-forward routing [3] and in packet-switched communications [20, 24].
In general, adaptive routing needs additional hardware support.
Several adaptive algorithms have been developed for wormhole routing. A
deadlock-free adaptive algorithm for the hypercube is the Hyperswitch algorithm
[4], which is based on backtracking and hardware modification of message
headers to avoid congestion and cycles. Another deadlock-free adaptive algorithm
has been proposed for the MEGA [14]. This algorithm always routes
messages, sending them away from their destination if necessary, like the Connection
Machine [16]. If the message arrives at a node without free output
channels, deadlocks are avoided by storing the message and removing it from
the network. In this respect, it is similar to virtual cut-through [19]. Jesshope
[18] has proposed an algorithm for n dimensional meshes, by decomposing them
into 2n virtual networks. Inside each virtual network, displacements along a
given dimension are always made in the same direction, thus avoiding cycles
and deadlock. A similar strategy for the development of adaptive and fault
tolerant routing algorithms for k-ary n-cubes has been proposed in [22]. It
is also based on the concept of virtual networks and requires the absence of
cycles in the channel dependency graph. That strategy is only feasible for low-dimensional
networks because the number of virtual channels increases very
rapidly with the dimension.
An alternative way consists of recovering from deadlock. Reeves et al. [25]
have used an abort-and-retry technique to remove messages blocked for longer
than a certain threshold from the network. Aborted messages are introduced
again into the network after a random delay. In [25] three adaptive routing
strategies have been proposed and evaluated for a binary 8-cube.
Another approach is the use of multistage interconnection networks, in
which deadlocks are easier to avoid. In [17] an adaptive algorithm based on
interval routing has been proposed and evaluated. Although the results show
that multistage networks outperform grids and hypercubes, the comparison
does not take into account the implementation restrictions, in the way proposed
Finally, in [11] we have proposed a very simple methodology to design
deadlock-free adaptive routing algorithms for wormhole networks. The routing
algorithms obtained from the application of that methodology to 2D and 3D-
meshes have been evaluated by simulation.
In summary, several adaptive routing algorithms have been proposed. In
general, they outperform static algorithms. In order to avoid deadlocks, routing
algorithms require either the absence of cycles in the channel dependency graph
or additional hardware support. The first approach is too restrictive, limiting
the number of alternative paths that can be used or requiring a lot of virtual
channels. The second approach introduces additional delays (backtracking,
message abortion, etc.
This paper develops the theoretical background for the design of deadlock-free
adaptive routing algorithms for wormhole networks. Some basic definitions
and two theorems are proposed and proved, developing conditions to verify that
an adaptive algorithm is deadlock-free, even when there are cycles in the channel
dependency graph. Also, two design methodologies based on the above
mentioned theorems are proposed. The first one supplies adaptive algorithms
with a high degree of freedom, without increasing the number of physical chan-
nels. The second methodology is intended for the design of fault-tolerant algo-
rithms. Some examples show the application of both methodologies, obtaining
new adaptive routing algorithms. Finally, one of those algorithms is evaluated
by simulation.
Section 2 develops the new theory for wormhole routing. Section 3 proposes
two design methodologies, giving some examples of their application. The
details concerning the simulation are described in section 4, showing the results
in section 5. Finally, some conclusions are drawn.
Definitions and theorems
This section develops the theoretical background for the design of deadlock-free
adaptive routing algorithms for networks using wormhole routing. This
theory is also valid when messages are split into packets. However, as typical
messages are short [7], we will consider that messages are not split. Otherwise,
the following assumptions and definitions should refer to packets.
The basic assumptions are very similar to the ones proposed by Dally [10],
except that adaptive routing is allowed. These assumptions are the following:
1. A node can generate messages destined for any other node at any rate.
2. A message arriving at its destination node is eventually consumed.
3. Wormhole routing is used. So, once a queue accepts the first flit of a
message, it must accept the remainder of the message before accepting
any flits from another message.
4. A node can generate messages of arbitrary length. Messages will generally
be longer than a single flit.
5. An available queue may arbitrate between messages that request that
queue, but may not choose among waiting messages.
6. A queue cannot contain flits belonging to different messages. After accepting
a tail flit, a queue must be emptied before accepting another
header flit. Then, when a message is blocked, its header flit will always
occupy the head of a queue. This assumption is necessary to prove theorem
2. If it is not satisfied, it is easy to define a deadlocked configuration
which invalidates that theorem, as will be seen in consideration 2 after
the theorem proof.
7. The route taken by a message depends on its destination and the status
of output channels (free or busy). At a given node, the routing function
supplies a set of output channels based on the current and destination
nodes. A selection from this set is made based on the status of output
channels at the current node. So, adaptive routing will be considered.
Before proposing the theorems, some definitions are needed:
network I is a strongly connected directed
multigraph, G(N;C). The vertices of the multigraph N represent the
set of processing nodes. The arcs of the multigraph C represent the set of
communication channels. More than a single channel is allowed to connect a
given pair of nodes. Each channel c i has an associated queue denoted queue(c i )
with capacity cap(c i ). The source and destination nodes of channel c i are
denoted s i and d i , respectively.
F be the set of valid channel status, busyg. Let
F be the status of the output channels in the network.
Definition 3 An adaptive routing function R : N \Theta N ! P(C), where
P(C) is the power set of C, supplies a set of alternative output channels
to send a message from the current node n c to the destination node n d ,
g. In general, p will be less than the number of output
channels per node to restrict routing and obtain deadlock-free algorithms.
As a particular case, defines a static routing
function. Also, R(n; . The domain of R has been defined as
N \Theta N instead of C \Theta N as in [10]. Otherwise, one of the theorems we propose
could not be proved. This point will be discussed in detail after proving theorem
(see consideration 3). Also, defining the result of R as a set of channels
(an element of P(C)) allows us the use of the operations defined on sets. In
particular, the 2 operator will be extensively used throughout this paper.
Definition 4 A selection function
channel (if any) from the set supplied by the routing function. From the
definition, S takes into account the status of all the channels belonging to the
set supplied by the routing function. The selection can be random or based
on static or dynamic priorities. Also, in the same way the result of a static
routing function may be a busy channel, if all the output channels are busy, any
of them may be selected. The decomposition of the adaptive routing into two
functions (routing and selection) will be critical while proving the theorems,
because only the routing function determines whether a routing algorithm is
deadlock-free or not. Then, the selection function will only affect performance.
Moreover, it is possible to extend the definition of the selection function by
taking into account additional information, either local to the node or remote.
We will comment on this in section 3.
routing function R for a given interconnection network I is
connected iff
In other words, it is possible to establish a path between x and y using
channels belonging to the sets supplied by R. Notice that the interconnection
network is strongly connected, but it does not imply that the routing function
must be connected.
Definition 6 A routing subfunction R 1 for a given routing function R and
channel subset C 1 ' C, is a routing function
Definition 7 Given an interconnection network I, a routing function R and
a pair of channels c there is a direct dependency from c i to c j iff
that is, c j can be used immediately after c i by messages destined to some
node n.
Definition 8 Given an interconnection network I, a routing function R, a
channel subset C 1 ae C which defines a routing subfunction R 1 and a pair of
there is an indirect dependency from c i to c j iff
that is, it is possible to establish a path from s i to d j for messages destined
to some node n. c i and c j are the first and last channels in that path and the
only ones belonging to C 1 . Then, c j can be used after c i by some messages.
As c i and c j are not adjacent, some other channels belonging to C \Gamma C 1 are
used between them. It must be noticed that, given three channels c
the existence of direct dependencies between c i , c j and c j , c k ,
respectively, does not imply the existence of an indirect dependency between
Definition 9 A channel dependency graph D for a given interconnection net-work
I and routing function R, is a directed graph, G(C;E). The vertices
of D are the channels of I. The arcs of D are the pairs of channels
such that there is a direct dependency from c i to c j . Notice that there are no
1-cycles in D, because channels are unidirectional.
extended channel dependency graph DE for a given inter-connection
network I and routing subfunction R 1 of a routing function R, is
a directed graph, The vertices of DE are the channels that
define the routing subfunction R 1 . The arcs of DE are the pairs of channels
such that there is either a direct or an indirect dependency from c i to
Definition 11 A sink channel for a given interconnection network I and routing
function R is a channel c i such that
In other words, all the flits that enter a sink channel reach their destination
in a single hop. As a result, there are no outgoing arcs from a sink channel in
any channel dependency graph, as can be easily seen from the definitions.
Definition 12 A configuration is an assignment of a set of flits to each queue,
all of them belonging to the same message (assumption 6). The number of flits
in the queue for channel c i will be denoted size(c i ). If the first flit in the queue
for channel c i is destined for node n d , then head(c . If the first flit is not
a header and the next channel reserved by its header is c j , then next(c
Let C h ' C be the set of channels containing a header flit at their queue head.
Let C d ' C be the set of channels containing a data or tail flit at their queue
head. A configuration is legal iff
For each channel, the queue capacity is not exceeded and all the flits stored
in the queue (if any), which have the same destination, can reach the channel
from the previous node using the routing function.
deadlocked configuration for a given interconnection network
I and routing function R is a nonempty legal configuration verifying the following
conditions:
In a deadlocked configuration there is not any flit one hop from its desti-
nation. Header flits cannot advance because the queues for all the alternative
output channels supplied by the routing function are not empty (see assumption
6). As a particular case (for disconnected routing functions), the routing
function may not supply any output channel. Data and tail flits cannot advance
because the next channel reserved by their message header has a full
queue. No condition is imposed to empty channels. It must be noticed that
a data flit can be blocked at a node even if there are free output channels to
reach its destination. Also, in a deadlocked configuration, there is no message
whose header flit has already arrived to its destination.
routing function R for an interconnection network I is
deadlock-free iff there is not any deadlocked configuration for that routing function
on that network.
Two theorems are proposed. The first one is a straightforward extension
of Dally's theorem for adaptive routing functions. The second one allows the
design of adaptive routing functions with cyclic dependencies in their channel
dependency graph. For each theorem, a sketch of the proof as well as the full
proof are given.
Theorem 1 A connected and adaptive routing function R for an interconnection
network I is deadlock-free if there are no cycles in its channel dependency
graph D.
Proof
( As the channel dependency graph for R is acyclic, it is possible to establish
an order between the channels of C. As R is connected, the minimals
of that order are also sinks. Suppose that there is a deadlocked configuration
for R. Let c i be a channel of C with a nonempty queue such that there are
no channels less than c i with a nonempty queue. If c i is a minimal (that is, a
sink) then the flit at the queue head can reach its destination in a single hop
and there is no deadlock. Otherwise, using the channels less than c i , the flit at
the queue head of c i can advance and there is not a deadlock.2
Proof:
Suppose that there are no cycles in D. Then, one can assign an order to
the channels of C so that if (c . Consider the channel(s)
c i such that
Such a channel c i is a minimal of the order. Let us prove that it is a
sink. If it were not a sink, as the routing function is connected, for any legal
configuration with a header flit stored in the queue head of c i
As the configuration is legal then
contrary to the assumption that c i is a minimal. So, d
is a sink of D.
Suppose that there is a deadlocked configuration for R. Let c i be a channel
of C with a nonempty queue such that there is not any channel less than c i
with a nonempty queue. If c i is a minimal, it is also a sink and then, all the
flits stored in its queue will be destined to d i and the flit at the head of the
queue for c i is not blocked. If c i is not a minimal then
Thus, the flit at the head of the queue for c i is not blocked, regardless it is
a header or a data flit, and there is no deadlock.2
There are some interesting considerations:
1. The theorem gives a sufficient but not necessary condition for an adaptive
routing function to be deadlock-free. As will be seen later, the existence
of cycles in the channel dependency graph does not imply the existence
of a deadlocked configuration.
2. For most networks and routing functions, even for static ones, only a
partial order between channels can be defined, based on the set E. In
general, there will be more than a single sink in D.
3. As indicated above, in a legal configuration all the flits stored in a given
queue have reached it using the routing function. Otherwise, the theorem
cannot be proved. Consider, for instance, a configuration in which the
queues of all the sink channels in D are full of flits destined to nodes not
directly connected to those channels.
Theorem 2 A connected and adaptive routing function R for an interconnection
network I is deadlock-free if there exists a subset of channels C 1 ' C that
defines a routing subfunction R 1 which is connected and has no cycles in its
extended channel dependency graph DE .
Proof
( The case C As the extended channel
dependency graph for R 1 is acyclic, it is possible to establish an order between
the channels of C 1 . As R 1 is connected, the minimals of that order are also
sinks. Suppose that there is a deadlocked configuration for R. There are two
possible cases:
a) The queues for channels belonging to C 1 are empty. As R 1 is connected
and the header flits are at queue heads, each header can be routed using channels
belonging to C 1 and there is no deadlock.
b) The queues for channels belonging to C 1 are not empty. Let c i be a
channel of C 1 with a nonempty queue such that there are no channels less than
c i with a nonempty queue. Again, there are two possible cases:
then the flit at the queue head is not blocked
and there is no deadlock.
is not a minimal, all the channels of C 1 less than c i will have empty
queues, existing three possible cases:
has a header at the queue head, it can be routed because R 1 is
connected and there is no deadlock.
b2.2) If there is a data flit at the queue head of c i and next(c i ) belongs to
that flit can also advance.
we have to use the indirect dependencies
in the extended channel dependency graph. Let c k be the channel containing
the header of the data flits contained in c i . Then, it is possible to find a channel
belonging to C 1 to route that header, because R 1 is connected. In that case,
there is an indirect dependency from c i to c j implying that c j is
empty and there is no deadlock.2
Proof:
Suppose that there exists a channel subset C 1 ' C which defines a
routing subfunction R 1 and that R 1 is connected and there are no cycles in
DE . If C ;. Thus, there is not any
cycle in D and R is deadlock-free by theorem 1. Otherwise C 1 ae C. As there
are no cycles in DE , one can assign an order to the channels of C 1 so that if
. Similarly to theorem 1, it can be proved that the
minimals of that order are also sinks.
Suppose that there is a deadlocked configuration for R. There are two
possible cases:
a) The queues for channels belonging to C 1 are empty. Then, there will be
channels belonging to C \Gamma C 1 with header flits at their queue heads. Let c i be
one of those channels. As R 1 is connected then
Also does not have a deadlock.
b) The queues for channels belonging to C 1 are not empty. Let c i be a
channel belonging to C 1 with a nonempty queue such that there are no channels
less than c i with a nonempty queue. Again, there are two possible cases:
is a minimal. As shown above, it is also a sink and then, all the flits
stored in its queue will be destined to d i and the flit at the head of the queue
for c i is not blocked.
is not a minimal. Then
existing three possible cases:
c i has a header at the queue head. Taking into account that R 1 is
connected
Also
and R does not have a deadlock.
c i has a data flit at the queue head, not destined to d i , and next(c i )
belongs to C 1 . Then
and R does not have a deadlock.
c i has a data flit at the queue head, not destined to d i , and next(c i )
belongs to be the set of channels reserved
by the message after reserving c i , c k containing the message header. Those
channels belong to C \Gamma C 1 , because in C 1 there are no channels less than c i
with a nonempty queue.
As R 1 is connected
Thus, there is an indirect dependency from c i to c j implying that
the header at the queue head for c k is not blocked and R
does not have a deadlock.2
Again, there are some interesting considerations:
1. The basic idea behind theorem 2 is that one can have an adaptive routing
function with cyclic dependencies between channels, provided that there
are alternative paths without cyclic dependencies to send a given flit
towards its destination. As messages are several flits long, the extended
channel dependency graph must be used to take into account the indirect
dependencies.
2. If it were not necessary to empty a queue before accepting the header
of another message, then there would be no guarantee that header flits
occupy the queue heads and the theorem would not be valid. Consider,
for instance, a set of four or more channels with cyclic dependencies
between them and a configuration in which the queues of those channels
are full, each one containing the tail of a message followed by a fragment
of another message destined two nodes away. The rest of that message
occupies part of the next channel queue and so on. That configuration
is deadlocked because the header flits do not occupy the queue heads
and cannot be routed using the alternative paths offered by the routing
function.
3. If the routing function were defined then the theorem
would not be valid. Consider, for instance, two subsets of C, namely,
routing function defined in such a way that all the
messages arriving to a given node through a channel belonging to
are routed through a channel belonging to the same subset. Suppose that
there are cyclic dependencies between the channels belonging to
and that C 1 defines a routing subfunction which is connected and has no
cycles in its extended channel dependency graph. That routing function
is not guaranteed to be deadlock-free.
4. The routing subfunction R 1 is not necessarily static. It can be adaptive.
3 Design methodologies
In this section we propose two methodologies for the design of deadlock-free
adaptive routing algorithms. The generation of static deadlock-free routing
algorithms requires restricting routing by removing arcs from the channel dependency
graph D to make it acyclic. If it is not possible to make D acyclic
without disconnecting the routing function, arcs can be added to D by splitting
physical channels into a set of virtual channels, each one requiring its own
buffer. This technique was introduced by Dally [10] to remove cycles from the
channel dependency graph.
However, a physical channel can be split into more virtual channels than the
ones strictly necessary to avoid deadlock [6, 11]. In such a case, the router can
choose among several channels to send a message, reducing channel contention
and message delay. Alternatively, more physical channels can be added to
each node, increasing the network bandwidth and allowing the design of fault-tolerant
adaptive routing algorithms.
A design methodology must supply a way to add channels following a regular
pattern, also deriving the new routing function from the old one. A design
methodology based on theorem 1 has been presented in [11]. Although the
algorithms designed with it behave better than the static ones, a higher degree
of freedom can be obtained basing the design on theorem 2. Here we
will present some more general methodologies for the design of deadlock-free
adaptive routing algorithms.
This methodology is intended to increase the number of valid
alternative paths to send a message towards its destination without increasing
the number of physical channels. In general, it will reduce channel contention
and message delay. The steps are the following:
1. Given an interconnection network I 1 , define a minimal path connected
static routing function R 1 for it, following Dally's methodology and splitting
physical channels into virtual ones, if necessary, to guarantee that R 1
is deadlock-free. Alternatively, define a minimal path connected adaptive
routing function R 1 and selection function S 1 , verifying that R 1 is
deadlock-free using theorem 2. Let C 1 be the set of channels at this point.
2. Split each physical channel into a set of additional virtual channels. Let
C be the set of all the (virtual) channels in the network. Let C xy be the
set of output channels from node x belonging to a minimal path from x
to y. Define the new routing function R as follows:
that is, the new routing function can use any of the new channels belonging
to a minimal path or, alternatively, the channels supplied by R 1 .
The selection function can be defined in any way.
3. Verify that the extended channel dependency graph for R 1 is acyclic. If
it is, the routing algorithm is valid. Otherwise, it must be discarded,
returning to step 1.
establishes the starting point. We can use either a static or adaptive
routing function as the basic one. Dally's theorem and theorem 2 can be used
to verify that the basic function is deadlock-free. Step 2 indicates how to
add more (virtual) channels to the network and how to define a new adaptive
routing function from the basic one. Step 3 verifies whether the new routing
function is deadlock-free or not. If the verification fails, the above proposed
methodology may lead to an endless cycle. Then, it does not supply a totally
mechanical way to design adaptive routing algorithms. Fortunately, all the
algorithms we have designed up to now have passed the verification step. So,
we wonder whether the step 3 is really necessary. This is still an open question.
The implementation of adaptive routing algorithms based on this methodology
requires that physical channels are split into virtual ones. Dally [8] has
described the implementation of virtual channels. That description is not restricted
to the case of static routing algorithms. Then, all the implementation
details described in [8] are applicable to this case.
It must be noticed that the methodology can also be applied by adding
physical channels instead of virtual ones. The resulting network will be faster
and more expensive, but the effective fault-tolerance will not increase. The
reason is that the new routing function relies on the set of channels C 1 to
guarantee that it is deadlock-free.
This methodology is intended to increase fault-tolerance in a
network. It will add physical channels, instead of splitting channels into virtual
ones. Of course, it will also reduce channel contention and message delay. The
steps are the following:
1. Given an interconnection network I 1 , define a static or adaptive connected
routing function R 1 for it, following Dally's methodology, the
above proposed methodology or verifying that R 1 is deadlock-free using
theorem 2. Let C 1 be the set of channels at this point.
2. Duplicate each physical channel. If the original channel was split into
several virtual channels, the duplicated channel will also be split into the
same number of virtual channels. Let C 2 be the set of duplicated channels
and C the set of all the channels. Let R 2 be a routing function identical to
defined using C 2 instead of C 1 . Define the new routing function
R as follows:
that is, the new routing function can use any of the channels supplied
by both, R 1 and R 2 . Define the selection function giving to the channels
belonging to C 1 and C 2 the same probability of use.
Again, step 1 supplies the basic routing function and step 2 adds alternative
paths. As can be easily seen, R 2 does not add any cycle to the extended channel
dependency graph for R 1 . Then, R is deadlock-free.
The duplication of channels defines an interconnection network I
which is identical to I 1 and shares the same set of nodes N . However,
are disjointed sets. R 2 has the same properties as R 1 . Also,
So, one can find, at least, two subfunctions of R, which allow us the application
of theorem 2 to guarantee that R is deadlock-free. Then, the theorem
can be applied even if we remove some channels either from C 1 or from C 2 .
However, the set of nodes is the same for I 1 and I 2 . It seems that the
proposed methodology is not tolerant to node faults. But, provided that R 1
and R 2 are adaptive routing functions, in general there will be alternative
paths to reach the destination node (assuming that it is not the faulty one).
Of course, some mechanism is needed to identify faulty channels, marking them
as busy, and faulty nodes, marking all the channels connected to them as busy
and avoiding to send messages to them. It must be noticed that if there is not
any faulty node, the information about faulty channels can be recorded locally.
Finally, step 2 can be applied several times, duplicating each channel as
many times as desired.
The proposed methodologies are very simple to apply. They illustrate the
power of the theorems. More complex design methodologies can be defined
based on the same theoretical background.
As an example, we will present a design based on the above proposed
methodologies. Consider a binary n-cube. We will study three cases: a) applying
methodology applying methodology 2; c) applying methodologies 1
and 2.
a) For the step 1 we can use the conventional static routing algorithm for
the binary n-cube. It forwards messages crossing the channels in order of
decreasing dimensions. It is well known that this routing function is connected
and deadlock-free.
For the step 2, consider that each physical channel c i has been split into k
virtual channels, namely, a i;1 ; a be the set of b channels.
The algorithm obtained applying the step 2 can be stated as follows: Route
over any useful dimension using any of the a channels. If all of them are busy,
route over the highest useful dimension using the corresponding b channel. A
useful dimension is one that forwards a message nearer to its destination.
Fig. 1 shows the extended channel dependency graph for R 1 on a 3-cube.
b26

Figure

1: Extended channel dependency graph for R 1
Black circles represent the unidirectional channels belonging to C 1 and are
labeled as bij, where i and j are the source and destination nodes, respectively.
As a reference, channels are also represented by thin lines, horizontal and
vertical ones corresponding to dimensions 0 and 1, respectively. Also, the
nodes of the 3-cube have been labeled as nk, where k is the node number.
Thick lines represent channel dependencies, dashed arrows corresponding to
indirect dependencies. It can be seen that the graph is acyclic. Then, R is
deadlock-free. It must be noticed that the channel dependency graph for R
(not shown) has cycles.
As virtual channels share a single physical channel, the former algorithm
effectively allows messages to cross the physical channels corresponding to the
n-cube dimensions in any order, increasing the number of alternative paths and
decreasing network contention. The performance of that algorithm has been
evaluated by simulation. The results are presented in the next sections.
b) Assume that step 1 is applied as in case a), obtaining the conventional
static routing algorithm.
For the step 2, consider that each physical channel c i has been duplicated,
obtaining a new channel g i . The algorithm obtained applying the step 2 can
be stated as follows: Route over the highest useful dimension using the corresponding
c or g channels.
That algorithm increases the tolerance to faulty channels, but it does not
take advantage of alternative minimal paths.
c) Assume that we apply the methodology 1, obtaining the algorithm proposed
in case a). That algorithm constitutes the step 1.
For the step 2, consider that each physical channel c i has been duplicated,
obtaining a new channel g i , which is also split into k virtual channels, namely,
. The algorithm obtained applying the step 2 can be stated
as follows: Route over any useful dimension using any of the a or e channels.
Alternatively, route over the highest useful dimension using the corresponding
b or f channels.
That algorithm has the advantages of the previous ones at the cost of a
slightly more complicated circuitry.
The number of virtual channels per physical channel only affects the per-
formance. We will comment on this in the next sections. Also, as stated
in section 2, the selection function only affects the performance. It is not
necessary to give a higher priority to the channels in the acyclic dependency
subgraph, because when the remaining channels are busy, those ones will be
used. In general, a higher performance is achieved when the channels in the
cyclic dependency subgraph are given a higher priority, because they usually
offer a larger number of alternative paths. Moreover, when several routing
options are available, selecting a virtual channel in such a way that channel
multiplexing is minimized usually reduces the average message delay.
Finally, the selection function can be extended by including additional information
in its domain. For instance, for the algorithm obtained in case a),
it is possible to favor the a channels connecting to the neighbor with a higher
number of free channels in useful dimensions. This selection function is inspired
in an algorithm proposed in [25], the main difference being that our
algorithm does not require a complex mechanism to abort messages because it
is deadlock-free.
4 Evaluation methodology
The routing algorithm obtained in case a) supplies a large number of routing
options to forward a message toward its destination. Also, the multiplexing
of physical channels reduces channel contention by allowing several messages
to share a channel. However, each virtual channel only has a fraction of the
total bandwidth, increasing the term L=B. So, there are opposite effects and
the behavior of the new routing algorithm is not intuitive, being necessary
to evaluate its performance under different load conditions. In what follows,
this algorithm will be referred to as adaptive algorithm. The static routing
algorithm for the binary n-cube (e-cube) has been evaluated under the same
conditions for comparison purposes. For this algorithm we have also analyzed
the effect of the virtual channel flow control mechanism proposed in [6], showing
the effect of channel multiplexing.
Once the topology has been selected, the algorithm performance depends on
several parameters, including channel bandwidth, network size, message traffic,
message length and the number of virtual channels per physical channel. Let
us analyze that dependency in order to select the conditions for the evaluation.
Firstly, we are interested in comparing different routing algorithms rather
than obtaining absolute performance measures. Then, channel bandwidth is
not important, provided a uniform criterion is used. The criterion we have
used consists of using a constant channel bandwidth equal to one flit per clock
cycle.
In general, network size has a considerable influence on network perfor-
mance. Then, taking into account the maximum sizes of current multicomput-
ers, we have mainly evaluated networks with 4096 nodes, also obtaining some
results for networks ranging from 64 to 4096 nodes. It is especially important
to see whether the routing algorithms scale well with network size.
Message traffic and message length are application and operating system
dependent. As these parameters are very difficult to model, we have used a
uniform distribution for message destination, trying to model the worst case.
For each routing algorithm, the flit generation rate ranges from a small value
to saturation. For message length, a constant value equal to 16 flits has been
used.
The number of virtual channels per physical channel is a design parameter.
We have analyzed the effect of this parameter, holding the total queue size per
physical channel constant, as proposed in [6].
Instead of analytic modeling, simulation has been used to evaluate the
routing algorithms, because the model can more faithfully represent a hardware
implementation, taking into account details like channel multiplexing, partial
buffering and delays in blocked messages. The simulation methodology we have
used is summarized in the following sections.
4.1 Multicomputer model
Our simulator models different topologies and network sizes up to 16K nodes.
Each node consists of a processor, a crossbar, a router and several channels.
Processors can generate messages at any rate. Message format will be described
below. Message reception is buffered, allowing the storage of messages independently
of the processes which have to receive them. The simulator takes
into account memory contention, limiting the number of messages that can be
sent or received simultaneously. Binary n-cubes have a large number of channels
in the network bisection, limiting channel bandwidth. Because of that, we
have assumed that up to four messages can be sent or received simultaneously.
The crossbar allows multiple messages to traverse a node simultaneously
without interference. It takes one clock cycle to transfer a flit from an input
queue to an output queue.
The router decides when to transfer a message, determining the output
channel as a function of the destination node, the current node and the output
channel status. Wormhole routing is used. The router can only process a
message header at a time. If there is no contention for the router, it takes
one clock cycle to compute the output channel. Otherwise, access is round
robin. When a message gets the router, but cannot be routed because all the
alternative output channels are busy, it must wait until its next turn.
Physical channels are split into up to four virtual channels. Each virtual
channel has queues of equal size at both ends. The total queue size associated
to each physical channel is held constant. Virtual channels are assigned the
physical channel cyclically, only if they can transfer a flit. So, channel band-width
is shared among the virtual channels requesting it. It must be noticed
that blocked messages and messages waiting for the router do not consume any
channel bandwidth.
4.2 Message generation
A message consists of a header, some data and a tail. For the sake of simplicity,
we have assumed that the header occupies a single flit, thus a message may be
routed as soon as the first flit arrives to a node.
The message generation rate is constant and the same for all the nodes.
After generating a message, each node waits a random number of clock cycles
before generating the next message. The number of cycles is uniformly distributed
between two simulation parameters. The inverse of the mean value of
these parameters will be referred to as message generation rate. The product
of the message generation rate by the message length is the flit generation rate
and can be measured in flits per node and clock cycle. As indicated above, up
to four messages are allowed to leave each node simultaneously. If there are
four outgoing messages and a new message is generated, it is queued.
Once the network has reached a steady state, the flit generation rate is
equal to the flit reception rate, unless the network is saturated. In this case,
both rates differ and source queues grow. We will refer to the flit reception
rate as traffic, because it is the actual traffic through the network. It must be
noticed that traffic is not an independent variable.
4.3 Performance measures
The most important performance measures are delay and throughput. Delay
is the additional latency required to transfer a message with respect to an
idle network. It is measured in clock cycles. The message latency lasts since
the message is introduced in the network until the last flit is received at the
destination node. An idle network means a network without message traffic
and, thus, without channel multiplexing.
Throughput is usually defined as the maximum amount of information delivered
per time unit. However, the network may be unstable when traffic
reaches the maximum value. In this case, increasing the flit generation rate
may reduce the traffic, as will be seen in the next section. Then, throughput
is defined as the saturation traffic. As we have normalized channel bandwidth,
throughput is measured in flits per node and clock cycle, making it independent
of network size.
4.4 Validation
Each simulation has collected data from 100000 messages, discarding the messages
corresponding to a transient period required to reach a steady state. The
number of discarded messages ranged from 50000 to 240000, depending on the
traffic. After the transient period, the fluctuation of the performance measures
for 4096-node networks was lower than 2.4%. Several simulations were rerun
to test the reproducibility. The performance measures did not change by more
than 1%.
5 Simulation results
The first simulation results for the adaptive algorithm proposed in section 3
(case a) were presented in [12], showing an important improvement over the
static algorithm for 16-flit and 256-flit messages. However, those results did
not consider partial buffering nor memory contention. Also, a single message
was allowed to leave a node at a time, preventing network saturation. Then,
the throughput gain achieved by the adaptive algorithm was not properly dis-
played. The simulation results presented in this paper overcome the former
limitations, also analyzing the effect of the number of virtual channels per
physical channel.
Firstly, we will compare the static and adaptive routing algorithms on a
binary 12-cube under the same conditions. The adaptive algorithm has been
simulated with three virtual channels per physical channel, while the static
one has been simulated with one and three virtual channels. Fig. 2 shows the
average message delay versus traffic for 4096 nodes. The independent variable
is the flit generation rate, traffic and average message delay being measures.
The use of virtual channels drastically increases the throughput achieved
by the static algorithm. This result was already pointed out by Dally [6].
Nevertheless, the adaptive algorithm still improves the throughput by 35%,
using the same number of virtual channels. Moreover, the adaptive algorithm
achieves an important reduction in message delay with respect to the static
algorithm. For the same number of virtual channels, the average delay for
the adaptive algorithm is as much as 35% of the delay obtained for the static
algorithm. Also, the standard deviation of message delay (not shown) is smaller
for the adaptive algorithm.
It is interesting to see the effect of the number of virtual channels per physical
channel. Fig. 3 also shows the average message delay versus traffic for 4096
nodes. The curves correspond to the static and adaptive algorithms, both with
two, three and four virtual channels per physical channel. Again, traffic and
average message delay are measures. Then, the curves do not represent
tions. As can be seen, there are two distinct average delay values corresponding
to a range of traffic values for one of the curves.
For the static algorithm, increasing the number of virtual channels also
increases throughput. However, this increment is small (less than 4%) when
the fourth virtual channel is added. This addition also increases the average
message delay by as much as 22%. So, it seems that three virtual channels per
physical channel is the best choice. This behavior agrees with the one presented
by Dally in [8] for a 16-ary 2-cube network. This similarity is interesting, taking
into account the very different number of dimensions of both networks.
For the adaptive algorithm, the influence of the number of virtual channels
is similar. The average message delay also increases by as much as 22%
when the fourth virtual channel is added. However, there are two important
differences. The most noticeable one consists of a drastic increase in message
Average
Traffic

Figure

2: Average message delay versus traffic for 4096 nodes
Average
Traffic

Figure

3: Effect of the number of virtual channels per physical channel on the
average message delay for 4096 nodes
delay and a reduction in traffic when the adaptive algorithm with two virtual
channels reaches saturation. The second difference refers to throughput. It
does not increase when the fourth virtual channel is added. Again, three virtual
channels per physical channel seems the best choice. These results will be
explained later.
It is also interesting to know whether the routing algorithms scale well
with network size. Fig. 4 shows the throughput as a function of network size.
For the range of sizes we have analyzed, throughput decreases by 32% for the
static algorithm. When virtual channels are used, throughput only decreases
by 14%. The adaptive algorithm scales even better, throughput decreasing by
as much as 6%. Additionally, the use of virtual channels in the static algorithm
increases throughput by a factor ranging from 1.8 to 2.2. Also, the adaptive
algorithm increases throughput over the static algorithm with a single virtual
channel by a factor ranging from 2.2 to 3.
Finally, Fig. 5 shows the average message delay as a function of network
size, holding traffic constant. This figure clearly shows that the static algorithm
with a single virtual channel does not scale well with network size. However,
when virtual channels are used, message delay increases almost linearly with
the logarithm of the network size. Message delay increases by 14% each time
the network size is doubled. This result is improved by the adaptive algorithm,
delay increasing linearly by 3.3% each time the network size is doubled. It must
be noticed that these results have been obtained holding channel bandwidth
constant while network size increases.
Let us analyze the former results. The static algorithm with a single virtual
channel has no choice, because the routing function supplies a single channel.
As network traffic increases, the probability for a message header of finding
decreases, increasing channel contention and message
Throughput0.20.611.4
Network size

Figure

4: Throughput per node as a function of network size
Average
Network size

Figure

5: Average message delay as a function of network size for flit generation
rate equal to 0.4 flits/cycle/node
delay. Moreover, when a message is blocked, the bandwidth of all the channels
it has reserved is wasted. This is the main reason why throughput is relatively
small. Also, as network size increases, there are more messages flowing through
the network, increasing channel contention and message delay.
As stated above, the use of virtual channels has two opposite effects: it reduces
channel contention by supplying more routing options, but it can increase
message delay because channel bandwidth is shared among the requesting mes-
sages. When traffic is intense, the reduction in channel contention has a larger
effect than bandwidth sharing. Moreover, the virtual channel mechanism has
an important advantage. When a message is blocked, the virtual channels reserved
by it do not consume any channel bandwidth. As a consequence, the use
of virtual channels increases throughput considerably and message delay scales
well with network size. However, adding more virtual channels yields diminishing
returns. As pointed out by Dally [8], adding virtual channels while holding
storage constant increases the usage of virtual channels. For instance, when
the static algorithm with four virtual channels reaches saturation, messages in
transit occupy 100000 virtual channels. The same algorithm with three virtual
channels only has 78000 busy channels.
On the other hand, as soon as a single channel occupied by a message is
multiplexed, the whole message is slowed-down. An uneven distribution for
channel multiplexing produces bottlenecks. As a consequence, the bandwidth
of the less multiplexed channels is partly wasted. Then, for low flit generation
rates, adding virtual channels increases message delay. This increment is small
because messages are short and only a few flits are affected by bottlenecks.
Also, message headers must be routed, introducing another bottleneck. Routing
operations, together with partial buffering, partly hide the effect of uneven
channel multiplexing until the message header reaches its destination. For long
messages, the negative effects of channel multiplexing are more noticeable, as
shown in [12].
The adaptive algorithm also uses virtual channels. Thus, it inherits the
basic properties of this flow control mechanism. However, it permits a message
to cross the n-cube dimensions in any order. Then, the routing function offers
more choices, reducing channel contention and message delay accordingly.
Also, the adaptive algorithm is able to use any minimal path, increasing channel
utilization from 70% (static algorithm with four virtual channels) to 90%
(adaptive algorithm with three virtual channels). As a consequence, through-put
also increases. Moreover, the selection function helps in reducing channel
multiplexing. First, it looks for a virtual channel belonging to a free physical
channel. Also, it assigns the a channels a higher priority. Then, channels
are only multiplexed when network traffic is intense, considerably reducing the
negative effects of virtual channels.
As pointed out before, there is an important performance degradation when
the adaptive algorithm with two virtual channels reaches saturation. We have
carefully analyzed this case. It must be noticed that theorem 2 allows the
existence of cyclic dependencies between channels. Deadlocks are avoided by
relying on a channel subset to drain messages involved in cyclic dependencies.
If the number of virtual channels per physical channel is insufficient, channel
contention increases the number of blocked messages when traffic is intense. It
is possible to reach a situation such that messages block cyclically faster than
they are drained. In this situation, some messages remain blocked for long
periods, increasing message delay drastically. Also, most channels are occupied
by blocked messages, reducing the effective network bandwidth. Throughput
is reduced accordingly. This is the price to pay for allowing the existence of
cyclic dependencies between channels. Fortunately, this problem disappears
when more virtual channels are added.
We also pointed out before that adding a fourth virtual channel to the adaptive
algorithm does not increase throughput, as opposed to the static algorithm.
The adaptive routing function supplies several routing options, reducing channel
contention with respect to the static algorithm. Then, adding more options
does not reduce contention significantly. It seems that three virtual channels
per physical channel is the best option. The existence of an optimal number
of virtual channels per physical channel has already been suggested in [11].
However, that optimal value may change for another distribution of message
destination. Currently, we are working on this subject.
Finally, the number of choices at each routing step increases with net-work
size, almost nullifying the negative effect produced by a higher traffic.
Because of that, the adaptive algorithm scales very well with network size.
Unfortunately, it is not feasible to implement binary n-cubes holding channel
bandwidth constant as network size increases.
6 Conclusions
The theoretical background for the development of deadlock-free adaptive routing
algorithms has been proposed for wormhole networks. Firstly, a straight-forward
extension of Dally's theorem has been presented, allowing the design of
adaptive algorithms. However, the absence of cycles in the channel dependency
graph is too restrictive.
Theorem 2 gives a more flexible condition for the development of adaptive
algorithms, by allowing the existence of cycles in the channel dependency
graph. The only requirement is the existence of a channel subset which defines
a connected routing subfunction with no cycles in its extended channel
dependency graph.
To simplify the application of the theorems, two design methodologies have
been proposed. The first one supplies adaptive algorithms with a high degree
of freedom. The second one gives a way to design fault-tolerant routing algo-
rithms. Both methodologies can be easily combined. Also, an example showing
three alternative ways to apply the proposed design methodologies is presented.
This example derives new adaptive routing algorithms for the binary n-cube.
Finally, one of those routing algorithms has been evaluated by simulation,
showing an important reduction in message delay with respect to the static
algorithm, even with the same number of virtual channels. Throughput also
increases considerably. Moreover, the new algorithm scales very well with net-work
size, showing an almost null increment in message delay as size increases.
Finally, the effect of the number of virtual channels has been analyzed.

Acknowledgment

Most assumptions, some definitions and theorem 1 are inspired in the theory
developed by W. J. Dally for static routing [10]. I also thank him for his encouraging
comments and suggestions to improve the paper. Finally, I would like to
thank the anonymous referees for their helpful comments and suggestions.



--R

"Multicomputers: Message-passing concurrent computers,"
"iWarp: An integrated solution to high-speed parallel computing,"
"The need for adaptive routing in the chaotic and unbalanced traffic environment,"
"Hyper- switch network for the hypercube computer,"
A VLSI Architecture for Concurrent Data Structures.
"Virtual-channel flow control,"
"Performance analysis of k-ary n-cube interconnection net- works,"
"Virtual-channel flow control,"
"The torus routing chip,"
"Deadlock-free message routing in multiprocessor interconnection networks,"
"Deadlock-free adaptive routing algorithms for multicomput- ers,"
"Deadlock-free adaptive routing algorithms for multicomputers: evaluation of a new algorithm,"
"A DAG-based algorithm for prevention of store-and- forward deadlock in packet networks,"
"Etude des m'ecanismes de communication pour une machine massivement parall'ele: MEGA,"
"Prevention of deadlocks in packet-switched data transport systems,"
The Connection Machine.
"Performance benefits from locally adaptive interval routing in dynamically switched interconnection networks,"
"High performance communications in processor networks,"
"Virtual cut-through: a new computer communication switching technique,"
"Adaptive packet routing in a hypercube,"
"Deadlock avoidance for systolic communication,"
"An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes,"
"Deadlock avoidance in store-and- forward networks - I: Store-and-forward deadlock,"
"Message routing schemes in a hypercube machine,"
"Adaptive routing and deadlock recovery: a simulation study,"
--TR
The connection machine
Deadlock-free message routing in multiprocessor interconnection networks
Multicomputers
Hyperswitch network for the hypercube computer
Deadlock avoidance for systolic communication
Adaptive packet routing in a hypercube
Message routing schemes in a hypercube machine
Warp: an integrated solution of high-speed parallel computing
High performance communications in processor networks
Performance Analysis of k-ary n-cube Interconnection Networks
Performance benefits from locally adaptive interval routing in dynamically switched interconnection networks
An Adaptive and Fault Tolerant Wormhole Routing Strategy for k-ary n-cubes
Virtual-channel flow control
A VLSI Architecture for Concurrent Data Structures
Virtual-Channel Flow Control

--CTR
Yong Ho Song , Timothy Mark Pinkston, A Progressive Approach to Handling Message-Dependent Deadlock in Parallel Computer Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.259-275, March
Timothy Mark Pinkston , Ruoming Pang , Jos Duato, Deadlock-Free Dynamic Reconfiguration Schemes for Increased Network Dependability, IEEE Transactions on Parallel and Distributed Systems, v.14 n.8, p.780-794, August
Youran Lan, An Adaptive Fault-Tolerant Routing Algorithm for Hypercube Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.6 n.11, p.1147-1152, November 1995
I. Garcs , D. Franco, Analysis of Distributed Routing Balancing behavior, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
Timothy Mark Pinkston , Sugath Warnakulasuriya, Characterization of Deadlocks in k-ary n-Cube Networks, IEEE Transactions on Parallel and Distributed Systems, v.10 n.9, p.904-921, September 1999
F. Safaei , A. Khonsari , M. Fathy , M. Ould-Khaoua, Performance analysis of fault-tolerant routing algorithm in wormhole-switched interconnections, The Journal of Supercomputing, v.41 n.3, p.215-245, September 2007
Timothy Mark Pinkston , Sugath Warnakulasuriya, On deadlocks in interconnection networks, ACM SIGARCH Computer Architecture News, v.25 n.2, p.38-49, May 1997
Aniruddha S. Vaidya , Anand Sivasubramaniam , Chita R. Das, Impact of Virtual Channels and Adaptive Routing on Application Performance, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.223-237, February 2001
Geyong Min , Mohamed Ould-Khaoua , John Ferguson, Performance prediction of wormhole switching in hypercubes with bursty traffic pattern, Proceedings of the ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
Ran Libeskind-Hadas, A Tight Lower Bound on the Number of Channels Required for Deadlock-Free Wormhole Routing, IEEE Transactions on Computers, v.47 n.10, p.1158-1160, October 1998
Geyong Min , John Ferguson , Mohamed Ould-Khaoua, Analysis of adaptive wormhole-routed torus networks with IPP input traffic, Proceedings of the 2001 ACM symposium on Applied computing, p.494-498, March 2001, Las Vegas, Nevada, United States
Yong Ho Song , Timothy Mark Pinkston, Distributed Resolution of Network Congestion and Potential Deadlock Using Reservation-Based Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.16 n.8, p.686-701, August 2005
Vivek Halwan , Fsun zgner , Atakan Dogan, Routing in Wormhole-Switched Clustered Networks with Applications to Fault Tolerance, IEEE Transactions on Parallel and Distributed Systems, v.10 n.10, p.1001-1011, October 1999
Shubhendu S. Mukherjee , Peter Bannon , Steven Lang , Aaron Spink , David Webb, The Alpha 21364 Network Architecture, IEEE Micro, v.22 n.1, p.26-35, January 2002
Jos F. Martnez , Josep Torrellas , Jos Duato, Improving the performance of bristled CC-NUMA systems using virtual channels and adaptivity, Proceedings of the 13th international conference on Supercomputing, p.202-209, June 20-25, 1999, Rhodes, Greece
Arjun Singh , William J. Dally , Brian Towles , Amit K. Gupta, Locality-preserving randomized oblivious routing on torus networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
A. Shahrabi , M. Ould-Khaoua , L. M. Mackenzie, Unicast-based broadcast: an analysis for the hypercube with adaptive routing, Proceedings of the 2001 ACM symposium on Applied computing, p.489-493, March 2001, Las Vegas, Nevada, United States
M. K. F. Schafer , T. Hollstein , H. Zimmer , M. Glesner, Deadlock-free routing and component placement for irregular mesh-based networks-on-chip, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.238-245, November 06-10, 2005, San Jose, CA
James Balfour , William J. Dally, Design tradeoffs for tiled CMP on-chip networks, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
Maurizio Palesi , Rickard Holsmark , Shashi Kumar , Vincenzo Catania, A methodology for design of application specific deadlock-free routing algorithms for NoC systems, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea
Ming-Jer Tasi , Sheng-De Wang, A Fully Adaptive Routing Algorithm for Dynamically Injured Hypercubes, Meshes, and Tori, IEEE Transactions on Parallel and Distributed Systems, v.9 n.2, p.163-174, February 1998
A. Shahrabi , M. Ould-Khaoua , L. Mackenzie, Communication delay in wormhole-routed torus networks, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
Daeho Seo , Akif Ali , Won-Taek Lim , Nauman Rafique , Mithuna Thottethodi, Near-Optimal Worst-Case Throughput Routing for Two-Dimensional Mesh Networks, ACM SIGARCH Computer Architecture News, v.33 n.2, p.432-443, May 2005
Jose Duato , Olav Lysne , Ruoming Pang , Timothy M. Pinkston, Part I: A Theory for Deadlock-Free Dynamic Network Reconfiguration, IEEE Transactions on Parallel and Distributed Systems, v.16 n.5, p.412-427, May 2005
NR Adiga , G Almasi , GS Almasi , Y Aridor , R Barik , D Beece , R Bellofatto , G Bhanot , R Bickford , M Blumrich , AA Bright , J Brunheroto , C Cacaval , J Castaos , W Chan , L Ceze , P Coteus , S Chatterjee , D Chen , G Chiu , TM Cipolla , P Crumley , KM Desai , A Deutsch , T Domany , MB Dombrowa , W Donath , M Eleftheriou , C Erway , J Esch , B Fitch , J Gagliano , A Gara , R Garg , R Germain , ME Giampapa , B Gopalsamy , J Gunnels , M Gupta , F Gustavson , S Hall , RA Haring , D Heidel , P Heidelberger , LM Herger , D Hoenicke , RD Jackson , T Jamal-Eddine , GV Kopcsay , overview of the BlueGene/L Supercomputer, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-22, November 16, 2002, Baltimore, Maryland
Jatin Upadhyay , Vara Varavithya , Prasant Moihapatra, A Traffic-Balanced Adaptive Wormhole Routing Scheme for Two-Dimensional Meshes, IEEE Transactions on Computers, v.46 n.2, p.190-197, February 1997
D. Franco , I. Garcs , E. Luque, A new method to make communication latency uniform: distributed routing balancing, Proceedings of the 13th international conference on Supercomputing, p.210-219, June 20-25, 1999, Rhodes, Greece
Loren Schwiebert, Deadlock-free oblivious wormhole routing with cyclic dependencies, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.149-158, June 23-25, 1997, Newport, Rhode Island, United States
Ludek Kucera, Wait-Free Deflection Routing of Long Messages, IEEE Transactions on Parallel and Distributed Systems, v.12 n.5, p.476-488, May 2001
Swaminathan Ramany , Derek Eager, The interaction between virtual channel flow control and adaptive routing in wormhole networks, Proceedings of the 8th international conference on Supercomputing, p.136-145, July 11-15, 1994, Manchester, England
S. Loucif , M. Ould-khaoua, Modeling Latency in Deterministic Wormhole-Routed Hypercubes under Hot-Spot Traffic, The Journal of Supercomputing, v.27 n.3, p.265-278, March 2004
Juan Manuel Ordua , Federico Silla , Jos Duato, On the development of a communication-aware task mapping technique, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.4, p.207-220, March 2004
Rajendra V. Boppana , Suresh Chalasani , C. S. Raghavendra, Resource Deadlocks and Performance of Wormhole Multicast Routing Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.9 n.6, p.535-549, June 1998
Jose C. Sancho , Antonio Robles , Jose Duato, An Effective Methodology to Improve the Performance of the Up*/Down* Routing Algorithm, IEEE Transactions on Parallel and Distributed Systems, v.15 n.8, p.740-754, August 2004
M. M. Hafizur Rahman , Susumu Horiguchi, Routing performance enhancement in hierarchical torus network by link-selection algorithm, Journal of Parallel and Distributed Computing, v.65 n.11, p.1453-1461, November 2005
Seung Eun Lee , Nader Bagherzadeh, Increasing the throughput of an adaptive router in network-on-chip (NoC), Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea
Profile-driven energy reduction in network-on-chips, ACM SIGPLAN Notices, v.42 n.6, June 2007
Soojung Lee, A deadlock detection mechanism for true fully adaptive routing in regular wormhole networks, Computer Communications, v.30 n.8, p.1826-1840, June, 2007
Mohamed Ould Khaoua , Geyong Min, A queueing model for predicting message latency in uni-directional k-ary n-cubes with deterministic routing and non-uniform traffic, Cluster Computing, v.10 n.2, p.229-239, June      2007
A. Ferre-Vilaplana , J. M. Bernabu-Aubn, A comparison of two approaches for independent scaling up of processing and communication capacities in multicomputer networks, Proceedings of the 13th international conference on Supercomputing, p.391-398, June 20-25, 1999, Rhodes, Greece
Ming-Jer Tsai , Sheng-De Wang, Adaptive and Deadlock-Free Routing for Irregular Faulty Patterns in Mesh Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.11 n.1, p.50-63, January 2000
G. Min , M. Ould-khaoua, Communication Delay in Wormhole-Switched Tori Networks under Bursty Workloads, The Journal of Supercomputing, v.26 n.1, p.77-94, August
Dhabaleswar K. Panda , Sanjay Singal , Ram Kesavan, Multidestination Message Passing in Wormhole k-ary n-cube Networks with Base Routing Conformed Paths, IEEE Transactions on Parallel and Distributed Systems, v.10 n.1, p.76-96, January 1999
Fernando Rodrguez-Salazar , John R. Barker, Hamming hypermeshes: high performance interconnection networks for pin-out limited systems, Performance Evaluation, v.63 n.8, p.759-775, August 2006
Slavko Gajin , Zoran Jovanovi, Explanation of Performance Degradation in Turn Model, The Journal of Supercomputing, v.37 n.3, p.271-295, September 2006
M. B. Hadim , I. Sakho, The Multi-Level Communication: Efficient Routing for Interconnection Networks, The Journal of Supercomputing, v.18 n.2, p.153-177, Feb. 1, 2001
V. Puente , J. A. Gregorio , C. Izu , R. Beivide , F. Vallejo, Low-level router design and its impact on supercomputer system performance, Proceedings of the 13th international conference on Supercomputing, p.193-201, June 20-25, 1999, Rhodes, Greece
Melanie L. Fulgham , Lawrence Snyder, Triplex: a multi-class routing algorithm, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.127-138, June 23-25, 1997, Newport, Rhode Island, United States
Jau-Der Shih, Fault-tolerant wormhole routing for hypercube networks, Information Processing Letters, v.86 n.2, p.93-100,
Jau-Der Shih, A fault-tolerant wormhole routing scheme for torus networks with nonconvex faults, Information Processing Letters, v.88 n.6, p.271-278, 31 December
A. Khonsari , H. Sarbazi-Azad , M. Ould-Khaoua, Analysis of true fully adaptive routing with software-based deadlock recovery, Journal of Systems and Software, v.71 n.3, p.259-270, May 2004
H. Sarbazi-Azad , M. Ould-Khaoua, A simple mathematical model of adaptive routing in wormhole k-ary n-cubes, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
Ge-Ming Chiu, The Odd-Even Turn Model for Adaptive Routing, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.729-738, July 2000
Mohamed Ould-Khaoua, A Performance Model for Duato's Fully Adaptive Routing Algorithm in k$k$-Ary n$n$-Cubes, IEEE Transactions on Computers, v.48 n.12, p.1297-1304, December 1999
Suresh Chalasani , Rajendra V. Boppana, Adaptive Multimodule Routers for Multiprocessor Architectures, Information Systems Frontiers, v.7 n.3, p.317-327, July      2005
Ted Nesson , S. Lennart Johnsson, ROMM routing on mesh and torus networks, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.275-287, June 24-26, 1995, Santa Barbara, California, United States
Rajendra V. Boppana , Suresh Chalasani, Fault-tolerant routing with non-adaptive wormhole algorithms in mesh networks, Proceedings of the 1994 conference on Supercomputing, p.693-702, December 1994, Washington, D.C., United States
Suresh Chalasani , Rajendra V. Boppana, Fault-tolerant wormhole routing in tori, Proceedings of the 8th international conference on Supercomputing, p.146-155, July 11-15, 1994, Manchester, England
Rajendra V. Boppana , Suresh Chalasani, Fault-tolerant routing with non-adaptive wormhole algorithms in mesh networks, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
Loren Schwiebert , D. N. Jayasimha, A universal proof technique for deadlock-free routing in interconnection networks, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.175-184, June 24-26, 1995, Santa Barbara, California, United States
Geyong Min , Mohamed Ould-Khaoua, A Performance Model for Wormhole-Switched Interconnection Networks under Self-Similar Traffic, IEEE Transactions on Computers, v.53 n.5, p.601-613, May 2004
Elizabeth Suet Hing Tse, Switch fabric architecture analysis for a scalable bi-directionally reconfigurable IP router, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.1, p.35-60, January 2004
Mohamed Ould-Khaoua , Hamid Sarbazi-Azad, An Analytical Model of Adaptive Wormhole Routing in Hypercubes in the Presence of Hot Spot Traffic, IEEE Transactions on Parallel and Distributed Systems, v.12 n.3, p.283-292, March 2001
Federico Silla , Jos Duato, On the Use of Virtual Channels in Networks of Workstations with Irregular Topology, IEEE Transactions on Parallel and Distributed Systems, v.11 n.8, p.813-828, August 2000
Jos Duato, A Necessary and Sufficient Condition for Deadlock-Free Routing in Cut-Through and Store-and-Forward Networks, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.841-854, August 1996
Geyong Min , Mohamed Ould-Khaoua , Demetres D. Kouvatsos , Irfan U. Awan, Stochastic Analysis of Deterministic Routing Algorithms in the Presence of Self-Similar Traffic, The Journal of Supercomputing, v.35 n.3, p.245-258, March     2006
Loren Schwiebert, Deadlock-Free Oblivious Wormhole Routing with Cyclic Dependencies, IEEE Transactions on Computers, v.50 n.9, p.865-876, September 2001
A. Shahrabi, Performance comparison of routing algorithms in wormhole-switched networks, Parallel Computing, v.32 n.11-12, p.870-885, December, 2006
K. V. Anjan , Timothy Mark Pinkston, An efficient, fully adaptive deadlock recovery scheme: DISHA, ACM SIGARCH Computer Architecture News, v.23 n.2, p.201-210, May 1995
Patrick T. Gaughan , Binh V. Dao , Sudhakar Yalamanchili , David E. Schimmel, Distributed, Deadlock-Free Routing in Faulty, Pipelined, Direct Interconnection Networks, IEEE Transactions on Computers, v.45 n.6, p.651-665, June 1996
Hamid Sarbazi-Azad , Mohamed Ould-Khaoua , Lewis M. Mackenzie, Analytical Modeling of Wormhole-Routed k-Ary n-Cubes in the Presence of Hot-Spot Traffic, IEEE Transactions on Computers, v.50 n.7, p.623-634, July 2001
Binh Vien Dao , Jose Duato , Sudhakar Yalamanchili, Configurable flow control mechanisms for fault-tolerant routing, ACM SIGARCH Computer Architecture News, v.23 n.2, p.220-229, May 1995
D. N. Jayasimha , Loren Schwiebert , D. Manivannan , Jeff A. May, A foundation for designing deadlock-free routing algorithms in wormhole networks, Journal of the ACM (JACM), v.50 n.2, p.250-275, March
A. Shahrabi , L. M. Mackenzie , M. Ould-Khaoua, An analytical model of wormhole-routed hypercubes under broadcast traffic, Performance Evaluation, v.53 n.1, p.23-42, June
Chien-Chun Su , Kang G. Shin, Adaptive Fault-Tolerant Deadlock-Free Routing in Meshes and Hypercubes, IEEE Transactions on Computers, v.45 n.6, p.666-683, June 1996
Suresh Chalasani , Rajendra V. Boppana, Communication in Multicomputers with Nonconvex Faults, IEEE Transactions on Computers, v.46 n.5, p.616-622, May 1997
A. Khonsari , M. Ould-Khaoua, A performance model of compressionless routing in k-ary n-cube networks, Performance Evaluation, v.63 n.4, p.423-440, May 2006
Timothy Mark Pinkston, Flexible and Efficient Routing Based on Progressive Deadlock Recovery, IEEE Transactions on Computers, v.48 n.7, p.649-669, July 1999
Suresh Chalasani , Rajendra V. Boppana, Fault-Tolerant Wormhole Routing Algorithms for Mesh Networks, IEEE Transactions on Computers, v.44 n.7, p.848-864, July 1995
Shubhendu S. Mukherjee , Federico Silla , Peter Bannon , Joel Emer , Steve Lang , David Webb, A comparative study of arbitration algorithms for the Alpha 21364 pipelined router, ACM SIGARCH Computer Architecture News, v.30 n.5, December 2002
Juan M. Martnez-Rubio , Pedro Lpez , Jose Duato, A Cost-Effective Approach to Deadlock Handling in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.12 n.7, p.716-729, July 2001
Ram Kesavan , Dhabaleswar K. Panda, Multiple Multicast with Minimized Node Contention on Wormhole k-ary n-cube Networks, IEEE Transactions on Parallel and Distributed Systems, v.10 n.4, p.371-393, April 1999
M. Ould-Khaoua , S. Loucif , F. A. Rabhi, On the performance of multicomputer interconnection networks, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.9, p.563-574, September 2004
S. Loucif , M. Ould-Khaoua, On the merits of hypermeshes and tori with adaptive routing, Journal of Systems Architecture: the EUROMICRO Journal, v.47 n.9, p.795-806, March 2002
Binh Vien Dao , Jose Duato , Sudhakar Yalamanchili, Dynamically Configurable Message Flow Control for Fault-Tolerant Routing, IEEE Transactions on Parallel and Distributed Systems, v.10 n.1, p.7-22, January 1999
J. D. Allen , P. T. Gaughan , D. E. Schimmel , S. Yalamanchili, Ariadnean adaptive router for fault-tolerant multicomputers, ACM SIGARCH Computer Architecture News, v.22 n.2, p.278-288, April 1994
H. Sarbazi-Azad , M. Ould-Khaoua , L. M. Mackenzie, Analytical modelling of wormhole-routed k-ary n-cubes in the presence of matrix-transpose traffic, Journal of Parallel and Distributed Computing, v.63 n.4, p.396-409, April
Jos Duato, A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.6 n.10, p.1055-1067, October 1995
Debashis Basak , Dhabaleswar K. Panda, Alleviating Consumption Channel Bottleneck in Wormhole-Routed k-ary n-Cube Systems, IEEE Transactions on Parallel and Distributed Systems, v.9 n.5, p.481-496, May 1998
Rajendra V. Boppana , Suresh Chalasani, A Framework for Designing Deadlock-Free Wormhole Routing Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.7 n.2, p.169-183, February 1996
Aniruddha S. Vaidya , Anand Sivasubramaniam , Chita R. Das, Performance benefits of virtual channels and adaptive routing: an application-driven study, Proceedings of the 11th international conference on Supercomputing, p.140-147, July 07-11, 1997, Vienna, Austria
Hamid Sarbazi-Azad , Mohamed Ould-Khaoua , Lewis M. Mackenzie, A Performance Model of Adaptive Wormhole Routing in k-Ary n-Cubes in the Presence of Digit-Reversal Traffic, The Journal of Supercomputing, v.22 n.2, p.139-159, June 2002
Federico Silla , Jos Duato, High-Performance Routing in Networks of Workstations with Irregular Topology, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.699-719, July 2000
Jos Duato, A Theory of Deadlock-Free Adaptive Multicast Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.6 n.9, p.976-987, September 1995
J. (Young-Joo) Suh , Binh Vien Dao , Jose Duato , Sudhakar Yalamanchili, Software-Based Rerouting for Fault-Tolerant Pipelined Communication, IEEE Transactions on Parallel and Distributed Systems, v.11 n.3, p.193-211, March 2000
Takashi Yokota , Masaaki Ogawa , Kanemitsu Ootsu , Takanobu Baba, Quasi-global routing for fault-tolerant high-performance interconnection networks, Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: parallel and distributed computing and networks, p.203-208, February 13-15, 2007, Innsbruck, Austria
W. Stephen Lacy , Jos L. Cruz-Rivera , D. Scott Wills, The Offset Cube: A Three-Dimensional Multicomputer Network Topology Using Through-Wafer Optics, IEEE Transactions on Parallel and Distributed Systems, v.9 n.9, p.893-908, September 1998
J. Duato , T. M. Pinkston, A General Theory for Deadlock-Free Adaptive Routing Using a Mixed Set of Resources, IEEE Transactions on Parallel and Distributed Systems, v.12 n.12, p.1219-1235, December 2001
Rajendra V. Boppana , Suresh Chalasani, Fault-Tolerant Communication with Partitioned Dimension-Order Routers, IEEE Transactions on Parallel and Distributed Systems, v.10 n.10, p.1026-1039, October 1999
Jongman Kim , Chrysostomos Nicopoulos , Dongkook Park , Reetuparna Das , Yuan Xie , Vijaykrishnan Narayanan , Mazin S. Yousif , Chita R. Das, A novel dimensionally-decomposed router for on-chip communication in 3D architectures, ACM SIGARCH Computer Architecture News, v.35 n.2, May 2007
Wenjian Qiao , Lionel M. Ni , Tomas Rokicki, Adaptive-Trail Routing and Performance Evaluation in Irregular Networks Using Cut-Through Switches, IEEE Transactions on Parallel and Distributed Systems, v.10 n.11, p.1138-1158, November 1999
Sugath Warnakulasuriya , Timothy Mark Pinkston, A Formal Model of Message Blocking and Deadlock Resolution in Interconnection Networks, IEEE Transactions on Parallel and Distributed Systems, v.11 n.3, p.212-229, March 2000
Jos Duato, A Theory of Fault-Tolerant Routing in Wormhole Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.8, p.790-802, August 1997
Aniruddha S. Vaidya , Chita R. Das , Anand Sivasubramaniam, A Testbed for Evaluation of  Fault-Tolerant Routing in  Multiprocessor Interconnection Networks, IEEE Transactions on Parallel and Distributed Systems, v.10 n.10, p.1052-1066, October 1999
Prasant Mohapatra, Wormhole routing techniques for directly connected multicomputer systems, ACM Computing Surveys (CSUR), v.30 n.3, p.374-410, Sept. 1998
Fleury , Pierre Fraigniaud, A General Theory for Deadlock Avoidance in Wormhole-Routed Networks, IEEE Transactions on Parallel and Distributed Systems, v.9 n.7, p.626-638, July 1998
Elizabeth Suet Hing Tse, Switch fabric design for high performance IP routers: a survey, Journal of Systems Architecture: the EUROMICRO Journal, v.51 n.10-11, p.571-601, October/November 2005
Chrysostomos A. Nicopoulos , Dongkook Park , Jongman Kim , N. Vijaykrishnan , Mazin S. Yousif , Chita R. Das, ViChaR: A Dynamic Virtual Channel Regulator for Network-on-Chip Routers, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.333-346, December 09-13, 2006
Jennifer Rexford , Wu-chang Feng , James Dolter , Kang G. Shin, PP-MESS-SIM: A Flexible and Extensible Simulator for Evaluating Multicomputer Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.1, p.25-40, January 1997
Tobias Bjerregaard , Shankar Mahadevan, A survey of research and practices of Network-on-chip, ACM Computing Surveys (CSUR), v.38 n.1, p.1-es, 2006
message passing;concurrency control;performance;index termsdeadlock-free adaptive routing;wormhole networks;telecommunication network routing;channeldependency graph;fault-tolerant algorithms;graph theory;routing algorithms;adaptive algorithm;fault tolerant computing