system-level diagnosis of multiprocessor systems
Date Issued
2005
Date
2005
Author(s)
Chang, Guey-Yun
DOI
en-US
Abstract
Abstract
System-level diagnosis is a process of identifying faulty processors in a system by conducting tests on various processors and interpreting the test results. A natural application of system-level diagnosis is the diagnosis of multiprocessor systems. Recently, it has been considered with renewed interest in the wafer-scale VLSI testing. There are three important issues in system-level diagnosis: characterization, diagnosiabilities and designing diagnosis algorithms. In the dissertation, we consider diagnosabilities and designing diagnosis algorithms for several classes of systems under two diagnosis models (the PMC model and the MM* model) and two classes of diagnosis strategies: one class includes one-step diagnosis, sequential diagnosis and (t,k)-diagnosis; the other includes precise diagnosis and pessimistic diagnosis.
Under one-step diagnosis strategy, one-step diagnosabilities of regular multiprocessor systems for two diagnosis models (i.e., the PMC and comparison models) and two diagnosis strategies (i.e., the precise and pessimistic diagnosis strategies) were considered. Many well-known and unknown but potentially useful multiprocessor systems were computed. These include hypercubes, enhanced hypercubes, twisted cubes, crossed cubes, Möbius cubes, cube-connected cycles, tori, star graphs, and many others. Some of these are established in several previous papers, and many are new. Our results were obtained as a consequence of four sufficient conditions. The four sufficient conditions can derive diagnosabilities for a class of regular systems.
Under sequential diagnosis strategy, topological properties for sequentially diagnosable systems under the PMC model and the MM* model were shown. Further, an efficient sequential diagnosis algorithms for chordal networks under the PMC model and the MM* model were also given.
Under (t,k)-diagnosis strategy, (t,k)-diagnosis algorithms for
matching composition networks introduced by Lai { et al.}, and
irregular systems under the PMC model and MM* model were proposed.
The diagnosabilities were also computed as follows: a matching
composition network with N vertices is (Ω(Nloglog N log N}), log N)-diagnosable under the PMC model and (Ω(Nloglog N log N}), log N)-diagnosable under the MM* model, where N > 2^5.
When k=1, a lower bound of Ω(Nloglog N log N}) is derived for the sequential diagnosability of matching composition networks. Applying our result, a lower bound
of the (t,k)-diagnosabilities of hypercubes, crossed cubes,twisted cubes, Möbius cubes and grids under the PMC model and the MM* model can all be obtained. And, a lower bound of the sequential diagnosabilities of these interconnection networks can be obtained, also.
Subjects
多處理機系統
系統偵錯
超方體
容錯
diagnosis
multiprocessor systems
hypercubes, PMC model
Type
thesis