Fault-tolerance with multimodule routers

The current multiprocessors such as Cray T3D support interprocessor communication using partitioned dimension-order routers (PDRs). In a PDR implementation, the routing logic and switching hardware is partitioned into multiple modules, with each module suitable for implementation as a chip. This paper proposes a method to incorporate fault-tolerance into such routers with simple changes to the router structure and logic. The previously known fault-tolerant routing methods assume centralized crossbar based routers and are not applicable to multiprocessors with PDRs. The proposed technique works for convex fault model, using only local knowledge of faults. Using the proposed techniques and as few as four virtual channels per physical channel, torus networks with PDRs can handle faults without compromising deadlock- and livelock-freedom. Simulations for 2-dimensional torus and mesh networks show that the resulting fault-tolerant PDRs have performances similar to those of the crossbar based routers