A positive-first and negative-first fault-tolerant routing schemes for concave and convex faults

Routing schemes with the ability to tolerate the faults are important in the massively parallel multiprocessors networks. In this paper, we propose a kind of fault-tolerant routing schemes called positive-first and negative-first (PFNF) for orthogonal concave and convex fault blocks in torus network, which is based on the turn property of PFNF adaptive routing algorithm. In comparison with previous methods, the computation cost of our routing schemes is very low and it can not only easily apply in convex fault block but also in concave fault block, so the disabled healthy nodes can be reduced at the most level. Due to the mutual-switching of turn schemes between two virtual networks, the virtual channel utilization is greatly increased, which is benefic for the traffic-balance and the improvement of system throughput. Sufficient simulation results are presented to demonstrate the effectiveness of the proposed algorithm.