Research On Multi-path Efficient And Fault-tolerant Routing Algorithm Based On MESH

2D-Mesh networks are widely used in the manufacturing of integrated circuits due to their simple structure,easy construction,low dimensions and high performance in processing various algorithms.The load balancing of the routing algorithm affects the throughput and latency of the network.Low throughput and high latency can cause network transmission performance to degrade.Therefore,improving load balancing is critical to routing algorithms,including fault-tolerant routing algorithms.Some specific applications require the network to work properly even with a small number of faults.Therefore,it is important to study the fault-tolerant routing algorithm for efficient network throughput in 2D-Mesh networks.Fault-tolerant routing algorithms traditionally employ adaptive routing strategies.When the adaptive routing algorithm performs message transmission in the network,it can independently select the path for transmission according to whether the network is busy at present.Although it has good flexibility,it needs to judge the network status and make routing decisions.,which increases the network transmission delay as well as complicates the router structure.While the random Oblivious routing algorithm does not need to consider the state of the current network,and randomly transmits messages through multiple paths existing between the source node and the destination node.Therefore,the random Oblivious routing algorithm has high flexibility and can achieve good performance.This paper presents a new idea based on Oblivious fault-tolerant routing.This idea avoids the problem that the network traffic is concentrated on the fault boundary in the traditional fault-tolerant routing,which can make the network traffic more evenly distributed.At the same time,in order to avoid the situation that the Oblivious route is not connected,a method is proposed in the process of selecting the routing intermediate node,which based on matrix multiplication to judge connectivity.By performing matrix multiplication calculations in two-stage routine,it is possible to accurately exclude intermediate nodes that cause disconnection.Experiments show that by using this algorithm,the connectivity of networks with fewer faulty nodes reaches 100%.Based on the idea of new Oblivious fault-tolerant routing,this paper proposes three kinds of 2D-Mesh fault-tolerant routing algorithms,namely DXYFT algorithm,DYXFT algorithm and U3TFT algorithm,which realizes the function of randomly selecting multiple paths from source node to destination node.The deadlock-free of these three routing algorithms is proved.These algorithms improve the throughput rate,avoid excessive concentration of network traffic on the fault boundary,make the network distribution more balanced,and ensure system connectivity.Experiments show that compared with the traditional routing algorithm,the new algorithm has better results in the network throughput under the average case communication.For example,when the network scale is 6×6 and multiple faulty nodes,the worst case throughput of the DXYFT algorithm,the DYXFT algorithm,and the U3TFT algorithm is increased by 18%,18%,and 19%,respectively,compared to the adaptive bypass path.