Mesh网中高效无死锁自适应路由算法  

Deadlock-Free Adaptive Routing in Fault-Tolerant Mesh Networks

作　　者：向东[1] 张跃鲤[2] 

机构地区：[1]清华大学软件学院,北京100084 [2]清华大学计算机科学与技术系,北京100084

出　　处：《计算机学报》2007年第11期1954-1962,共9页Chinese Journal of Computers

基　　金：国家杰出青年基金(60425203);国家自然科学基金面上基金(60573055)~~

摘　　要：提出了一种新的应用于三维Mesh网中的无死锁路由算法.在当今的商用多计算机系统中,二维和三维的Mesh网是多处理器网络最为常用的拓扑结构之一.在应用于Mesh网的平面自适应路由(Planar Adaptive Rou-ting)算法中,每条物理通道只需三条虚拟通道就可以有效地在三维以及更高维的Mesh网中避免死锁的产生.然而,采用该算法,网络拓扑一维和三维分别有两条和一条虚拟通道始终处于空闲状态.该文所提出的算法针对三维Mesh网,每条物理通道只需两条虚拟通道就可以有效地避免死锁.文中通过充分的模拟数据验证了此算法的有效性.A new deadlock-free routing algorithm is proposed for 3-dimensional meshes. Most of the recent commercial machines are constructed using 2D or 3D meshes. The planar adaptive routing scheme was proposed and effective deadlock avoidance technique use only three virtual channels for each physical channel in 3-dimensional or higher dimensional mesh networks. However, there exist two idle virtual channels for all channels along the first dimension, and one idle virtual channel for channels along the third dimension. A new deadlock avoidance technique is proposed for 3-dimensional meshes using only two virtual channels for each physical channel. Sufficient simulation results are presented to demonstrate the effectiveness of the proposed algorithm.

关 键 词：容错路由 完全自适应路由 部分自适应路由 平面自适应路由 MESH网 

分 类 号：TP306[自动化与计算机技术—计算机系统结构]