Multiphase minimal fault-tolerant wormhole routing in 2D meshes

Abstract

A fault-tolerant wormhole routing algorithm using multi-phase minimal routing paths for mesh networks is proposed in this paper. When routing messages come in contact with a fault region, they always select a local shortest path around the fault-region in clockwise or counter clockwise direction. The proposed algorithm can tolerate convex fault-connected regions with four virtual channels per physical channel regardless of how processors of different f-polygons overlap. The fault regions divide each routing path into multiple minimal routing paths-a multiphase minimal routing path. The performance of multiphase minimal routing vs. minimal routing is compared by simulation.