A FAULT-TOLERANT WORMHOLE ROUTING ALGORITHMS IN 2-DIMENSIONAL MESH NETWORKS

We propose a fault-tolerant routing algorithm for 2D meshes. Our routi ng algorithm can tolerate any number of concave fault regions. It is b ased on xy-routing and uses the concept of the fault ring/chain compos ed of Fault-free elements surrounding faults. Three virtual channels p er physical link are used for deadlock-free routing on a fault ring. F our virtual channels are needed for a fault chain. For a concave fault ring, fault-free nodes in the concave region have been deactivated to avoid deadlock in the previous algorithms, which results in excessive loss of the computational power. Our algorithm ensures deadlock-freed om by restricting the virtual channel usage in the concave region, and it minimizes the loss of the computational power. We also extend the proposed routing scheme for adaptive fault-tolerant routing. The adapt ive version requires the same number of virtual channels as the determ inistic one.