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

Deadlock-Free Adaptive Routing in Fault-Tolerant Mesh Networks

提出了一种新的应用于三维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.