標題: 在比較模式下對類超立方體局部診斷能力之研究
Local Diagnosability of Hypercube Like Network under the Comparison Model
作者: 廖家緯
Chia-Wei Liao
譚建民
Jimmy J.M. Tan
資訊科學與工程研究所
關鍵字: 診斷能力;局部診斷能力;類超立方體;比較模式;診斷演算法;diagnosability;t-diagnosable;comparison model;MM* model;Hypercube Like network;local diagnosability;diagnosis algorithm
公開日期: 2005
摘要: 在多處理器系統中,診斷能力是判斷一個系統可靠度的重要依據。以往的文獻都是以全域的角度來看一個系統的診斷能力,本篇論文提出一種局部的診斷方法,並且用局部的診斷方法來證明類超立方體的診斷能力,最後我們提出一個診斷演算法,可以用來快速的診斷一個點的好與壞,其時間複雜度為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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009323608
http://hdl.handle.net/11536/79139
Appears in Collections:Thesis


Files in This Item:

  1. 360801.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.