Heuristic fault-tolerant routing in mesh using minimal-connected-component fault blocks

Rectangular fault block model is designated to solve the problem of fault-tolerant route in mesh and was improved as Minimal-Connected-Component (MCC) model. Based on MCC, we construct an overlapping graph and give a set of algorithm according to the graph to work out the route as short as possible to avoid the appearance of fault block when Manhattan route does not exist. The simulated test shows that the route found by the algorithm mentioned above is nearly the shortest one. Hence compared to other methods costing much more time, this new heuristic fault-tolerant algorithm is of no doubt a better method in finding the shortest route.