The Hamiltonian-Based Fault-Tolerant Routing Algorithm For NoC

With the increasing requirements for Integrated Circuits, Multi-Processor Systems-on-Chip(MPSoCs) have been used in the area of Integrated Circuits products with higher performance, higher speed and lower power consumption. Nowadays, the Processing Elements(PEs)in System on Chip(SoC) will become more and more, traditional BusInterconnection system cannot meet the requirement of the communication of different PEs because of its poor scalability and limited bandwidth. Network on Chip(NoC) is presented as a new paradigm of interconnection, which can separate the communication system from the computation system and improve the performance of SoC. During the processing, routers and data channels have a certain fault rate, which will degrade the reliability of SoC even paralyze the whole network, therefore, the strategy of fault tolerant is play an important role in research. Based on this background, this paper proposed a fault-tolerant routing algorithm combining Hamiltonian-path and Hamiltonian-based Odd-Even(HOE) turn model in 2D and 3D mesh topologies, the main works of this paper shown as follows:Based on the traditional Hamiltonian-path, this paper proposed a Hamiltonian-path based odd-even Fault-tolerant Algorithm(Hoe FA) without the usage of virtual channels and extra routing information, which guarantees the existence of alternative paths for every packet when fault link occurs. Because of the reduced prohibited turns in HOE turn model, Hoe FA can explore the unused minimal paths and achieve the partial adaptive to balance the traffic degree. The experiment results presented that there are 2% to 6% improvement in throughput and the amount of arrival packets of proposed method, and it also reduced the global average latency and max latency in some extent compared with traditional Hamiltonian-path based Fault-tolerant Algorithm(Ham FA).Based on the design in 2D mesh, this paper proposed a 3D fault tolerant routing algorithm considering the strategy of the routing involving vertical links, and adopting different routing method in different odd or even planes. The experimental result shows similar improvement in performance including throughput, latency and the number of arrival packets.The proposed algorithm combines the redundancy design of hardware. By modifying the boundary router of mesh topology and adding redundancy channels, packets can be provided an alternative channel when they meet some boundary locations, which can avoid the deadlock problem. This methodology can support all different faults and only create small overhead.