STORAGE-EFFICIENT, DEADLOCK-FREE PACKET ROUTING ALGORITHMS FOR TORUS NETWORKS

We present two new packet routing algorithms for parallel computers wi th torus interconnection networks of arbitrary size and dimension, Bot h algorithms use only minimal length paths, are fully adaptive in the sense that all minimal length paths may be used to avoid congestion, a nd are free of deadlock, livelock and starvation. Algorithm 1 requires only three central queues per routing node, It is the first known min imal length packet routing algorithm for torus networks which requires a constant number of queues per node, regardless of the size and dime nsion of the torus, In fact, the requirement of three queues per node is optimal, as no such algorithm is possible when all nodes have two o r fewer queues. Algorithm 2 requires only that each node have two inpu t buffers per edge, It is the first known minimal-fully-adaptive packe t routing algorithm for torus networks which does not require central queues and which does not require any node to have more than two input or two output buffers per edge. Both algorithms are simple and appear to be well-suited to VLSI implementation, They can be used with eithe r store-and-forward or virtual cut-through routing,