Reliability Evaluation Of Hypercubes And Its Several Famous Variants

In recent years,multiprocessor computer systems have become the trend of modern com-puters development,however,they are vulnerable to the probability of system failures with the increase in the number of processors.Therefore,solving the reliability of multiprocessor system is a key problem for the application and popularization of multiprocessor computer system.In fact,underlying interconnection network of multiprocessor system is one of the dominating factors of performance of the system,that is,the reliability of computer system largely depend on the reliability of their underlying interconnection network.In this thesis,the fault tolerance and system diagnosis of multiprocessor systems based on hypercube and its variant structures are examined by deterministic methods.Firstly,the fault tolerance of the system can be characterized by the probability of con-nectedness of the surviving interconnection network in the presence of failures.Recent-ly,people have explored the fault tolerance of interconnection network by using minimal cut sets,and clearly showed the existence of h-extra cut sets.The folded hypercube is a variant of hypercube and has some excellent performances than the same dimension hy-percube.Therefore,we study and determine that the minimum h-cluster degree of FQn is?hc(FQn)= ?hc(Qn-1)+2h,and to further determine the h-extra connectivity of FQn,that is,?h(FQn)= ?h+1 c(FQn),where 0 ? ? n-3.Which is better to reflect the fault tolerance ability of the interconnection network than the traditional connectivity ?(FQn)= n + 1.Secondly,connectivity is only confined to the layout and design of the interconnection net-work,which can contribute little to the operational reliability of the interconnection net-work.It is a powerful tool for System-level fault diagnosis to identify faulty processors in measuring the operational reliability of the interconnection network.The maximal number of faulty processors,which can be guaranteed to be diagnosed,is called the dianosability of the system.In this thesis,we investigate the h-extra conditional diagnosability of balanced hypercube BHn.The 4,5-extra connectivity of BHn are proved to be 6n-8,and the 4,5-extra conditional diagnosability of BHn under PMC model are determined to be 6n-3 for n>4.Finally,these parameters of measuring the fault diagnosis capability are all only applicable to the circumstance with no link faults in the system,but in real circumstance,both node and link faults may occur simultaneously when a network is put into use.In order to adapt to the real circumstances where both node and link faults may occur,we introduce the h-edge tolerable diagnosability and determine the h-edge tolerable diagnosability of hypercube Qn under the PMC model and MM*model as follows:the(Qn)= n-h,where 1 ? h ? n,n>4.In summary,we study the fault tolerance and diagnosability of two kinds of networks,and propose a new parameter-h-edge tolerable diagnosability to better measure the diagnosis capability of hypercube under hybrid fault circumstances.These results benefit the practi-cality of the above-mentioned interconnection networks in the theory.