Practical Deadlock-Free Fault-Tolerant Routing in Meshes Based on the Planar Network Fault Model
Practical Deadlock-Free Fault-Tolerant Routing in Meshes Based on the Planar Network Fault Model
复制标题
DOI：
10.1109/tc.2008.211
复制
发表时间：
2009-05
影响因子：
3.7
通讯作者：
D. Xiang;Yueli Zhang;Yi Pan
中科院分区：
文献类型：
--
作者：
D. Xiang;Yueli Zhang;Yi Pan
无死锁路由所需的虚拟通道数对于经济高效和高性能的系统设计非常重要。平面自适应路由方案是一种有效的死锁避免技术，在3D或更高维的网状网络中，每个物理信道仅使用三个虚拟信道，具有非常简单的死锁避免方案。然而，在基于平面自适应路由算法的网状网络中，沿沿着第一维的所有物理信道存在一个空闲虚拟信道，沿沿着最后一维的信道存在两个空闲虚拟信道。针对仅使用两个虚拟通道的三维网格模型，提出了一种新的死锁避免技术。无死锁的自适应路由方案，然后修改为一个无死锁的自适应容错路由方案的基础上的平面网络（PN）故障模型。提出的无死锁自适应路由方案也扩展到n维网格仍然使用两个虚拟通道。充分的仿真结果证明了所提出的算法的有效性。
The number of virtual channels required for deadlock-free routing is important for cost-effective and high-performance system design. The planar adaptive routing scheme is an effective deadlock avoidance technique using only three virtual channels for each physical channel in 3D or higher dimensional mesh networks with a very simple deadlock avoidance scheme. However, there exist one idle virtual channel for all physical channels along the first dimension and two idle virtual channels for channels along the last dimension in a mesh network based on the planar adaptive routing algorithm. A new deadlock avoidance technique is proposed for 3D meshes using only two virtual channels by making full use of the idle channels. The deadlock-free adaptive routing scheme is then modified to a deadlock-free adaptive fault-tolerant routing scheme based on a planar network (PN) fault model. The proposed deadlock-free adaptive routing scheme is also extended to n-dimensional meshes still using two virtual channels. Sufficient simulation results are presented to demonstrate the effectiveness of the proposed algorithm.