A Region-based Fault Tolerant Routing Algorithm for 2D Irregular Mesh Network-on-Chip
A Region-based Fault Tolerant Routing Algorithm for 2D Irregular Mesh Network-on-Chip
复制标题
一种基于区域的二维不规则网状片上网络容错路由算法
DOI：
10.1007/s10836-013-5377-9
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
and Ikuko Eguchi Yairi
中科院分区：
文献类型：
--
作者：
Yusuke Fukushima;Masaru Fukushi;and Ikuko Eguchi Yairi
提出了一种基于区域划分的不规则网状片上网络无死锁容错路由算法。在这种方法中，一组矩形的故障区域称为故障块形成的故障节点和迂回路径定义为每个故障块，以指示数据包必须绕道thefaulty块。关于该方法的最新路由算法是消息路由（Message-Route）（Holsmark和Kumar J Inf Sci Eng 23：1649-1662，2007），其对可容忍故障节点的数量及其分布没有限制。然而，该算法有三个关键问题：（1）该算法未能提供完整和无死锁的路由，（2）许多非故障节点包含在故障块中，从而停用，（3）复杂的路由功能是不可行的硬件实现。在本文中，我们给出了上述三个问题的解决方案。我们纠正了消息路由的错误，使其完整和无死锁。然后，我们提出了一个无死锁的容错路由算法，它可以工作在小尺寸的故障块与一个简单的路由控制。实验结果表明，该算法显著减少了故障块的大小，并改善了随机和集群故障的通信延迟。此外，该算法的FPGA实现也进行了讨论。
This paper presents a deadlock-free fault-tolerant routing algorithm for irregular mesh network-on-chips based on a region-based approach. In this approach, a set of rectangular faulty regions called faulty blocks is formed for faulty nodes and a detour path is defined for each faulty block to indicate how packets must detour thefaulty block. The most recent routing algorithm on this approach is Message-Route (Holsmark and Kumar J Inf Sci Eng 23:1649–1662, 2007) which does not have restrictions on the number of tolerable faulty nodes and its distribution. However, this algorithm has three crucial problems; (1) this algorithm fails to provide complete and deadlock-free routing, (2) many nonfaulty nodes are contained in faulty blocks and thus deactivated, and (3) complex routing functions are not feasible for hardware implementation. In this paper, we give a solution for each of the above three problems. We correct the errors of Message-Route to make it complete and deadlock-free. Then, we propose a deadlock-free fault-tolerant routing algorithm which can work under small-sized faulty blocks with a simple routing control. Experimental results show that the proposed algorithm significantly reduces the size of faulty blocks and improves communication latency for both random and cluster faults. Moreover, an FPGA implementation of the proposed algorithm is also discussed.