Multi-phase minimal fault-tolerant wormhole routing in meshes

Abstract

In a multiprocessor system, it is important that the shortest path is always selected for inter-process communication. If every node in the system can acquire the accurate status of all nodes, then optimal routing is possible, but this is not feasible in view of the space and time costs involved. We propose a fault-tolerant wormhole routing algorithm for the mesh network in this paper, which is based on the idea of multi-phase minimal routing. The algorithm requires only local information at every node. When messages in transit come in contact with a fault region, they would select a locally minimal path around the region. The proposed algorithm can tolerate convex fault regions with only four virtual channels per physical channel regardless of how processors of different fault regions may overlap. The aggregation of locally minimal path segments gives a complete routing path between source and destination. Via simulation, we find that the algorithm has near optimal performance in most cases. © 2004 Elsevier B.V. All rights reserved.