Fully Adaptive Minimal Deadlock-Free Packet Routing in Hypercubes, Meshes, and Other Networks: Algorithms and Simulations

Abstract

This paper deals, with the problem of packet-switched routing in parallel machines. Several new routing algorithms for different interconnection networks are presented. While the new techniques apply to, a wide variety of networks, routing algorithms will be shown for the hypercube, the two-dimensional mesh, and the shuffle-exchange. Although the new techniques are designed for packet routing, they can be used alternatively for virtual cut-through routing models. The techniques presented for hypercubes and meshes are fully-adaptive and minimal. A fully-adaptive and minimal routing is one in which all possible minimal paths between a source and a destination are of potential use at the time a message is injected into the network. Minimal paths followed by messages ultimately depend on the local congestion encountered in each node of the network. In the shuffle-exchange network, the routing scheme also exhibits adaptivity but paths could be up to 3log N long for an N node machine. The shuffle-exchange algorithm is the first adaptive and deadlock-free method that requires a small (and independent of N) number of buffers and queues in the routine nodes for that network. Furthermore, all of the new techniques are completely free of deadlock situations. In dynamic message injection models, the routing methods are also ensured to be free of livelock if messages competing for resources are handled with fairness. In contrast to other approaches in which adaptivity, deadlock and livelock freedom can be guaranteed at the expense of complex architectures, the algorithms presented in this paper require a very moderate amount of routing resources. In particular, it will be shown that only two central queues per routing node of the network are necessary for the cases of the two-dimensional mesh and the hypercube. and four queues for the shuffle-exchange. Simulations are reported showing the performance of the routing algorithms for two-dimensional meshes and hypercubes for different traffic models: random, complement, transpose, bit-reversal and leveled permutations. The performance of the routing algorithms is measured in terms of throughput, maximum and average latency, and saturation point. In the case of the mesh network, the new method is compared to an oblivious scheme similar to the x-y or e-cube router. Simulation results are reported for hypercubes up to 16-K nodes and for meshes of 1-K nodes. These results demonstrate that the new algorithms outperform oblivious e-cube-type techniques. © 1994 IEEE