A fault-tolerant routing algorithm aiming at a path fault and local congestion in NoC

作者：Ouyang, Yi Ming; He, Xin Cheng; Liang, Hua Guo; Yi, Mao Xiang; Du, Gao Ming; An, Xin

来源：Acta Electronica Sinica, 2016, 44(4): 920-925.

DOI：10.3969/j.issn.0372-2112.2015.04.024

• Algorithm design
• Bottleneck problem
• Congestion modeling
• Fault model
• Fault-tolerant routing algorithm
• Network traffic
• On-chip interconnection
• Throughput rate

As a new type of on-chip interconnection architecture, Network-on-chip overcomes 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 routing 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 algorithm is not only fault-tolerant but also makes sure the network a good performance. What's more, the algorithm chooses the optimal path under the condition of fault-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.

• 出版日期2016
• 单位合肥工业大学