LCFAA:一个低代价的完全自适应路由算法  

LCFAA: A LOW COST FULLY ADAPTIVE ROUTING ALGORITHM

作　　者：刘燕[1] 孙利民[1] 杨晓东[1] 

机构地区：[1]国防科学技术大学计算机科学系

出　　处：《计算机研究与发展》1999年第3期331-336,共6页Journal of Computer Research and Development

基　　金：国家"八六三"高技术计划;"九五"国防预研基金

摘　　要：大规模并行处理机系统（ＭＰＰ）中路由算法对互联网络通信性能和系统性能起着重要作用．自适应路由算法具有灵活性好、网络的通道利用率高和网络容错能力强等优点，但其实现难度较大，因而目前仅在少数ＭＰＰ系统中得以实现．文中在ｍｅｓｈ结构上提出了一个低代价无死锁的完全自适应最短虫孔路由算法ＬＣＦＡＡ，该算法所需虚通道数少，具有代价低、自适应性强的特点．文中证明了算法的无死锁、无活锁性和完全自适应性，并模拟验证了其性能．Routing algorithm constitutes the primary factor influencing on the performance of massively parallel processors(MPP) system. The use of fully adaptive routing in an MPP interconnection network improves network performance by making use of all available paths and provides fault tolerance by allowing messages to be routed around failed channels and nodes. But it's difficult to implement adaptive routing algorithm, and this limits its wide use in MPP systems, especially in commercial MPP systems. To reduce the implement complexity of adaptive routing algorithm and implement it simply and efficiently, the implement complexity problem in routing algorithm design is considered. By reducing the virtual channel requirements and imposing fewer restrictions on the choice of virtual channels, a deadlock free fully adaptive minimal wormhole routing algorithm LCFAA is presented, which needs very few virtual channels on every physical channel (3 n 1 virtual channels per router, not including the channels to or from the node) in n dimensional mesh. Compared with other proposed fully adaptive routing algorithms, LCFAA is fully adaptive with low cost, easy to implement, and scalable. Finally, the deadlock free property of LCFAA is proved, and its performance is demonstrated by simulation.

关 键 词：并行处理机系统 自适应路由算法 LCFAA 互联网络 

分 类 号：TP338.016[自动化与计算机技术—计算机系统结构] TP393[自动化与计算机技术—计算机科学与技术]