Research On Fault-tolerant Routing Algorithms In NoC Oriented To Different Fault Granularities

With the continuous decrease of feature size, more and more IP cores can be integrated on asingle chip. Traditional bus interconnect structure has been unable to meet the communicationrequirements between so many IP cores. Thus Network-on-Chip(NoC) is proposed as a newinterconnect structure. However, the ever decreasing chip feature size and increasing integrationdensity, results in an increasing failure rate in NoC. Fault-tolerance becomes a key issue urgentlyneeds to be addressed. Because of the relatively short study period, there are still some problemsin the NoC fault-tolerant routing, which can be outlined as:1) In the fault-tolerant routing basedon fault block model, the packets select a non-minimum path to avoid around the fault block inthe case of the minimum path exists.2) In the fault-tolerant routing based on fixed-priority ideas,there is a lack of effective solutions to solve the problem of pinball routing.3) Due to theunawareness of fault information in next hop nodes, packets are routed in a non-optimal routingpath. This dissertation specially focuses the research on fault-tolerant routing algorithm in NoCto solve the above problems.Based on the study of existing fault-tolerant routing algorithms, the dissertation establisheda novel building model for region of minimum path, and proposed two fault-tolerant routingalgorithms.The main achievements of this dissertation are as follows:1A building model of region of minimum path(RMP) is proposed, which is in distributedstorage. The RMP avoids a variety of complex avoidance-around rules in fault-tolerant routingbased on fault block model, but the traditional building method needs continuous communicationcooperation between the source node and destination node. The proposed building model dividesthe2D-Mesh NoC with fault blocks into a number of different size rectangular regions. Thesource node only needs to find two boundary regions of RMP, and the corresponding RMPbetween two nodes is constructed by a combination of different rectangular regions, in which thepackets are routed in a minimum routing with full adaptiveness. The building model has a certainvalue in other aspects such as routing in irregular NoC.2A NoC fault-tolerant routing algorithm IPFR based on improved-priority is proposed. Inthe traditional fixed-priority fault-tolerant routing based on single fault model, packets are proneto pinball routing, which is a kind of livelock routing. In this dissertation, port priorities areassigned with the input port to be considered. And a dynamic update strategy of priority isfurther proposed as well. Based on the two priority strategies proposed above, fault-tolerantrouting IPFR is proposed. Simulation results show that the algorithm could avoid pinball routing,as well as reduce the invalid load and packets loss rate in network.3A NoC fault-tolerant routing algorithm FNA-FR is proposed, which is fault-on-neighboraware. In the fault-tolerant routing based on the original functional fault model, the paths packetsrouted are non-optimal. In this dissertation, the original functional fault model is expanded to notonly store its own fault information, but also part of the channel fault information in the adjacentnodes; And odd-even turn model is embedded into the functional fault model to avoid deadlock. In the end, based on the extended functional fault model and embedded odd-even turn model, apath-optimal fault-tolerant routing algorithm FNA-FR is proposed. Simulation results show thatthe routing paths of this algorithm are closer to the minimum routing path, and could ensure highreliability of communication.