O'Reilly logo

Principles and Practices of Interconnection Networks by Brian Patrick Towles, William James Dally

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

8.3 The Routing Relation 163
Therefore these algorithms are referred to as minimal. As we have already seen, it’s
often important to include non-minimal routes and in this case, routing functions
choose paths from the set of all minimal and non-minimal routes R
xy
. These algo-
rithms are refered to as non-minimal. Again, from our simple example on the ring,
the greedy algorithm is minimal, while randomized and adaptive algorithms are non-
minimal.
8.3 The Routing Relation
It is useful to represent the routing algorithm as a routing relation R and a selection
function ρ. R returns a set of paths (or channels for an incremental routing algorithm),
and ρ chooses between these paths (or channels) to select the route to be taken. With
this division of the algorithm, issues relating to channel dependencies and deadlock
deal with the relation R while issues relating to adaptivity deal with the selection
function ρ. We address deadlock in detail as part of Chapter 14.
Depending on whether our algorithm is incremental, and whether it is node-
based or channel-based, we define R in three different ways:
R : N × N P(P ) (8.1)
R : N × N P(C) (8.2)
R : C × N P(C) (8.3)
where P(X) denotes the power set, or the set of all subsets, of the set X. This notation
allows us to reflect the fact that a routing relation may return multiple paths or
channels, one of which is chosen by the selection function.
When the output of the routing relation is an entire path, as in Relation 8.1 —
the first of our three routing relations, the routing algorithm is referred to as all-
at-once. This name reflects exactly how the routing algorithm is used. When a packet
is injected into the network at the source node x destined to node y, the routing
relation is evaluated: U = R(x,y). Since U may be a set of routes, one is selected and
assigned to the packet. Of course, U does not have to include all possible routes R
xy
or even all minimal routes R
xy
, and in the case of a deterministic routing algorithm,
it returns only one (|U |=1). Once the route is chosen, it is stored along with the
packet. As we will see in Chapter 11, all-at-once routing minimizes the time spent
evaluating the routing relation for each packet, but this advantage comes with the
overhead of carrying the routes inside the packets.
An alternate approach is incremental routing, where the relation returns a set of
possible channels. Instead of returning an entire path at once, the routing relation is
evaluated once per hop of the packet. The output of the relation is used to select
the next channel the packet follows. In Relation 8.2, the second form of the routing
relation, for example, the inputs to the relation are the packet’s current node w and
its destination y. Evaluating the relation gives us a set of channels D = R(w, y),
where each element of D is an outgoing channel from w or D C
Ow
. The selec-
tion function is then used to choose the next channel used by the packet from D.
This incremental process is repeated until the packet reaches its final destination.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required