Designing maximally adaptive algorithms for wormhole routing: the turn model
Christopher J. Glass · 1992
One obstacle to using wormhole routing as the switching technique in a direct network is designing a good algorithm for routing message packets through the network. A good routing algorithm should provide low communication latency, high network throughput, and ease of implementation in VLSI. Contributing to these objectives are such factors as deadlock freedom, adaptive routing, nonminimal routing, livelock freedom, and fault tolerance. Previous models for designing routing algorithms have been either ad hoc or based on adding virtual channels to the networks. The algorithms produced by these models prevent deadlock, but the cost is either non-adaptiveness in routing or extra hardware to support virtual channels. To solve the design problem more completely, this dissertation presents a model for systematically designing routing algorithms that are deadlock free and maximally adaptive for a network, as well as minimal or nonminimal, livelock free, and fault tolerant. The model is not based on adding virtual channels to a network, but can be applied to networks that have virtual channels. Instead, the model is based on analyzing the directions in which packets can turn in a network and the cycles that the turns can form. This turn model is applied to n-dimensional meshes and k-ary n-cubes in the dissertation, but it can be applied to any direct network that has directions associated with its channels. Simulations of the routing algorithms produced for meshes and hypercubes show that they can perform better than previous routing algorithms.