Fault-Tolerant Adaptive and Minimal Routing in 2D-Mesh Using Region of Minimal Paths
二维网格中基于最小通路区的自适应和最小容错路由算法

Mesh is a popular topology for connecting processors in parallel computers.The design of fault-tolerant minimal routing algorithms in multiprocessors with nodes fault is always an issue of researches.The minimal routing problem in 2D-mesh with fault blocks is studied in this paper.We propose a sufficient and necessary condition for minimal routing in 2D-mesh.A fault-tolerant adaptive and minimal routing algorithm is presented,which is based on the idea of Region of Minimal Paths(RMP).If there exists RMP from the source node to the destination node,messages use fault-tolerant adaptive and minimal routing in RMP.Otherwise,messages use multi-phase minimal fault-tolerant routing.The main idea is that the shortest path is selected whenever possible because multiprocessors with fault nodes.The algorithm is distributed because it requires only local information at every node.