Research On The Fault-Tolerant Performance Of Generalized Hypercube Network

High performance computing is widely used in various fields such as national defense and security,high-tech development and national economic construction.Therefore,high performance computing is an important benchmark for measuring the development level of national comprehensive strength.The computing efficiency of high performance computing is the top priority for its development,and parallel computing technology plays an important role in solving the bottleneck of multi-processing unit speed.The connection between processors in a parallel computing system is defined as an interconnection network,and the connection can be described by a topology.The topology determines the communication performance such as bandwidth,latency,communication,and routing of the interconnected network.Generalized hypercube is a common topology.The r-dimensional generalized hypercube is denoted as G(mr,mr-1,…,m1)where mi denotes the base of the i-th dimension.When mi=2,the generalized hypercube can be regarded as a hypercube;when mi=k,the generalized hypercube can be regarded as a k-ary n-cube,so the generalized hypercube is a more general topology.The generalized hypercube has very excellent properties.It has symmetry and regularity;its connection method and recursive structure make it easy to construct;it can be represented in arbitrary binary,so the degree and connectivity of the generalized hypercube are larger than those of hypercubes of the same dimension,and thus has better fault tolerance.The generalized hypercube also has a wide range of practical applications,and has been used to design some data center networks such as BCube and HyperX.As the number of processors in a network increases,the probability of processor failure also increases.Fault tolerance refers to the ability of a network to communicate properly even when a vertex or edge in the network fails.Connectivity is one of the important metrics to measure the fault tolerance of a network.Under classical connectivity,all neighbors of a vertex can fail at the same time,but the probability of such an event occurring is very low.The(r+1)-component connectivity is a more realistic measure of the fault tolerance of the network,which requires that at least r+1 components remain in the graph after removing the failed vertices.The(r+1)-component connectivity is considered from the point of view of the faulty vertices,but faulty vertices in the network tend to interact with each other and thus generate a faulty structure.Considering the probability that there is a faulty structure in the network and all neighbors of a vertex are faulty vertices is very low,super H-connectivity and super H*-connectivity can make the graph G free of isolated vertices in the remaining components after removing the faulty structure.The fault-tolerant routing algorithm based on connectivity is a common fault-tolerance mechanism.When the number of faulty vertices in the network is smaller than the connectivity,the fault-tolerant routing algorithm can obtain at least one fault-free path between any two fault-free vertices,thus guaranteeing the normal communication function of the network.In this thesis,the 3-component connectivity of generalized hypercubes and fault-tolerant routing algorithms based on 3-component connectivity,super H-connectivity and super H*connectivity and the corresponding fault-tolerant routing algorithms are studied.The details of the study are as follows:(1)3-component connectivity of the generalized hypercube and its fault-tolerant routing algorithm:based on the definition of(r+1)-component connectivity,the 3-component connectivity of the generalized hypercube is obtained,and gives the relevant proofs and faulttolerant performance analysis.Also,a fault-tolerant routing algorithm GHCCP for generalized hypercubes based on 3-component connectivity is given,and the time complexity of the algorithm is O(κ(G)3).The algorithm can obtain at least one fault-free path between any two fault-free vertices when the number of faulty vertices is less than the 3-component connectivity.A visual demonstration of the algorithm is then performed.Finally,simulation experiments are conducted to compare it with the depth-first search algorithm DFS andS the breadth-first search algorithm BFS,mainly to compare the time spent and the path length to obtain a fault-free path,and to verify the effectiveness of the algorithm GHCCP.(2)Super H-connectivity and super H*-connectivity of generalized hypercube:based on the definitions of super H-connectivity and super H*-connectivity,the super H-connectivity and super H*-connectivity of generalized hypercube are studied,where H ∈ {K1,M,C3,C4,K4}.Then a fault-tolerance performance analysis was performed.The results show that super H-connectivity and super H*-connectivity can accommodate almost twice as many fault nodes as classical connectivity with better fault tolerance performance under ideal conditions.(3)Fault-tolerant routing algorithm based on super H-connectivity and super H*-connectivity:based on the definitions of super H-connectivity and super H*-connectivity,the generalized hypercube fault-tolerant routing algorithm GHFRouting based on super H-connectivity and super H*-connectivity is proposed,and the time complexity of this algorithm is O(κ(G)3).The algorithm can obtain at least one fault-free path between any two fault-free vertices when the number of fault structures is smaller than the super H-connectivity and super H*-connectivity.In addition,simulation experiments are conducted to compare it with the depth-first search algorithm DFS and the breadth-first search algorithm BFS to analyze the time spent and the path length of the three algorithms to obtain a fault-free path,and the execution efficiency of the algorithm GHFRouting is obtained to be better than that of DFS and BFS.