Research On NoC Fault-tolerant Routing Algorithms Based On Fault Models Of Different Granularities

Fault-tolerance is one of the key technologies for providing reliable data communication ofNetwork on Chip (NoC). It is a major factor which affects the network throughput and latency.Fault-tolerant routing algorithm is the primary method to tolerate permanent faults infault-tolerant technologies of NoC. Fault models are essential for the research on fault-tolerantrouting algorithms, and according to the decreasing order of granularities, fault models adoptedby current routing algorithms include fault block model, single component fault model andfine-grained fault model. However, there are still three main problems in the research of NoCfault-tolerant routing algorithms based on fault models of different granularities. Firstly,algorithms based on single component fault models adopt the way of "hop-by-hop comparison"to transmit packets, which results in great network latency. Secondly, the existing fine-grainedfault models deal with link faults roughly, which leads to low utilization ratio of effectiveresources in nodes. Thirdly, routing algorithms based on fine-grained fault model adopt thetraditional way of "bypassing faults" to deal with channel faults in nodes, which results in longrouting paths and low network performances.To solve those three problems above, this dissertation researches adaptive fault-tolerantrouting technologies based on single component fault models and fine-grained fault models in2D Mesh NoC, by combining the differences between traditional Ethernet and NoC. Main workand contributions of this dissertation are outlined as follows:1. A low latency adaptive NoC fault-tolerant routing algorithm based on single componentfault model is proposed. Combined with the features of2D Mesh NoC, the algorithm adopts thetransmitting method of "hop-spanning comparison" to replace "hop-by-hop comparison".Meanwhile, the algorithm uses a fuzzy priority policy which can be implemented by simple logiccircuits to ensure adaptability. Experimental results demonstrate that the proposed algorithm is alow latency algorithm suitable for large-scale NoC, ISE synthesis results show that the algorithmrequires low hardware overheads.2. A very fine-grained fault model which is improved from traditional fine-grained faultmodels is established. To solve the resource wasting problem caused by roughly equivalent wayin current fine-grained fault models, the very fine-grained fault model adds link faults into therecording faults, so as to distinguish link faults from channel faults effectively. And the proposedmodel adds buffer faults into the describable faults, which makes it possible to reuse discardedbuffer resources in NoC. This dissertation compares the proposed model with two commonfine-grained fault models using available resource utilization rate as the performance indicator,and analyzes system-level hardware overheads of three fault models. The results show that thevery fine-grained fault model is a cost-effective fault model.3. A fault-tolerant routing algorithm of NoC based on buffer reuse is proposed by using veryfine-grained fault model. The algorithm adopts "channel-replacing fault tolerance" instead of"channel-bypassing fault tolerance" to tolerate channel faults. The way of "channel-replacingfault tolerance" can use normal channels that are discarded because of link faults in place of faulty channels, that can improve the available resource utilization rate and the probability ofpackets outputting through optimal port, increase the number of normal routing paths in thewhole NoC as well. Both the experiment and ISE synthesis results demonstrate that thealgorithm has high performance-price ratio and high stability, meanwhile it is suitable for NoC ofhigh failure rate as well.