二维网格中基于最小通路区的自适应和最小容错路由算法  

Fault-Tolerant Adaptive and Minimal Routing in 2D-Mesh Using Region of Minimal Paths

作　　者：陈文斌[1] 杨小帆[1] 苏伟[1] 唐荣旺[1] 曾智[1] 

机构地区：[1]重庆大学计算机学院,重庆400044

出　　处：《计算机科学》2006年第7期292-294,F0003,共4页Computer Science

基　　金：重庆市自然科学基金资助课题(批准号:CSTC;2005BB2191)

摘　　要：网格结构是并行与分布式处理中最流行的一种网络拓扑结构。在存在故障的情况下,如何设计具有最优性的容错路由算法一直是研究的热点问题。本文研究了采用故障块模型的二维网格的最小路由问题,提出存在最小通路的一个充分必要条件。基于最小通路区(RMP)的概念,提出一种自适应的最小容错路由算法。如果源节点和目的节点之间存在最小通路区,则在最小通路区中进行自适应最小容错路由;反之,则采用多阶段最小容错路由。主要思想就是在存在故障的情况下,尽量保证路由算法能走最短路径。因为只要求知道每个节点的局部信息,故算法是分布式的。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 faulttolerant 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.

关 键 词：容错 网格 最小路由 最小通道区 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP302.8[自动化与计算机技术—计算机科学与技术]