A Deflection-Based Deadlock Recovery Framework to Achieve High Throughput for Faulty NoCs

Deadlock is a critical issue in faulty Networks-on-Chips (NoCs). Existing deadlock-free approaches on faulty NoCs suffer from low throughput and poor fairness when the network becomes oversaturated. This problem hinders their practical use as oversaturation scenarios are more frequent on faulty NoCs. To address this issue, a deflection-based deadlock recovery framework is proposed for higher oversaturation performance on faulty NoCs. First, we observe the low oversaturation performance of existing deadlock recovery approaches, and analyze the positive feedback loop that can amplify the negative impact of deadlocks and congestions, which necessitate handling both deadlocks and congestions in a deadlock recovery framework. Second, we propose a novel deadlock recovery framework, which includes an accurate, timely deadlock detection and a highly efficient deadlock recovery. Both the deadlock detection and recovery reduce the average packet traversal latency, thereby improving the average oversaturation throughput. Third, we propose a distributed implementation to make the entire network enter and exit the deflection mode, which is conducted by broadcasting special messages via a bufferless subnetwork. An average oversaturation throughput improvement of $1.1\sim 8.1\times $ over state-of-the-art approaches is achieved. In terms of fairness, the minimal oversaturation throughput is improved from near zero to half of the peak throughput.