ADAPTIVE DEADLOCK-FREE AND LIVELOCK-FREE ROUTING WITH ALL MINIMAL PATHS IN TORUS NETWORKS

This paper consists of two parts. In the first part, two new algorithm s for deadlock- and livelock-free wormhole routing in the torus networ k are presented. The first algorithm, called -Channels, is for the n- dimensional torus network. This technique is fully-adaptive minimal, t hat is, all paths with a minimal number of hops from source to destina tion are available for routing, and needs only five virtual channels p er bidirection link, the lowest channel requirement known in the liter ature for fully-adaptive minimal worm-hole routing. In addition, this result also yields the lowest buffer requirement known in the literatu re for packet-switched fully-adaptive minimal routing. The second algo rithm, called 4-Classes, is for the bidimensional torus network. This technique is fully-adaptive minimal and requires only eight virtual ch annels per bidirectional link. Also, it allows for a highly parallel i mplementation of its associated routing node. In the second part of th is paper, four worm-hole routing techniques for the two-dimensional to rus are experimentally evaluated using a dynamic message injection mod el and different traffic patterns and message lengths.