A Deterministic-Path Routing Algorithm for Tolerating Many Faults on Very-Large-Scale Network-on-Chip

Citations Over TimeTop 18% of 2020 papers

Abstract

Very-large-scale network-on-chip (VLS-NoC) has become a promising fabric for supercomputers, but this fabric may encounter the many-fault problem. This article proposes a deterministic routing algorithm to tolerate the effects of many faults in VLS-NoCs. This approach generates routing tables offline using a breadth-first traversal algorithm and stores a routing table locally in each switch for online packet transmission. The approach applies the Tarjan algorithm to degrade the faulty NoC and maximizes the number of available nodes in the reconfigured NoC. In 2D NoCs, the approach updates routing tables of some nodes using the deprecated channel/node rules and avoids deadlocks in the NoC. In 3D NoCs, the approach uses a forbidden-turn selection algorithm and detour rules to prevent faceted rings and ensures the NoC is deadlock-free. Experimental results demonstrate that the proposed approach provides fault-free communications of 2D and 3D NoCs after injecting 40 faulty links. Meanwhile, it maximizes the number of available nodes in the reconfigured NoC. The approach also outperforms existing algorithms in terms of average latency, throughput, and energy consumption.

Related Papers

• → A Fault-Tolerant Routing Algorithm Using Tunnels in Fault Blocks for Network-on-Chip(2017)1 cited
• → Design of Router Supporting Multiply Routing Algorithm for NoC(2014)
• Analysis and Evaluation of Fault-tolerant Routing Algorithms for NoC(2011)
• A Selective Packet Discard Technique for Efficient Deadlock Recovery in Networks-on-Chip(2015)
• → Deadlock-Free Routing Algorithm of 2D-Torus Network-on-Chip Based on FPGA(2021)