A General Fault-Tolerant Minimal Routing for Mesh Architectures

Fault-tolerant minimal routing algorithms aim at finding a Manhattan path between the source and destination nodes and route around all faulty nodes. Additionally, some non-faulty nodes that are helpless to make up of a fault-tolerant minimal path should also be routed around. How to label such non-faulty nodes efficiently is a major challenge. State-of-the-art solutions could not address it very well. We propose a path-counter method. It can label every node that are helpless to make up of a fault-tolerant minimal path with low time complexity. By counter the number of fault-tolerant minimal paths, it can: support arbitrary fault distribution, check the existence of fault-tolerant minimal paths, not sacrifice any available fault-tolerant minimal paths.