Extending Fault Blocks to Avoid Livelock for a Logic-Based Distributed Fault-Tolerant Routing Algorithm of Networks-on-Chip

For logic-based distributed fault-tolerant routings, livelock is a troublesome challenge. In this paper, we prove the sufficient conditions which make the fault-tolerant routing PR-WF [1] to be livelock-free. Due to the diversity of fault blocks, it is almost impossible to verify the sufficient condition of livelock-free by a formal method. In this paper, both visual analysis and enumerative simulation methods are taken to prove livelock theorems. In order to avoid livelock, an algorithm is presented to extend fault blocks. Experimental results show that, it has to disable no more than 1.8% no-faulty links to avoid livelock if the true faulty link rate is 10%.