Reliability Evaluation Of Multiprocessor System Based On Half Hypercubes

In the wake of rapid development of large-scale multiprocessor systems, which in-creases the vulnerability of system components, reliability and self-diagnostic capability of systems are two significant metric parameters in the design and choice of the topological structures of multiprocessor systems.A network's diagnosability is an important measure of its self-diagnostic capabili-ty. The diagnosabilities of many well-known network topological structures have been investigated, such as hypercubes, star graphs, alternating group graphs, k-ary n-cubes, et al. Obviously, the hypercube is one of the most popular network structures. The half hypercube, proposed by Kim et al, is a new improvement of the hypercube, which reduces the hypercube degree by approximately half with the same number of vertices. This the-sis investigates the reliability of the half hypercube from the aspects of fault tolerance performance and fault diagnostic performance.In the introduction, we introduce some research background, significance, research status and the latest progress of interconnection networks, fault tolerance theory and system-level diagnosis theory. There are five chapters in this thesis.The first chapter introduces some basic knowledge. It mainly includes terminologies in graph theory, combinatorial network theory, the principle of the design of networks, as well as some diagnostic models of system-level diagnostic theory.The second chapter is devoted to the structure properties of hypercubes and half hypercubes, which paves the way for subsequent exploration.In the third chapter, we concentrate on the fault tolerance performance of the half hypercube. The connectivity and the h-extra, connectivity (1?h?3) of the half hypercube are derived through its vulnerability analysis.The fourth chapter investigates the fault diagnostic performance of the half hyper-cube. In detail, we show that precise diagnosability. pessimistic diagnosability and condi-tional diagnosability of the half hypercube under the MM* model are [n/2]+1 (n?4), 2[n/2] (n?9) and 3[n/2]-2 (n?6). respectively. Besides, we a,lso determine these three kinds of diagnosabilities of the half hypercube under the PMC model are [n/2]+1 (n?3),2[n/2] (n?7) and 4[n/2]-3 (n?T), respectively. Moreover, we solve t/k-diagnosability and t/k-diagnosis algorithm of the half hypercube under the PMC modelFinally, we conclude with some remarks and outline some considerable future work in this area.