Adaptive Deadlock- and Livelock-Free Routing in Torus Networks
Pablo E. Berman · 1992
This paper consists of two parts. In the first part, a new algorithm for deadlock- and livelock-free routing for the n-dimensional torus network is presented. This algorithm, called *-Channels, is fully-adaptive minimal, i.e. all paths with a minimal number of hops from source to destination are available for routing. *- (7hannels works for messages of unknown size, thus yielding new routing techniques for both packet-switched and worm-hole models. *-Channels differs radically from the packetswitched fully-adaptive minimal methods presented in SPAA ’91 by Pifarr6, Gravano, Felperin, and Sanz [PGFS91]. In particular, the packet-based techniques in [PGFS91] do not work for worm-hole routing as deadlock situations can be constructed.