PAIR: Periodically Alternate the Identity of Routers to Ensure Deadlock Freedom in NoC

Network-on-Chip (NoC) has become widely adopted in multi/many-core systems for on-chip communication. Avoiding deadlock is a critical issue in NoC design. Recently proposed techniques partition the network resources into one or more express paths. Each path allows a blocked packet to move forward to its destination, thereby breaking deadlocks. However, as the scaling up of NoC, the existing methods are experiencing a decline in efficiency due to the coarse-grained partitioning strategy. In this work, we present PAIR, a novel scheme that guarantees deadlock freedom. PAIR adopts a fine-grained resource partitioning approach, significantly increasing the number of express paths available. The express paths in PAIR not only allow blocked packets but also permit non-blocked packets to be forwarded to the next hop, minimizing the performance degradation for the normal flow control. We implemented and evaluated PAIR on the mesh network using classic synthetic traffic patterns. Our experiments show that PAIR significantly improves throughput performance, achieving an average increase of 80.36% compared with state-of-the-art deadlock-free solutions. Furthermore, PAIR outperforms the latest deadlock-free scheme by 37.78% in terms of throughput.