Diagnostic Performance Analysis Of Multiprocessor System Based On Internetworking

The network structure of multiprocessor system,called interconnection net-work,is a significant factor to determine the performance of multiprocessor system.With the rapid increase of the scale of multiprocessor systems based on internet-working,not only vertex faults take place but also edge malfunctions may arise inevitably.Fast and effective fault diagnosis is crucial for the reliability of multipro-cessor systems.Diagnosability is a key metric to the capability of fault identification for multiprocessor systems,which has been a research hotspot for a long time.In this thesis,graph theory modeling,combinatorial network theory analysis and sys-tem level fault diagnosis theory are used to resolve the diagnosability of regular networks.Our main research works are listed as follows.Firstly,a new diagnosis model,called the bounded PMC model,is proposed,which generalizes the classical symmetric PMC model and asymmetric BGM model.This thesis presents some properties and equivalent characterization of one-step diagnosability and f/(n-1)-diagnosability.As applications,one-step diagnosability of regular graphs under the bounded PMC model is determined,and some general f/(n-1)-diagnosable examples are constructed.Secondly,based on investigating more general and more practical diagnosability-hybrid diagnosability.In this thesis,we take two kinds of newly introduced hybrid diagnosabilities,the h-edge tolerant diagnosability and hybrid diagnosability with broken-down nodes and missing links,as our research objects and discuss the h-edge tolerant diagnosability of the maximally connected regular networks and the t-diagnosable networks under the PMC model and MM*model.We also determine the hybrid diagnosability of several kinds of regular networks.Our results with respect to h-edge tolerant diagnosability and the hybrid diagnosability under broken-down nodes and missing links generalize some existing results.Thirdly,we investigate the relationship among the non-inclusive diagnosability,the classical diagnosability and the conditional diagnosability of general networks.Furthermore,we give the upper and lower bounds of the non-inclusive diagnosability under the PMC model and MM*model,and show that the bounds we present are sharp.Finally,we give some characterizations such that the lower bound and the upper bound are reached.Finally,as for the widely-studied conditional diagnosability,we determine the conditional diagnosability of a family of networks-hyper bijective connection net-works,which are more general than BC networks,under the PMC model and MM*model.We show the 2-extra connectivity and 3-extra connectivity of hyper bijec-tive connection networks and reveal their strong robustness.Then,by the aid of fault tolerance,we show the conditional diagnosability of hyper bijective connec-tion networks under the PMC model and MM*model,respectively.The result of conditional diagnosability under the MM*model generalizes some initial results.