Research On The Reliability Of The K-ary N-cube Network

As an important means of scientific and technological innovation,high-performance computing is widely used in many fields,such as nuclear explosion simulation,aerospace,weather forecasting,energy survey,engineering calculation and so on,which embodies the comprehensive strength of a country.In the research of high-performance computing,improving the operating efficiency has always been the primary goal of its development,and the parallel computing is an effective means to improve the computing speed and processing power of computer systems.The interconnection network is a network in which the processors inside a parallel computer are connected in a certain way.Its topological structure largely determines the construction cost,scalability,bandwidth,and delay of the interconnection network,which directly affects or even determines the ability of parallel computing.The k-ary n-cube network is an interconnection network topology with excellent performance,which has the following properties:recursive constructibility,node-symmetry and edge-symmetry,Hamiltonian property,and high bandwidth and low latency.In addition,many common network structures such as the hypercube,the cycle,and the Torus are subclasses of the k-ary n-cube.In fact,a large number of distributed multiprocessor systems,such as iWARP,J-machine,Cray T3D,Cray T3E,and IBM super computer BlueGene/L,are built based on the k-ary n-cube.Therefore,this network has important theoretical research and practical application values.With the increase of the number of processors in an interconnection network,the failure of processors is inevitable.When the processor fails,the information passing through the failed processor will be unreliable,which may cause fatal consequences.Therefore,the research on the reliability of interconnection networks is an important topic,while the reliability of networks can be characterized by parameters such as connectivity,diagnosability,fault-tolerant path,disjoint path,and subgraph reliability.This thesis studies the reliability of the k-ary n-cube network through the above parameters.The main contents are as follows.1.The(r+1)-component connectivity of the k-ary n-cube network and the(r+1)component diagnosability of the network under the PMC model and MM*model are determined.The results show that the(r+1)-component connectivity of the network is nearly r-1 times higher than the traditional connectivity of the network,and the(r+1)-component diagnosabilities of the network under the PMC model and MM*model are r times higher than the traditional diagnosability of the network(when n is sufficiently large).2.A fault-tolerant path construction algorithm on the k-ary n-cube network is presented.When the number of faulty nodes of the network does not exceed 2n-1,the algorithm can always construct a fault-free path between any two distinct fault-free nodes in the network.The simulation results show that the running time of the algorithm is much lower than the time of constructing fault-free paths between nodes using the algorithm Dijkstra.3.An algorithm for constructing disjoint paths on the k-ary n-cube network is designed.The algorithm can construct 2n disjoint paths between any two distinct nodes in the network.Considering that the connectivity of the k-ary n-cube network is 2n,the number of disjoint paths constructed by the algorithm is the largest.The simulation results show that the algorithm has a great advantage in running time compared with the algorithm based on the algorithm Dijkstra to construct disjoint paths between any two nodes.4.The subgraph reliability of the k-ary n-cube network is studied.Based on the idea from whole to local,the upper bound,lower bound,and approximate value of the subgraph reliability of the network are obtained by using the inclusion exclusion principle,and some numerical simulation experiments are carried out.The results show that when the reliability of a single node is getting smaller and smaller(as time goes on),the three values show good consistency.To sum up,this thesis describes the reliability of the k-ary n-cube network from five aspects of component connectivity,component diagnosability,fault-tolerant path,disjoint path,and subgraph reliability,which provides a basis for the research and application of the k-ary n-cube network.