Graceful deadlock-free fault-tolerant routing algorithm for 3D Network-on-Chip architectures

• High-throughput deadlock-free fault tolerant routing algorithm for 3D-Network-on-Chip systems.
• Combination of look-ahead routing and local-routing for performance enhancement.
• Low cost deadlock-recovery technique.
• Hardware complexity and performance evaluations.
• Graceful performance degradation and deadlock-freedom obtained at high fault-rates.

Three-Dimensional Networks-on-Chip (3D-NoC) has been presented as an auspicious solution merging the high parallelism of Network-on-Chip (NoC) interconnect paradigm with the high-performance and lower interconnect-power of 3-dimensional integration circuits. However, 3D-NoC systems are exposed to a variety of manufacturing and design factors making them vulnerable to different faults that cause corrupted message transfer or even catastrophic system failures. Therefore, a 3D-NoC system should be fault-tolerant to transient malfunctions or permanent physical damages.In this paper, we present an efficient fault-tolerant routing algorithm, called Hybrid-Look-Ahead-Fault-Tolerant (HLAFT), which takes advantage of both local and look-ahead routing to boost the performance of 3D-NoC systems while ensuring fault-tolerance. A deadlock-recovery technique associated with HLAFT, named Random-Access-Buffer (RAB), is also presented. RAB takes advantage of look-ahead routing to detect and remove deadlock with no considerably additional hardware complexity. We implemented the proposed algorithm and deadlock-recovery technique on a real 3D-NoC architecture (3D-OASIS-NoC1) and prototyped it on FPGA. Evaluation results show that the proposed algorithm performs better than XYZ, even when considering high fault-rates (i.e., ≥≥ 20%), and outperforms our previously designed Look-Ahead-Fault-Tolerant routing (LAFT) demonstrated in latency/flit reduction that can reach 12.5% and a throughput enhancement reaching 11.8% in addition to 7.2% dynamic-power saving thanks to the Power-management module integrated with HLAFT.