配對合成網路的錯誤診斷研究

Abstract

在這個計劃中，我們研究multiprocessor system 的錯誤診斷問題(fault diagnosis problem)，關於多處理機系統的 錯誤自我診斷問題，在文獻中已有幾個不同的模式被 提出。Preparata, Metze and Chien 三人最早提出一種構想及模式。現在稱為 PMC-Model。在此模式下，兩個相連接的processor 可以互相偵測是否faulty。Maeng and Malek 在之後提出一種comparison model 稱為MM-model。他們對錯誤診斷的基本構想 是由一個processor 向相鄰的兩個processors，送出信號，然後由回收的訊號，比較並 判斷是否有fault。為了要收集到最多的資料以供錯誤診斷，在MM*-model 下,規定任一 個processor 都對其所有相鄰的兩個processors 作偵測及比較。 錯誤診斷在IEEE Trans. on Computers 及IEEE Trans. on Parallel and Distributed Computing 已有很多文獻研究。我們近年也在這個領域作了一些研究,並投稿至IEEE Trans. on Computers，已有一篇在做最後revision。 在這個計畫中，我們研究一種配對合成網路matching composition network (MCN) 的診斷能力(diagnosability)，在MM*-comparison model 下，配對合成網路的診斷能 力(diagnosability) ，與它的組成成分之間的diagnosability and connectivity 有 一定關係，我們研究其間的關係，可將文獻中有關各種cube 如hypercube, crossed cube, twisted cube and Mobius cube 的diagnosability 研究結果有一個統一的解釋。我們 已有一些研究成果,撰文投稿 。 對PMC- model 下的錯誤診斷也有所研究。我們定義出一種」strongly t-diagnosable systems」及」conditional diagnosability」的觀念。目前正在探究，期能繼續進行 成果收集。

We propose to study the diagnosis problem of multiprocessor system. For the purpose of self-diagnosis of a given system, several different models have been proposed in literature. Preparata, Metze, and Chien first introduced a model, so called PMC-model, for system level diagnosis in multiprocessor systems. In this model, it is assumed that a processor can test the faulty or fault-free status of another processor. The comparison model, called MM model, proposed by Maeng and Malek, is considered to be another practical approach for fault diagnosis in multiprocessor systems. In thisapproach, the diagnosis is carried out by sending the same testing task to a pair {u, v} of processors and comparing their responses. The comparison is performed by a third processor w that has direct communication links to both processors u and v. The third processor w is called a comparator of u and v. If the comparator is fault-free, a disagreement between the two responses is an indication of the existence of a faulty processor. To gain as much knowledge as possible about the faulty status of the system, it was assumed that a comparison is performed by each processor for each pair of distinct neighbors with which it can communicate directly. This special case of MM-model is referred to as the MM*-model. Sengupta and Dahbura studied the MM-model and the MM*-model, gave a characterization of diagnosable systems under the comparison approach, and proposed a polynomial time algorithm to determine faulty processors under MM*-model. In this proposal, we consider the diagnosability of a family of networks, called the Matching Composition Network (MCN); two components are connected by a perfect matching. The diagnosability of MCN under the comparison model is shown to be one larger than that of the component, provided some connectivity constraints are satisfied. Applying our result, the diagnosability of the Hypercube Qn, the Crossed cube CQn, the Twisted cube TQn, and the Mobius cube MQn can all be proved to be n, for n . 4. We shall also study the diagnosis problem under PMC-model. We define some new concepts called strongly t-diagnosable system and conditional diagnosability, we are currently working on this subject.