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 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

choices.

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

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” trafﬁc 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 trafﬁc 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 ﬁnding 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 trafﬁc.

Start Free Trial

No credit card required