2.6 Routing Mechanisms for Interconnection Networks
Efficient algorithms for routing a message to its destination are critical to the performance of parallel computers. A routing mechanism determines the path a message takes through the network to get from the source to the destination node. It takes as input a message's source and destination nodes. It may also use information about the state of the network. It returns one or more paths through the network from the source to the destination node.
Routing mechanisms can be classified as minimal or non-minimal. A minimal routing mechanism always selects one of the shortest paths between the source and the destination. In a minimal routing scheme, each link brings a message closer to its destination, but the scheme can lead to congestion in parts of the network. A non-minimal routing scheme, in contrast, may route the message along a longer path to avoid network congestion.
Routing mechanisms can also be classified on the basis of how they use information regarding the state of the network. A deterministic routing scheme determines a unique path for a message, based on its source and destination. It does not use any information regarding the state of the network. Deterministic schemes may result in uneven use of the communication resources in a network. In contrast, an adaptive routing scheme uses information regarding the current state of the network to determine the path of the message. Adaptive routing detects congestion in the network and routes messages around it.
One commonly used deterministic minimal routing technique is called dimension-ordered routing. Dimension-ordered routing assigns successive channels for traversal by a message based on a numbering scheme determined by the dimension of the channel. The dimension-ordered routing technique for a two-dimensional mesh is called XY-routing and that for a hypercube is called E-cube routing.
Consider a two-dimensional mesh without wraparound connections. In the XY-routing scheme, a message is sent first along the X dimension until it reaches the column of the destination node and then along the Y dimension until it reaches its destination. Let PSy,Sx represent the position of the source node and PDy,Dx represent that of the destination node. Any minimal routing scheme should return a path of length |Sx - Dx| + |Sy - Dy|. Assume that Dx Sx and Dy Sy. In the XY-routing scheme, the message is passed through intermediate nodes PSy,Sx+1, PSy,Sx+2, ..., PSy,Dx along the X dimension and then through nodes PSy+1,Dx, PSy+2,Dx, ..., PDy,Dx along the Y dimension to reach the destination. Note that the length of this path is indeed |Sx - Dx| + |Sy - Dy|.
E-cube routing for hypercube-connected networks works similarly. Consider a d-dimensional hypercube of p nodes. Let Ps and Pd be the labels of the source and destination nodes. We know from Section 2.4.3 that the binary representations of these labels are d bits long. Furthermore, the minimum distance between these nodes is given by the number of ones in Ps Pd (where represents the bitwise exclusive-OR operation). In the E-cube algorithm, node Ps computes Ps Pd and sends the message along dimension k, where k is the position of the least significant nonzero bit in Ps Pd . At each intermediate step, node Pi , which receives the message, computes Pi Pd and forwards the message along the dimension corresponding to the least significant nonzero bit. This process continues until the message reaches its destination. Example 2.16 illustrates E-cube routing in a three-dimensional hypercube network.
Example 2.16 E-cube routing in a hypercube network
Consider the three-dimensional hypercube shown in Figure 2.28. Let Ps = 010 and Pd = 111 represent the source and destination nodes for a message. Node Ps computes 010 111 = 101. In the first step, Ps forwards the message along the dimension corresponding to the least significant bit to node 011. Node 011 sends the message along the dimension corresponding to the most significant bit (011 111 = 100). The message reaches node 111, which is the destination of the message.
Figure 2.28. Routing a message from node Ps (010) to node Pd (111) in a three-dimensional hypercube using E-cube routing.
In the rest of this book we assume deterministic and minimal message routing for analyzing parallel algorithms.