Torus网络自适应容错路由算法  

Adaptive Fault-tolerant Routing in Torus Networks

作　　者：段新明[1,2] 武继刚[1,2] 张大坤[1,2] 

机构地区：[1]天津工业大学计算机科学与软件学院,天津300387 [2]中国科学院软件研究所计算机科学国家重点实验室,北京100190

出　　处：《计算机科学》2012年第2期115-117,153,共4页Computer Science

基　　金：国家自然科学基金(60970016)资助

摘　　要：在应用于大规模并行计算机的互连网络的设计中,容错问题是其中的一个关键问题和难点问题。提出了一种基于Torus虫孔交换网络的容错路由算法,这一算法使用了矩形故障模型,无论故障区域大小多少和如何分布,算法始终是无死锁的,而且具有足够的自适应性,只要故障节点没有断开网络的连接,算法就能够通过选路使消息绕过故障区域,保持路由的连通性。同时,算法仅需要使用3个额外的虚拟通道。最后算法在不同故障率的Torus网络中进行了仿真实验,结果显示这一算法具有良好的平滑降级使用的特性。Fault tolerance is one of the most dominant issues for the design of interconnection networks of large-scale multiprocessor systems.A new fault tolerant routing algorithm for wormhole torus network was proposed.The routing algorithm provides enough adaptability so that it is always connected as long as fault regions do not disconnect the network.In spite of the variety of fault components in torus,the proposed routing algorithm is always connected and deadlock-free.At the same time,the proposed algorithm only employs extra three virtual channels.The result of simulation shows that the proposed routing algorithm is of feasibility of gracefully degraded operation.

关 键 词：带环网格 路由算法 容错 无死锁 

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