一种无虚通道NoC负载均衡容错路由算法

A load-balancing fault-tolerant NoC routing algorithm based on turn rules without virtual channel

摘要:

随着芯片复杂度的不断增大,设计一个高效的片上网络容错路由算法面临着巨大的挑战。由于芯片面积开销的限制,拥有低面积开销的无虚通道片上网络路由器受到学术界的广泛关注。但目前对无虚通道片上网络容错路由算法的研究却停留在容错性能上,而忽略了容错路由算法的路由路径过于单一所造成的负载不均、数据包平均延迟较大等问题。文章在借鉴已有的奇偶转向容错路由算法的基础上,对算法的故障模型和故障绕行策略进行优化,并在算法中融入负载均衡策略,以形成新的容错算法缓解上述问题。在9x9的2D mesh网络中对新提出的算法和参考算法的仿真结果表明：与参考算法相比,新算法在降低数据延迟和吞吐量方面有着明显的优势,在最优情况下能减少8.92%数据延迟和增加10.46%的吞吐量。

Abstract:

As structure of chip is becoming more complex, An efficient routing algorithm designed for Network on Chip has became increasingly challenging. Currently, the research of fault-tolerant routing algorithm without virtual channels mainly focus on routing around fault, but neglects issues of load-balancing and latency caused by communication hotspot and single path between source and destination. To address the problems, a fault-tolerant routing algorithm based on Odd-Even turn rules with load-balancing strategy is proposed based on existing OE fault-tolerant strategy. The novel algorithm extend Odd-Even fault model and Odd-Even fault-tolerant strategy to enhance capacity of fault-tolerant and also fuse a load-balance strategy to relieve the issues. The simulation results demonstrate that the proposed algorithm outperforms in average package latency and throughout compared to reference algorithms in the 9x9 2D mesh NoC. In the best case, it reduces 8.92% average delay and increase 10.46% throughout.