在PMC模式下對k元n維立方體局部診斷能力之研究

Abstract

在這篇論文裡，我們介紹了一個新的衡量錯誤診斷能力的方法，稱為局部診斷能力。依據不同的觀點，來做不同的詮釋研究，從原本廣域的觀點轉換成局部的觀點來觀察。在新的觀點下，我們展示了一個簡單的方法來診斷一個多處理機系統。我們把局部診斷能力的研究應用在連線無損壞的k元n維立方體上，並觀察得每個點的價數(degree)即為其局部診斷能力。接著我們把局部診斷能力的研究應用在有任意連線損壞 的k元n維立方體上。根據我們在這篇論文裡的証明，在任意的損壞連線數不超過2n−2個數時，每點的局部診斷能力仍為每點的價數。此外，我們提出了一個更為有效率的演算法來診斷錯誤的發生。

In this thesis, we introduce a new measure for diagnosability, called local diagnosability, by changing the original global viewpoint to a local viewpoint. With this new viewpoint, we yield an easy way to diagnose a multiprocessor system. We apply the concept of local diagnosability to k-ary n-cube with no missing links and the local diagnosability of each node is exactly the degree of each node. Then we investigate the local diagnosability of k-ary n-cube with arbitrarily distributed missing links. Based on the result proved in this thesis, the number of missing links can be up to 2n−2 and the local diagnosability of each node is the remaining degree of each node. Moreover, we propose a more efficient diagnosis algorithm.