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 P_Sy,Sx represent the position of the source node and P_Dy,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 P_Sy,Sx+1, P_Sy,Sx+2, ..., P_Sy,Dx along the X dimension and then through nodes P_Sy+1,Dx, P_Sy+2,Dx, ..., P_Dy,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 P_s and P_d 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 P_s P_d (where represents the bitwise exclusive-OR operation). In the E-cube algorithm, node P_s computes P_s P_d and sends the message along dimension k, where k is the position of the least significant nonzero bit in P_s P_d . At each intermediate step, node P_i , which receives the message, computes P_i P_d 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.

In the rest of this book we assume deterministic and minimal message routing for analyzing parallel algorithms.