An Adaptive Fault Tolerant Routing Algorithm Research For 3D NoC

With the development of system-on-chip and single chip integrates much more transistors,the increment of integration and the decrease of the feature size exacerbates the communication difficulty of the system-on-chip.The on-chip communication structure based on network-on-chip can solve the communication problem caused by bus structure effectively.Along with the increase of the network-on-chip scale,the area and interconnection line of two-dimensional on-chip structure are also in escalation which has a great influence on network performance.Three-dimensional network-on-chip structure has shorter network distance and effectively improves the network performance which has been paid much attention.However,there may be a series fault in link and vertical link which results in the packet being not transferred to the destination node.Thus,the design of an efficient fault-tolerant routing algorithm based on the Three-dimensional network-on-chip has become a popular study point.This thesis not only sets up and verifies three-dimensional network-on-chip simulation platform,but also put forward a new fault-tolerant routing algorithm based on the three-dimensional network-on-chip which efficient improves the network performance under the high fault rate situation.This thesis analyzes key technologies of three-dimensional network-on-chip,including routing structure,topology,routing algorithm and especially fault-tolerant routing algorithm in detail.As for most simulation platforms not supporting three-dimensional network-on-chip structure with fault link,this thesis sets up three-dimensional network-on-chip simulation platform based on NIRGAM,improves the NIRGAM software,builds three-dimensional network-on-chip simulation platform and designs fault link in three-dimensional topology.In order to test and verify the three-dimensional network-on-chip simulation platform with fault link.,this thesis introduces a reliable routing algorithm based on three-dimensional network-on-chip with low consumption high-performance,a deflection routing fault-tolerant method based on dynamic priority and a minimum self-adaption fault-tolerant algorithm into router architecture.On the basis of analyzing the existing three-dimensional network-on-chip fault-tolerant routing algorithm,this thesis propose a wide-range fault rate self-adaption reliable fault-tolerant routing algorithm based on three-dimensional Mesh topological structure.The main idea is to find the biggest non-fault cube and reach to the node which is closest to the destination node in this cube through the random independent routing algorithm.Then,it runs the fault-tolerant routing algorithm to bypass the fault link and repeats the process until reach the destination node.This thesis verifies the fault tolerance reliability of the proposed algorithm on the improved simulation platform,tests the algorithm performance under different network scale and different packet injection rate,and compares with the three completed fault tolerant routing algorithm.The simulation results shows that the proposed LAHF algorithm's average delay is less than the AFRA algorithm,DPDR algorithm and MAFA algorithm by respectively 14%,32% and 25% when the packet injection rate equal to 0.3 while the LAHF algorithm's average throughput is more than AFRA algorithm,DPDR algorithm and MAFA algorithm by respectively 1.3 times more,2.4 times more and 1.8 times more.This thesis improves and verifies the network-on-chip simulation platform NIRGAM,and proposes a new LAHF algorithm which is applicable to wide range and high fault rate.The simulation results show the proposed algorithm performance is better than existing algorithms and has a lower latency and higher throughput.In summary,this thesis provides a certain reference for research of the three-dimensional network-on-chip fault-tolerant routing algorithm.