A Fault-Tolerant Routing Protocol in 2D Torus Based on Positive-first and Negative-first Turn Models

摘要

A kind of routing scheme with the ability to tolerate the faults is necessary in the massively parallel multiprocessors. In this paper, we would present a fault-tolerant wormhole routing scheme, called Positive-first-Negative-first scheme, in the torus network with Orthogonal Convex Polygon faults model, this fault-tolerant routing scheme is motivated by the PFNF routing algorithms that with positive-first and negative-first turn restriction implement in two virtual networks. Because of the mutual-switch of turn schemes between the two virtual networks, the routing algorithm is nearly fully adaptive without deadlock, so it can convenience and efficient applied in the fault-tolerant routing by employing the algorithm self-property. The reason why we choose the Orthogonal Convex Polygon faulty model is that it is convenient to design a simple and efficient tolerant-tolerant routing algorithm, at the same time the number of disabled healthy nodes in the fault block is reduced at the moderate level. Sufficient simulation results are presented to demonstrate the effectiveness of the proposed algorithm.