Reliability And Hybrid Fault Diagnosis Of Interconnection Network

With the continuous development of information technology,the number of processors contained in high-performance computers has also increased rapidly.During the operation of the system,due to the interference of its own life and external factors,the processor and its links in the system inevitably fail.Interconnection network is the topological structure of multiprocessing system,which can directly reflect the related performance of the system.In order to ensure the effective information transmission between the fault-free processors in the system,reliability and fault diagnosis ability have become two important aspects in the design and maintenance of large-scale multiprocessor computer systems,which are usually reflected in the interconnection network with connectivity and diagnosis degree as parameter indicators.As the promotion of connectivity,h-extra connectivity and h-extra edge-connectivity can eliminate some faults in the system,so it can better measure the reliability of the system.In this paper,we first study the general situation of h-extra connectivity and h-extra edge-connectivity of balanced hypercubes and exchanged hypercubes.It is proved that the h-extra connectivity of balanced hypercubes is(2?(h-)12?n(10)n-2?(h-)12?)for1?h?2n-1;and the h-extra edge-connectivity of balanced hypercubes is(2h(10))1h-(4h-)1for h?2n-1and2?h?11.In the exchanged hypercubes,the h-extra connectivity of exchanged hypercubes is(h(10))1s-12(h~2(10)h)(10)1forh(27)s?t;and the h-extra edge-connectivity of exchanged hypercubes is(h(10)1)(s-)1forh(27)s?tand3?h?4.HPMC model can better measure the fault-tolerant performance of multiprocessor system in the case of point-edge hybrid fault than PMC model.Then h-restrict edge diagnosability and r-restrict vertex diagnosability are two new parameters of the t-diagnsability extended in the HPMC model.They are also the latest research results of the system-level diagnosis.Compared with the previous parameters extended by the t-diagnsability,they are more suitable for the fault diagnosis and analysis of the system in the actual circumstance.In this paper,we study the fault-tolerant performance of interconnection networks under HPMC model.First,we prove the general circumstance of the h-restrict edge diagnosability and r-restrict vertex diagnosability of the networks.Then we apply the results to the four famous networks of k-ary n-cubes,star graphs,BC networks and exchanged hypercubes,and determine their h-restrict edge diagnosability and r-restrict vertex diagnosability respectively.The above research results are of great theoretical value and practical significance for the application and popularization of balanced cube network and switched cube network in multiprocessor systems.In addition,by proving two kinds of new parameters of the general networks in the HPMC model,that is,h-restrict edge diagnosability and r-restrict vertex diagnosability,it provides a theoretical basis for the fault-tolerant performance of multiprocessor system in the cases of hybrid fault.