The Multi-level Communication: Minimal Deadlock-Free and Storage Efficient Routing for Torus Networks

In this paper, we recall the methodology, proposed in [7], for constructing correct and efficient routing strategies for distributed memory multicomputers. As the methodology is based on a primary communication scheme, we choose routing by Eulerian cycle rules [9] as the primary one. We first propose an improvement of this latter routing scheme. Then, we apply the general routing strategy to the torus network. We give a detailed proof of a result for this network. From this proof, we deduce a new static, deadlock-free and minimal algorithm which uses an optimal memory space and a cycle free dependency graph.