Congestion-Aware Adaptive Routing with Quantitative Congestion Information
Sheng Xu, Binzhang Fu, Mingyu Chen, Lixin Zhang · 2016
Congestion-aware adaptive routing can effectively improve the performance of Networks-on-Chip (NoC) due to its ability to accurately predict network congestion and make optimal routing decisions. Based on the fact that transporting quantitative congestion information is cost-prohibitive through current Congestion Propagation Networks (CPN), state-of-the-art adaptive routing algorithms tend to exploit qualitative congestion information. Unfortunately, qualitative congestion information can not provide a precise view of the network congestion level and hence mispredict network congestion in some cases, which easily leads to suboptimal routing decisions. To address this problem, this paper proposes the Quantitative Congestion Awareness (QCA) technique, which collects non-local quantitative congestion information by transferring the difference instead of the absolute value of the desired congestion metrics, such as the number of free virtual channels. With QCA technique, the cost of CPN is minimized and fixed since only one wire per destination is required regardless of the size of network and number of virtual channels per physical channel. A novel adaptive routing algorithm combining both congestion avoidance scheme and comprehensive evaluation scheme is proposed to fully exploit the properties of quantitative congestion information and make optimal routing decisions. With extensive simulations, the results show that the throughput could be improved up to 17.13% compared with state-of-the-art routing algorithms.