8.7 Exercises 171
8.1 Tradeoffs between routing algorithms. Reconsider the routing algorithms and network
from Section 8.1. Which algorithm would you choose to optimize for the following:
(a) Minimum message latency.
(b) Best throughput under uniform trafﬁc.
(c) Highest average throughput over many permutation trafﬁc patterns.
Limit your choice to one algorithm for each of the different criteria and defend your
8.2 Limitations of incremental routing. Describe a routing algorithm that could be speciﬁed
using the the path-based relation from Relation 8.1, but could not be expressed with
either of the incremental forms from Relations 8.2 and 8.3.
8.3 Header bits for incremental and all-at-once routing. Destination tag routing can be
implemented as either an incremental or all-at-once algorithm. Compute the num-
ber of bits that need to be stored along with the packet to implement each approach.
Does one approach require fewer bits? Does this relationship hold for minimal rout-
ing in a general topology? How is this related to the path diversity of the topology?
8.4 Backtracking in the ring. Suppose we allow backtracking in the routing example
of Section 8.1. Is it possible to develop an algorithm that gives better worst-case
throughput than the weighted random algorithm? If so, give such an algorithm; oth-
erwise, explain why no such algorithm exists.
8.5 Routing in a butterﬂy with extra stages. Describe a deterministic extension for
destination-tag routing to handle a k-ary n-ﬂy with one or more extra stages. Suggest
a simple way to introduce randomization into this algorithm to improve load balance.
8.6 Direction-order routing in the Cray T3D. Suppose you rearrange the labels on the Cray
T3D router’s channels in Figure 8.6 so that the ﬁrst router handles +x and +y, the
second router handles +z and −x, and the third router handles −y and −z. Describe
a routing algorithm that can work with this partitioning. Remember that once a
packet reaches each of the three routers, it can never return to the previous routers.
8.7 Advantages of direction-order routing. Consider the routing algorithm you derived
for Exercise 8.6. What advantages does this algorithm have over dimension-order
8.8 Routing to and from I/O nodes in the T3D. I/O nodes are added to a T3D network
only in the x and z dimensions by adding an additional x and/or z coordinate to a
3-cube. For example, suppose you have a 64-node 4-ary 3-cube with nodes addressed
from (0,0,0) to (3,3,3). An I/O node might be added with address (4,0,0) or (0,0,4).
Explain how you can assign each I/O node a pair of addresses so that it is always
possible to route from any node in the interior of the machine to the I/O node and
from the I/O node to any interior node using dimension-order routing.