Deadlock-Free Adaptive Routing in Meshes Based on Cost-Effective Deadlock Avoidance Schemes
Deadlock-Free Adaptive Routing in Meshes Based on Cost-Effective Deadlock Avoidance Schemes
复制标题
DOI：
10.1109/icpp.2007.30
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
D. Xiang;Yueli Zhang;Yi Pan;Jie Wu
中科院分区：
文献类型：
--
作者：
D. Xiang;Yueli Zhang;Yi Pan;Jie Wu
针对只有两个虚拟通道的n维网格，提出了一种新的无死锁自适应路由算法，其中一个虚拟通道可以被两个连续平面共享，而不存在任何循环通道依赖。信息沿着一系列平面传送。提出的平面自适应路由算法利用最后一个维度的空闲虚拟通道，将其增强为三维网格的完全自适应路由版本。针对三维网格，提出了另一种避免死锁的技术，该技术采用一种新的虚拟网络分区方案，该方案只有两个虚拟通道。基于虚拟网络分区方案，两个虚拟网络可以共享一些共同的虚拟通道。然后将无死锁自适应路由方案改进为基于平面构造的MCC故障模型的无死锁自适应容错路由方案。仿真结果充分证明了该算法的有效性。
A new deadlock-free adaptive routing algorithm is proposed for n-dimensional meshes with only two virtual channels, where a virtual channel can be shared by two consecutive planes without any cyclic channel dependency. A message is routed along a series of planes. The proposed planar adaptive routing algorithm is enhanced to a fully adaptive routing version for 3-dimensional meshes using the idle virtual channels along the last dimension. Another deadlock avoidance technique is proposed for 3- dimensional meshes using a new virtual network partitioning scheme with only two virtual channels. Two virtual networks can share some common virtual channel based on the virtual network partitioning scheme. The deadlock-free adaptive routing scheme is then modified to a deadlock-free adaptive fault-tolerant routing scheme based on a planarly constructed MCC fault model. Sufficient simulation results are presented to demonstrate the effectiveness of the proposed algorithm.