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.7 Exercises 171
8.7 Exercises
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 traffic.
(c) Highest average throughput over many permutation traffic patterns.
Limit your choice to one algorithm for each of the different criteria and defend your
choices.
8.2 Limitations of incremental routing. Describe a routing algorithm that could be specified
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 butterfly with extra stages. Describe a deterministic extension for
destination-tag routing to handle a k-ary n-fly 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 first 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
routing?
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.
172 CHAPTER 8 Routing Basics
8.9 Balancing “halfway around” traffic in tori. For dimension-order routing, we discussed
the load balance issues that arise when a node is exactly halfway around a ring of
a torus. If we always chose the positive direction in this halfway case instead of
load-balancing, how would this affect the throughput of uniform traffic on a k-ary
n-cube with k even? What’s the worst-case throughput in this case? Express your
results in terms of fraction of capacity. Suggest a way to improve load balance for the
halfway case while maintaining a deterministic algorithm. Recalculate the uniform
and worst-case throughputs.
8.10 Minimal routing in CCCs. Design a near minimal routing algorithm for a general
CCC topology described in Exercise 5.8. Opt for simplicity rather than finding ex-
act minimal routes in all cases, but be sure that no path generated by the algorithm
is greater than the diameter H
max
= 2n +n/2−2, as shown in [128]. Comment
on the load balance of your routing algorithm under uniform traffic.

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