Research On Fault-tolerance Associated With Distance On Hypercubes

With the development of computer science and information network technologies, high performance computers are playing an increasingly important role in all areas of society.Performance of a high performance computer depends largely on the connection mode of internal processors of the system(interconnection network). The research on the topology and the properties of interconnection network is one of the important researches in the field of parallel computing. An interconnection network can generally be represented by a simple graph G =(V(G), E(G)), where V(G) is the vertex set, representing the processors in interconnection network, and E(G) is the edge set, representing the links between the processors.With the continuous expansion of the scale of the interconnection network, the number of processors and links in the network is gradually increasing, and the probability of failure will also increase. Whether the properties of the network can be maintained in case of failure? This can be characterized by the fault tolerance of the network, which is a key metric to measure the performance of the interconnection network.Hypercube network is a common interconnection network in multiprocessor systems.It has many excellent properties, for example, small diameter, symmetrical structure, recursive construction, strong scalability, etc.. Based on hypercubes, some hypercube variants with superior properties have already been presented, such as crossed cubes, twisted cubes,M ¨obius cubes, etc.. Therefore, the hypercube has become one of the most basic and most important network models in multiprocessor systems.In this thesis, based on theoretical analysis, a new measurement method is proposed for the fault tolerance of hypercubes. Besides that, under the limitation of the method, we study the conditional connectivity, the fault-tolerant routing algorithm as well as the fault-tolerant hamiltonian properties of hypercubes. The major contributions are listed as follows.1. This thesis presents a new conditional connectivity associated with distance:(g, d, k)-conditional(edge) connectivity. Compared with other conditional connectivity,(g, d, k)-conditional(edge) connectivity is more realistic. And it allows more faulty nodes(edges).It provides a new measure to study the fault tolerance of hypercubes and other networks.2. This thesis studies some(g, d, k)-conditional(edge) connectivities of hypercubes,including ?1,1,k(Qn), ?1,d,2(Qn), ?1,1,1(Qn) and ?1,d,2(Qn). These results provide a reference for the further research on other(g, d, k)-conditional(edge) connectivities of hypercubes, and also provide methodological guidance for the research on other networks.3. In the case of(1, 1, 1)-conditional connection, we present a fault-tolerant unicast routing algorithm based on local information. This algorithm chooses the routing dimension through the spanning path whose length does not exceed 3. We analyze the time complexity and space complexity of the algorithm, and compare with several existing unicast routing algorithms in terms of success rate, running time and path length.4. Based on the concept of(g, d, k)-conditional edge connectivity, a new fault-tolerant Hamiltonian property is proposed, which is called to be f-(g, d, k) conditional edge faulttolerant Hamiltonian. This thesis studies that, when n ? 4, the n-dimensional hypercube is(4n- 13)-(3, 0, 0) conditional edge fault-tolerant Hamiltonian, and this rusult is optimal.Finally, the work of this paper is summarized, and the future research work is prospected.