Minimum Boundary And Diagnosability Of Interconnection Network

Multi-processor system is a main implementation of supercomputers. With the increasing size of supercomputers, the possibility of the presence of faulty processors in such systems is becoming increasingly large, leading to a dramatic drop in the reliability. So in the design of supercomputers, diagnosability and reliability analysis is quite important.The architecture of an interconnection network is always represented by a graph, where vertices represent processors and edges represent links between processors. Connectivity and edge connectivity are important parameters to measure the fault tolerance ability of interconnection networks. Although they can correctly reflect the fault tolerant ability of multiprocessors systems with just few processors. It greatly underestimate the fault tolerant ability of large multiprocessor systems. So some new parameters are proposes. The restricted connectivity, the super connectivity and the extra connectivity are among them. As the most famous and widely used interconnection networks, the Hypercube have been extensively studied and many of its properties have been acquired. The M?bius cube is a variation of Hypercube by replacing some links in Hypercube with other ones. It reserved both the recursive structure and the high connectivity of the Hypercube. They are both studied in this thesis.First, for 1 ?h ?3n- 6 we determined the h-extra connectivity of Hypercube by study the structure of faulty Hypercubes. The method used in this paper can get further results of the reliability of hypercubes.In chapter four, we stuied a parameter called the super diagnosability to Hypercube, which can measure the diagnosability of a multiprocessor system by restricting that there is no-trivial components after removing faulty vertices in a multiprocessor systems. We proved that in the n-dimensional Hypercube, the super diagnosability is 2n-1while the classical diagnosability is n.At last, we also studied the h-extra connectivity of M?bius cubes with similar methods like the Hypercube. Which means the methods used in this thesis are of some significance.