Deadlock free wormhole routing in a faulty torus networks

Torus and mesh-connected networks have been widely used in recent experimental or commercial multi computers and multiprocessors [2]. The majority of these multi computers use dimension-order or e-cube routing with wormhole switching. Wormhole routing is a form of cut-through routing in which blocked messages hold on to the channels they already reserved. The performance of such multi computers is highly dependent on the node-to-node communication cost. The huge number of nodes and associated devices of these machines significantly affect the probability of failure. In reality, the loss of communication between any two nodes might prevent a distributed recovery, because the state of the computation in the isolated nodes is unreachable. Therefore, it is necessary to address an effective fault-tolerant routing algorithm in a torus/mesh networks. For networks with faults, a routing algorithm should exhibit the following additional features: graceful degradation of performance, ability to support reasonably large number of faults with only small increase in routing logic complexity and without disabling any non-faulty node. Thus, fault-tolerant routing algorithm for wormhole routed torus networks should be designed taking the above mentioned features into consideration.