Abstract: A fault-tolerant and deadlock-free routing algorithm applied in 2D-mesh was proposed to solve the problem of the permanent and unpredictable failure occurrence in network on chip. Firstly a new definition of fault block is proposed to reduce the region of fault and the affected healthy node, and then a detour-path construction algorithm is designed to implement the construction of fault block and the generation of detour-path list by recursive of message deliver. The detour-path routing algorithm combines the detour-path list and routing rules, makes a detour to avoid the fault block by adding detour-path list into the header flit. The experimental results show that the proposed algorithm achieves a reduction of average delay under uniform random distribution and hotspot distribution.  

Key words: network on chip (NoC), routing algorithm, faulttolerant, deadlock avoidance