Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s10836-013-5377-9 | J. Electronic Testing |
Keywords | Field | DocType |
Network-on-chip,2D irregular mesh networks,Fault-tolerant routing,Deadlock-free routing,Region-based approach | Multipath routing,Link-state routing protocol,Equal-cost multi-path routing,Dynamic Source Routing,Computer science,Static routing,Parallel computing,Destination-Sequenced Distance Vector routing,Routing table,Distance-vector routing protocol | Journal |
Volume | Issue | ISSN |
29 | 3 | 0923-8174 |
Citations | PageRank | References |
4 | 0.46 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yusuke Fukushima | 1 | 92 | 12.80 |
| Masaru Fukushi | 2 | 121 | 16.50 |
| Ikuko Eguchi Yairi | 3 | 67 | 14.16 |