Complement routing: A methodology to design reliable routing algorithm for Network on Chips

摘要

Use of deep sub-micron VLSI technologies in fabrication of Network on Chips (NoCs) makes the reliability to be one of the first order concerns in the design of these products. This paper proposes and evaluates a methodology that adds reliability to NoC routing algorithms with minimal power and performance overheads. The key idea behind this methodology is to use the concept of complement routing in which two routing algorithms with disjoint sets of allowed turns are incorporated. According to this methodology, while a packet is routed by a routing algorithm, a redundant copy of that packet is routed by the complement of that routing algorithm. This is done by exploiting channels with lower utilization to route redundant packets. To find the complement of the used NoC routing algorithm, an analytical approach based on the channel dependency graph is presented. The methodology is applied to two NoCs using the dimension order and the Duato's routing algorithms. These networks are simulated using an HDL-based NoC simulator along with the Synopsys Power Compiler tool. Results extracted by different traffic generation rates and by different error injection rates confirm that the proposed methodology provides similar reliability improvement in comparison with the flood-based routing algorithms. This methodology also decreases the performance and power consumption overheads as compared to the flood-based routing algorithms.