针对路径故障与局部拥塞的NoC容错路由算法

A Fault-Tolerant Routing Algorithm Aiming at a Path Fault and Local Congestion in NoC

片上网络作为一种新型片上互连架构,克服了片上系统在发展中遭遇的瓶颈问题.然而,片上网络中的路由器故障以及路由器之间的链路故障都会造成网络性能损失.对此,文章提出一种针对路径故障与局部拥塞的NoC容错路由算法.首先,设计了一种相隔节点间路径故障模型,该模型下的路由器以较小的开销为代价,动态感知两跳以内的路径故障状态.其次,提出了一种新颖的更能准确反映局部网络拥塞状态的拥塞模型来均衡网络流量.最后,当网络无故障时,算法保证走最优路径;有故障时,算法不仅可以实现容错还能保证网络具有良好的性能.实验表明,在无故障的情况下,本文方案相较于对比对象延迟降低了10%-20%,吞吐率提高了25%左右.在有故障的情况下,本文方案较对比对象的优势更加明显.

As a new type of on-chip interconnection architecture, network-on-chip overcomes the bottleneck problem of the system-on-chip during the development. However, a failure arising in a router or a link between routers in network-on- chip will cause the reduction of network performance. To avoid this phenomenon, this paper puts forward a fault-tolerant rou- ting algorithm aiming at a path fault and local congestion in network-on-chip. Firstly, the algorithm designs a fault model that reflects the fault status of the path within two hops. As a result, this novel fault model makes the router achieve a dynamic perception of path state within two hops with less cost. Secondly, a novel congestion model has been proposed for reflecting the state of the local network more accurately, contributing to balance network traffic. Finally, when a fault occurs, the algo- rithm not only is fault-tolerant but also makes sure the network has a good performance. What＇ s more, the algorithm chooses the optimal path under the condition of fanlt-free. Experimental results show that the proposed algorithm has 10% - 20% lower latency in average and 25% higher throughput rate than the contrast case when the network is fault-free. In the case of defective in the network, the advantage of the present scheme has a bigger superiority.