Fault-tolerant Routing for Irregular Faulty Patterns in 2D-Mesh Without Virtual Channel

In wormhole meshes, many fault-tolerant routing algorithms have been proposed. None of them, however, can tolerate general (irregular) fault model without virtual channels. In this paper, a 0-virtual channel fault-tolerant deadlock-free routing algorithm for general fault model is proposed for wormhole routing in two-dimensional meshes. Considering XY-routing as a precious property of two-dimensional meshes, we try to keep as many XY-routings as possible without incurring any deadlock. During the preprocessing, the mesh is divided into a number of fault-free (healthy) rectangular regions, and a minimum spanning tree connecting all these regions is built. Routing within a region uses XY-routing mainly, and routing across regions will use the spanning tree. An online solution is given for handling dynamic faults and recovery.