Research On Fault-tolerant Routing Algorithm In Network On Chip

As the number of integrated IP (Intellectual Property) cores in the current SOC (System-On-Chip) keeps increasing, communication requirements among cores can not be sufficiently satisfied, using either traditional or multi-layer bus architectures, because of their poor scalability and bandwidth limitation on a single bus. While new techniques have been explored to overcome such a limitation, the notion of NOC (Network-On-Chip) has been proposed. NOC realizes the deviation of communication and computation, can improve SOC performance effectively. NOC gradually becomes a new communication structure besides traditional on-chip bus.NOC has a good performance in reliability, but once faults appear, the performance will be down. Even the faults will induce NOC collapse. So the design of NOC fault-tolerant routing is of great important to NOC design. Although some achievements have been proposed now, a lot of them are the transition of the technology of interconnection network. There is little design for NOC only. To solve these problems, using specify topology, this paper mainly do research on NOC fault-tolerant routing. Next is the introduction of my work.Firstly, by the introduction of NOC fault-tolerant, using mesh topology and dimension-ordered routing algorithm, a new fault-tolerant routing in mesh based on priority (PR algorithm) is proposed. Comparing with traditional routing algorithms, PR algorithm can make packets bypass the fault links or nodes to realize fault-tolerant, according the priority of routing direction decided by the relationship between the source node and the destination node dynamically. PR algorithm has the characteristics of high throughput, low delay, good self-adaptability and deadlock-free.Secondly, by using redundant devices in fault-tolerant mechanism for reference, a novel NOC fault-tolerant mechanism based on default fault-tolerant paths (DFPs) is proposed. By DFPs, using minimum spanning tree to generate minimum spanning tree, the source node routes to the destination node, complying with the path generated by traversing minimum spanning tree. Due to no need of extra hardware, this mechanism reduces the cost of area. Simulation results demonstrate the algorithm that based on this mechanism appears good performance.