Reliability Analysis Of Multiprocessor System

Large scale multiprocessor systems always strive to ensure high reliability and fault tolerance when big data processing and high-performance computing are carried out.However,as the cardinality of multiprocessor systems grows,the probability of arising malfunctioning or failing processors in the system increases.It is then of both practical and theoretical importance to quantify the reliability of the system.There are five chapters in this thesis.In the first chapter,we first introduce basic conceptions and notations of graph theory and combinatorial network theory,and then present system-level diagnostic models based on test and comparison and probabilistic diagnostic model,respectively.Furthermore,some concepts of diagnosability and its characterization are provided.In the successive two chapters,we mainly focus on combinational fault tolerance and deterministic fault diagnosis.The second chapter resolves the DQcube on three aspects.Firstly,we show that DQcube is a Cayley graph based on hybrid product of abelian group(Zm(>)Z2)× 2n,i.e.,DQ(m,d,n)(?)Cay((Zm(>)Z2)× Z2n,S),and so is vertex-transitive.Secondly,we mainly explore connectivity and tightly super-connectivity of DQcube.Thirdly,the conditional diagnosabilities of DQcube under the PMC model and the MM*model are determined,respectively.In Chapter three,we present the discussion on Cayley coset graph—(n,k)-star graph,and Cayley graph-star graph.We mainly explore the h-extra conditional diagnosability under the PMC model and MM*model and t/h-diagnosability of these two graphs.Fur-thermore,we propose a t/h-diagnostic algorithm for the general regular network G under the PMC model,and establish the relationship between the h-extra connectivity and the t/h-diagnosability of the general regular network G.In the fourth chapter,we present a probabilistic diagnosis strategy and apply it for hypercube-based multiprocessor system,and carry out an analysis on the strategy effectiveness,which shows a very high rate of correct diagnosis,no matter it is under local scale or global scale.Although the discussion is done for a particular regular network(the hypercube),the strategy can shed light on the effectiveness of the probabilistic diagnosis for a large group of triangle-free multiprocessor systems.In the fifth chapter,we give concluding remarks and propose some constructive but unsolved problems.