Message routing on irregular 2D-meshes and tori

Abstract: "Wormhole message routing is supported by the communication hardware of several distributed memory machines. This particular method of message routing has numerous advantages but creates the problem of a routing deadlock. When long messages compete for the same channels in the network, some messages will be blocked until the first message is fully consumed by the processor at the destination of the message. A deadlock occurs if a set of messages mutually blocks, and no message can progress towards its destination. Most deadlock free routing schemes previously known are designed to work on regular binary hypercubes, a very special case of multicomputer interconnection networks.However, these routing schemes do not provide enough flexibility to deal with the irregular 2-D-tori and attached auxiliary cells found on many newer parallel systems. To handle irregular topologies elegantly, a simple proof is necessary to verify the router code. The new proof given in this report is carried out directly on the network graph. It is constructive in the sense that it reveals the design options to deal with irregularities and shows how additional flexibility can be used to achieve better load balancing. Based on the modified routing model, a set of deadlock free router functions relevant to the iWarp system configurations are described and proven to be correct."