Adaptive and fault-tolerant schemes for routing messages in a 2D torus interconnection network for distributed memory multi-computers (message passing concurrent computers) are presented. For the adaptive scheme, two new techniques, channel switching and dimension switching, are developed and proved deadlock-free. For the fault-tolerant scheme, a message can be rerouted to a virtual destination, which in turn sends the message to the real destination. This scheme can tolerate all single faults and many multiple faults, and is deadlock-free. The two routing schemes are suitable for the high performance virtual cut-through and wormhole routing. The required hardware overhead for realizing the fault-tolerant scheme is small and no time penalty is paid in the fault-free case.
All Science Journal Classification (ASJC) codes