Fault-Tolerant Routing in Mesh-Connected Multicomputers based on Majority-Operator-Produced Transfer Direction Identifiers

The paper focuses on fault-tolerant 2D mesh-connected multicomputers, which can proceed operating even if some of their units and/or links are faulty, and more particularly, on the routing environment of the multicomputers capable of transferring packets between healthy processor units along the paths containing faulty components. A novel approach to the fault-tolerant packet routing is presented making it possible to increase the packet delivery probability by expanding the XY-routing scheme. The proposed approach is capable of recovering corrupted routing direction data contained in the address section of a packet by using the majority operator applied to the current direction IDs generated at the current and the two preceding hops on the route. Our simulation study shows that the successful routing probability increases at least by 40% with the new scheme; yet, it grows on as the route length increases compared to the XY-routing with no routing data recovery.