Diagnosability Analysis Of Multiprocessor System Based On Regular Topologies

With the advance of network technology and the increase of network scale,so does the emphasis on the research in the areas of reliability,design-for-test,fault diagnosis and detection of large-scale multiprocessor interconnected systems.System-level diagnosis theory,which originates from the testing of VLSI and Wafer,aims to identify faulty processors in these systems by means of analyzing the test results among the processors.Diagnosability is an important metric parameter for measuring the fault tolerance of these systems.There are five chapters in this thesis.In the introduction,we introduce some re-search background,significance,research status and the latest progress of interconnection networks,fault tolerance theory and system-level diagnosis theory.And we also introduce some basic knowledge,which mainly includes terminologies in graph theory,combinato-rial network theory,the principle of the design of networks,as well as some diagnostic models of system-level diagnostic theory.The second chapter presents some determinant characterizations on t/x-diagnosability and t[x]-diagnosability of regular network based on multiple-valued logic.Suppose r ≥ 3 and G =(V,E)is a triangle-free r-regular system,which is not isomorphic to G8 or Gτ+1,τ+1.Then G is t[x]-(or t/x)-diagnosable by comparison strategy if N(u)≠ N(v)holds for any two distinct nodes u and v of G.In third chapter,we establish the g-good-neighbor diagnosability for n-dimensional complete cubic network CCN(n),which is a generalization of hierarchical cubic network.In detail,we show that the g-good-neighbor diagnosability of the complete cubic network CCN(n)under the PMC model(1 ≤ g≤ n-2)and the MM*model(1≤g ≤n-2 and n ≥ 4)is(n-g + 2)29-1,respectively.The fourth chapter investigates the strong local diagnosable property of(n + 1)-dimension DQcube,which is a novel composition architecture of disc-ring and hypercube,under the comparison model.In addition,we design efficient algorithms to build Hamil-tonian paths and extended stars,which can be used to identify all faulty processors in(n + 1)-dimensional DQcube if the number of faulty processors is no more than n + 1.Finally,we conclude with some remarks and outline some considerable future work in this area.