A Unified Algorithm for Both Randomized Deterministic and Adaptive Routing in Torus Networks

Torus networks are popular in large scale, high performance computing installations due to their use of relatively short cables and their incremental expandability. There are basically two types of traditional torus routing approaches: deterministic dimension ordered routing and adaptive routing. Traditional approaches to deterministic routing have known shortcomings under some traffic patterns, but adaptive routing creates challenges at the network end-point for programming models that expect ordered messages (e.g. MPI and SHMEM). This paper presents a new approach that supports both adaptive routing and improved throughput for deterministically routed (and therefore ordered) messages. In addition, whereas most current approaches to adaptive routing are designed for either mesh networks or virtual cut-through torus networks, the new routing algorithm allows for adaptive routing of messages on wormhole routed torus networks. The result is a routing algorithm that achieves a substantial portion of the benefit of adaptive routing while maintaining message ordering.