ON THE ROUTING OF SIGNALS IN PARALLEL PROCESSOR MESHES

Wormhole message routing is supported by the communication hardware of several distributed memory machines. This particular method of messag e routing has numerous advantages but creates the problem of a routing deadlock. When long messages compete for the same channels in the net work, some messages will be blocked until the first message is fully c onsumed by the processor at the destination of the message. A deadlock occurs if a set of messages mutually blocks, and no message can progr ess towards its destination. Most deadlock free routing schemes previo usly known are designed to work on regular binary hypercubes, a very s pecial case of multicomputer interconnection networks. However, these routing schemes do not provide enough flexibility to deal with the irr egular 2-D-tori and attached auxiliary cells found on many newer paral lel systems. To handle irregular topologies elegantly, a simple proof is necessary to verify the router code. The new proof given in this re port is carried out directly on the network graph. It is constructive in the sense that it reveals the design options to deal with irregular ities and shows how additional flexibility can be used to achieve bett er load balancing. Based on the modified routing model, a set of deadl ock free router functions relevant to the 1Warp system configurations