多處理機系統之系統偵錯

system-level diagnosis of multiprocessor systems

張貴雲(Guey-Yun Chang)

指導教授 ： 陳健輝

共同指導教授 ： 張鎮華

國立臺灣大學/電機資訊學院/資訊工程學研究所/博士(2005年)

https://doi.org/10.6342/NTU.2005.01322

摘要

摘要
系統偵錯（system-level diagnosis）是根據系統中各個處理機相互測試的結果，推導出系統中錯誤處理機程序。系統偵錯原本應用在多處理機系統。最近，晶圓的測試也開始使用系統偵錯的技術。系統偵錯包含三個重要的研究主題：特性描述（characterization）、可偵錯度（diagnosabilities）計算、偵錯演算法設計。本論文主要考慮在兩個不同偵錯模式（PMC model 和MM* model）和兩類不同的偵錯策略（第一類偵錯策略包括單步偵錯（one-step diagnosis）、循序偵錯（sequential diagnosis）和 (t, k)-偵錯；第二類偵錯策略包括精確偵錯（precise diagnosis）和非精確偵錯（pessimistic diagnosis））下研究可偵錯度計算和偵錯演算法設計。

首先，本論文考慮單步偵錯策略。我們在兩個不同偵錯模式和第二類的兩種不同偵錯策略下探討規則多處理機系統（regular multiprocessor systems）之可偵錯度問題。本論文中推導出四個定理。根據這四個定理，可以得到許多常見以及未見但實用的規則多處理機系統的可偵錯度。其中，hypercubes、enhanced　hypercubes、twisted cubes、crossed cubes、Möbius cubes、cube-connected cycles、tori和star graphs。

接下來，本論文考慮循序偵錯策略。我們推導出有用的循序偵錯系統拓樸性質。根據這些拓樸性質，設計出弦圖（chordal graphs）在兩個不同偵錯模式下的偵錯演算法。

最後，本論文考慮(t, k)-偵錯策略。我們成功地為matching composition networks（由賴寶蓮等提出）和非規則多處理機系統（irregular multiprocessor systems）設計出(t, k)-偵錯演算法。同時，我們也計算出一個包含N個多處理機之matching composition networks的(t, k)-可偵錯度下限(lower bound)：在 PMC 模式和MM* 模式下都是 (Ω(Nloglog N / log N), log N)。當 k=1時，(Ω(Nloglog N / log N), 1) 即是matching composition networks的循序可偵錯度的下限。根據這些結果，我們可以得到hypercubes、twisted cubes、crossed cubes、Möbius cubes和grids的(t, k)-可偵錯度下限和循序可偵錯度的下限以及(t, k)-偵錯演算法和循序偵錯演算法。

關鍵字

多處理機系統 ； 系統偵錯 ； 超方體 ； 容錯

並列摘要

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.

並列關鍵字

diagnosis ； multiprocessor systems ； hypercubes, PMC model

參考文獻

[1] S. B. Akers, D. Harel, and B. Krishnamurthy, “The star graph: an attractive alternative

to the n-cube,” Proceedings of the International Conference on Parallel Processing, pp.

393-400, 1987.

[3] F. J. Allan, T. Kameda, and S. Toida, “Approach to the diagnosability analysis of a

system,” IEEE Transaction on Computers, vol. 25, pp. 1040-1042, 1975.