在比較模式下對類超立方體局部診斷能力之研究

Abstract

在多處理器系統中，診斷能力是判斷一個系統可靠度的重要依據。以往的文獻都是以全域的角度來看一個系統的診斷能力，本篇論文提出一種局部的診斷方法，並且用局部的診斷方法來證明類超立方體的診斷能力，最後我們提出一個診斷演算法，可以用來快速的診斷一個點的好與壞，其時間複雜度為O(nlgn)，其中n為一個系統的點數總和，比Sungupta提出的演算法O(n^5)更有效率 。

Interconnection networks have been an active research area for parallel and distributed computer system. We usually use a graph G=(V,E) to represent the topology of a network, where vertices represent processors and edges represent links between processors. The diagnosability has played an important role in the reliability of an interconnection network. In this thesis, we present a novel idea on system diagnosis called local diagnosability. There is a strong relationship between the local diagnosability and the traditional global one. For this local sense, we focus more on a single processor and require only identifying the status of this particular processor correctly. We propose a sufficient condition to determine the local diagnosability of a given processor, and we prove the diagnosability of Hypercube Like network HLn is n for n≧5 in this local sense. Moreover, we proposed a diagnosis algorithm to easily compute the local diagnosability of each node based on the comparison model.