Hotspot Avoidance

  One important advantage of scheduled routing is its ability to make full use of a network's internal bandwidth when presented with data patterns that normally cause hotspotting in the network. For example, a bit-reversal routing can be efficiently distributed across the bisection by precomputing the paths that all the data will follow. Less-structured communication can also be routed cleverly so as to avoid problems from contention in the network. In general, when using all the scheduled streams at full bandwidth, the only time that communications will run slower than the actual path distance between nodes is when the network bandwidth needed is inadequate, not just because of contention artifacts.

  

Figure 1.1: Bitreversal on a small mesh

Figure 1.1 shows a simple communication pattern that demonstrates this problem. Each node transfers data to the node whose number is the bit-reversal of its own number; thus node 2 (binary 0010) transfers its data to node 4 (binary 0100). When transferring data using standard dynamic-routing schemes, messages will tend to saturate particular links in the mesh. For example, using e-cube routing (where messages travel first in the x dimension, then the y ), all the data from the top and bottom rows will flow using along the links on the edges of the mesh, using none of the central links. As the mesh grows (particularly for 3D meshes), the problem gets worse. With scheduled routing, good paths can be found for all the communications; Figure 1.2 shows possible scheduled paths for the $4\times 4$ example.

  

Figure 1.2: Scheduled paths for bitreversal on a small mesh

Figure 1.3 shows the results of a simple benchmark for bitreversal using different routing techniques. 512 data words are transferred between each pair of nodes with bitreversed addresses. Regular e-cube dynamic routing is shown, as is a simple adaptive routing technique from [21], and a scheduled-routing algorithm. The scheduled-routing algorithm schedules a route for all the streams at compile time by rerouting streams one at a time until it finds a good path, using only per-link bandwidths to determine legal routes. The dynamic routing cycle counts are gathered by simulation, and the scheduled routing cycle counts by scheduling a path and deriving the number of cycles a message takes to flow across the paths given the allocated bandwidths.

  

Figure 1.3: Bitreversal routing (dynamic vs. scheduled routing)

The graph shows that the latency (expressed in cycles) for the two dynamic routing techniques is worse than for scheduled routing, and rising faster as the graph grows larger. Adaptive routing comes close in cycle count to scheduled routing, but to do that it must pay a price in router complexity and resulting slower cycle times.