The Fault-tolerant Adaptive Routing, Load Balancing And Deadlock-free Routing Algorithm Based On Cracky Fault Block Of The Two-dimensional Mesh

Parallel processing is an important area of research, and improve the communication efficiency is an important research topic。Network routing is the process that send message from the source node through some intermediate relay nodes to the destination。The quality of the routing rules determines the direct parallel computer performance, and the fault-tolerant routing rules is a measure of performance for routing criteria。This paper, based on two-dimensional plane mesh of parallel computer, is to proposed a fault-tolerant, self-routing method.This paper proposed and implemented the new algorithm,"Adaptive fault tolerant routing table block algorithm" is based on the "Graph Theory in the communication network and wireless network applications in sensor networks," mentioned in the new fault tolerant model. It is the fault of the network in the form containing a number of small disjoint blocks, making block boundaries and block in the external links are trouble-free, and all the failed link or node located within the block, said This block is fault block, fault block within the node connected fault-free link suspension by the fault block in the border point to the root of the tree, by the way the trees and fault block boundaries constitute the graph is called the rift fault blocks, also known as a gap in the cracks rectangular block. The original paper, based on this model, an algorithm, called "The novel routing algorithm based on cracky rectangular blocks", the algorithm continuously between adjacent nodes send messages, update their status until the status of each point is stable so far achieved the two-dimensional grid fault block structure. Those who met the original algorithm, fault block boundary nodes have child nodes, regardless of whether the target node in the fault block, the routing algorithm will enter fault block route, with a certain blindness, and adaptive fault block fault-tolerant routing table algorithm to completely rule out the possibility of such blindness.This paper compares the two algorithms through experiments under the route length. Experiments in accordance with the grid size and fault block design accounting for these two conditions, in which the grid size was25×25,50×50,100×100,200×200, fault block proportion of0%to90%. Experiments using randomly generated node error method, randomly generated1000pairs of different points of dispatch and receiving points, the two algorithms calculate the average routing path length.The results show that adaptive fault tolerant routing table algorithm block size in the same grid, the same fault than the case, routing length are much smaller than the fault-tolerant adaptive algorithm:When the grid size of25×25, the average routing length ratio fault-tolerant adaptive algorithm reduced45.35%, when the grid size is50x50, the average route length shorter than the fault-tolerant adaptive algorithm is44.39%, mesh size of100×100, the average route length shorter than the fault-tolerant adaptive algorithm of45.14%, mesh size of200x200, the average route length shorter than the fault-tolerant adaptive algorithm44.04%.The important contribution of this paper is the routing path length in the original algorithm based on the fault block in the proportion of60%reduced at least70%, and found that, regardless of which grid size, when the fault blocks accounting for less than50%cracks on a seamless rectangular block fault model with high fault tolerance capabilities, fault block in this proportion range, the average route length of slow growth.