比較模組下多處理器系統診斷能力之局部量測

Abstract

系統診斷對於多處理器系統的可靠度來說是個相當重要的議題，而計算出一系統的診斷力也在近年來許多的研究上被廣為討論。在這篇論文當中，我們提出了一個新穎的診斷觀念─點診斷力，即為一局部的策略、從一點的觀點來計算出整個系統的全域診斷力，而這個局部點診斷力和整個系統的全域診斷力可謂息息相關。利用此局部的概念，我們將重心放在任意挑選的一點之上，以比較模組作為探討的基礎，我們提出了一個充分的條件，以計算出某點的局部點診斷力；我們也提出了一個稱之為延伸星狀圖的有用架構，以利我們判斷出某點的點診斷力之大小。除此之外，基於此局部診斷的觀點，我們也討論了一重要的性質─強點診斷性質；此性質說明了當某種條件成立時，我們可確保在一系統中，某點的局部點診斷力會等同於他自身的維度。最後，利用延伸星狀圖的特點，我們提出了一個能夠偵測出系統上所有點好壞的演算法；若一多處理系統上的總點數為N，我們提出的演算法將能達到O(N logN)的表現，運用到大多數遞迴建構起的多處理器系統上都會有著不錯的效能。

Diagnosis is an essential subject for the reliability of a multiprocessor system. Determining a system’s diagnosability is a widely discussed issue on recent research. In this thesis, we present a novel idea on system diagnosis called node diagnosability. The node diagnosability can be viewed as a local strategy toward system diagnosability. There is a strong relationship between the node diagnosability and the traditional diagnosability. For this local sense, we focus more on a single processor and require only identifying the status of this particular processor correctly. Under the comparison diagnosis model, we propose a sufficient condition to determine the node diagnosability of a given processor. We also propose a useful local structure called an extended star to guarantee the node diagnosability. Based on the local sense of diagnosis, the strongly node-diagnosable property is discussed; this property describes the equivalence of the local diagnosability of a node and its degree. Furthermore, we provide an efficient algorithm to determine the faulty or fault-free status of each processor based on this structure. For a multiprocessor system with total number of processors N, the time complexity of our algorithm to diagnose a given processor is O(logN) and that to diagnose all the faulty processors is O(N logN) under the comparison model, provided that there is an extended star structure at each processor and that the time for looking up the testing result of a comparator in the syndrome table is constant. This newly proposed diagnosis algorithm has a well performance on most recursively constructed multiprocessor systems.