the global and local channels. This randomized non-minimal routing traverses at most two global
channels and requires five steps:
Step 1 :If G s = G i
and R s
does not have a connection to G i , route within G s
from R s
R a , a router that has a global channel to G i .
Step 2 :If G s = G i traverse the global channel from R a to reach router R x in G i .
Step 3 :If G i = G d and R x does not have a connection to G d , route within G i from R x to
R y , a router that has a global channel to G d .
Step 4 :If G i = G d , traverse the global channel from R y
to router R b
in G d .
Step 5 :If R b =
R d , route within G d from R b to R d .
Figure 5.4 shows how VCs [ 21 ] are used to avoid routing deadlock. To prevent routing
deadlock [ 19 ], two VCs are needed for minimal routing and three VCs are required for non-minimal
routing. This assignment eliminates all channel dependencies due to routing. For some applications,
additional virtual channels may be required to avoid protocol deadlock — e.g., for shared memory
systems, separate sets of virtual channels are required for request and reply messages. Based on these
descriptions of minimal and nonminimal routing, adaptive routing algorithms described earlier in
this chapter can also be applied to the dragonfly topology.
Although the topology determines the performance bounds, the routing algorithm is critical in
determining how much of this performance can be realized. Recently proposed high-radix topologies
rely on proper adaptive routing algorithms to load-balance both the minimal and non-minimal
channels. High-radix networks also present interesting challenges to adaptive routing because of
indirectness of network congestion information and we demonstrate how indirect adaptive routing
is needed for these routing algorithms.