网格中基于最小连接块的启发式容错路由算法  

Heuristic Fault-Tolerant Routing in Mesh Using Minimal-Connected-Component Fault Blocks

作　　者：陈贵海[1] 杜鹏[1] 王大进[1] 谢立[1] 

机构地区：[1]南京大学计算机软件新技术国家重点实验室,江苏南京210093

出　　处：《电子学报》2004年第2期318-322,共5页Acta Electronica Sinica

基　　金：国家自然科学基金项目 (No.60 0 730 2 9) ;国家 973项目 (No .2 0 0 2CB31 2 0 0 2 ) ;教育部高校青年教师奖资助计划

摘　　要：矩形无效块模型可以用来解决网格下的容错路由问题 ,最小连接块 (MCC)模型是它的一个改良模型 .本文在MCC基础上 ,建立MCC重叠图 ,当发现不存在曼哈顿路径的时候 ,给出一套算法 ,来计算出一条避免无效块的尽可能短的路径 .模拟试验表明 ,通过这种算法找到的路径 ,与最短路径相差很小 .比起花费更多的时间去找寻最短路径 。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.

关 键 词：自适应路由 矩形无效块模型 容错性 网格 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]