多處理器系統診斷能力之量測

Diagnosability Measures for Multiprocessor Systems: A New Local Strategy

徐國晃(Guo-Huang Hsu)

指導教授 ： 譚建民

國立交通大學/資訊學院/資訊科學與工程研究所/博士(2009年)

https://doi.org/10.6842/NCTU.2009.00051

摘要

有關多處理機系統錯誤診斷問題已經在相當多的文獻被廣泛的討論，並且很多著名連結網路的診斷能力也已經被提出來了。在這篇論文當中，我們針對多處理機系統研究了一些不同的診斷問題。首先，我們介紹了一種新的診斷能力量測方法稱為局部診斷能力量測，並且提出了一些架構用來決定系統中一個處理機在PMC診斷模式下是否為局部t-可診斷的。針對超立方體網路(hypercube)和星狀網路(star graph)，我們證明了網路中每一個點的局部診斷能力等於它們自己的分支度。接著，我們針對系統診斷問題提出了一個新的觀念稱為強局部可診斷特性。一個系統我們說他具有強局部可診斷特性即表示此系統中每一個處理機的局部診斷能力等於它們自己的分支度。所以我們可以推得n維度超立方體網路Qn和星狀網路Sn都有此很強的特性，當n >= 3。下一步我們接著研究當多處理機系統具有一些壞掉的邊時，每一個點它們的局部診斷能力。對於具有一些壞掉的邊的n維度超立方體網路Qn和星狀網Sn，我們證明了Qn在壞n-2條邊以內其仍然保有此很強的特性，而Sn在壞n-3條邊以內也仍然保有此特性。假設網路在壞掉邊時每一個點具有至少兩條好的邊時，在這樣的條件下，我們證明了Qn壞掉的邊數可以增加到3(n–2)–1條仍然保有這種強特性，而Sn在此條件下無論壞多少條邊仍然可保有此特性。更進一步地，我們考慮網路在壞掉邊時每一個點具有至少三條好的邊時，在這樣的條件下，我們證明了Qn無論壞多少條邊仍可保有此很強的特性，並且我們所提出的這些壞邊數都是最佳值。除此之外，我們針對一般系統也提出了一個新的診斷演算法。此演算法的時間複雜度為O(N log N)，此處N代表系統中處理機的總數。

條件式診斷能力量測是由賴等人所提出的，此量測方法在多處理機系統是另外一個有趣的議題。此量測方法在量測一個系統的診斷能力時給予一個條件，此條件為，在系統中任一個錯誤點集合不能包含任一個點的所有鄰居。本篇論文當中，我們根據這個條件去計算一個n維度超立方體網路Qn在比較式診斷模式下它的條件式診斷能力，並且得到的答案為3(n-2)+1，當n >= 5。此條件式診斷能力約是傳統診斷能力的三倍之多。最後，我們延伸這個結果到BC(bijective connection)網路上，一個n維度BC網路記作Xn，此網路是一個n-正規圖具有2^n個點和n2^{n-1}條邊。一般常見的超立方體網路(hypercube)、交錯超立方體網路(crossed cube)、雙扭超立方體網路(twisted cube)和梅式超立方體網路(Mobius cube)都是BC網路的一種。在這篇論文當中，我們也證明了一個n維度BC網路Xn在比較式診斷模式下它的條件式診斷能力為3(n-2)+1，當n >= 5。根據這個結果，我們可以推得所有立方體網路的條件式診斷能力。

關鍵字

PMC 診斷模式 ； 比較式診斷模式 ； t-可診斷的 ； 診斷能力 ； 局部診斷能力 ； 強局部可診斷特性 ； 條件式錯誤集合 ； 條件式診斷能力 ； 超立方體網路 ； 星狀網路 ； BC網路 ； 診斷演算法

並列摘要

The problem of fault diagnosis has been discussed widely and the diagnosability of many well-known networks has been explored. In this thesis, we study some variants of diagnosis problems on multiprocessor systems. First of all, we introduce a new measure of diagnosability, called local diagnosability, and derive some structures for determining whether a vertex of a system is locally t-diagnosable under the PMC model. For hypercube network and star graph, we prove that the local diagnosability of each vertex is equal to its degree. Then, we propose a concept for system diagnosis, called strongly local-diagnosable property. A system G(V,E) is said to have a strongly local-diagnosable property, if the local diagnosability of each vertex is equal to its degree. We show that both Qn and Sn have this strong property for n >= 3, where the two notations Qn and Sn represent an n-dimensional hypercube and an n-dimensional star graph, respectively. Next, we study the local diagnosability of a faulty multiprocessor system. For a faulty hypercube Qn and a faulty star graph Sn, we prove that both Qn and Sn keep this strong property even if they have up to n–2 faulty edges and n–3 faulty edges, respectively. Assume that each vertex of a faulty hypercube Qn and a faulty star graph Sn is incident with at least two fault-free edges, we prove that Qn keeps this strong property even if it has up to 3(n–2)–1 faulty edges and Sn will also keep this strong property no matter how many edges are faulty. Furthermore, we prove Qn keeps this strong property no matter how many edges are faulty, provided that each vertex of a faulty hypercube Qn is incident with at least three fault-free edges. Our bounds on the number of faulty edges are all tight. Besides, we propose a new diagnosis algorithm for general systems. The time complexity of our algorithm to diagnose all the faulty processors is bounded by O(N log N), where N is the total number of processors.

The conditional diagnosability measure, introduced by Lai et al., is another interesting issue for multiprocessor systems. They proposed this novel measure of diagnosability by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. In this thesis, We make a contribution to the evaluation of diagnosability for hypercube networks under the comparison model and prove that the conditional diagnosability of n-dimensional hypercube Qn is 3(n–2)+1 for n >= 5. The conditional diagnosability of Qn is about three times larger than the classical diagnosability of Qn. Furthermore, we extend the result to bijective connection network (in brief, BC network). An n-dimensional BC network, denoted by Xn, is an n-regular graph with 2^n vertices and n2^{n-1} edges. The n-dimensional hypercube, crossed cube, twisted cube, and Mobius cube are some examples of the n-dimensional BC networks. In this thesis, we also prove that the conditional diagnosability of Xn is 3(n–2)+1 under the comparison model, n >= 5. As a corollary of this result, we obtain the conditional diagnosability of the cube family.

並列關鍵字

PMC model ； comparison model ； t-diagnosable ； diagnosability ； local diagnosability ； strongly local-diagnosable property ； conditional faulty set ； conditional diagnosability ； hypercube network ； star graph ； BC network ； diagnosis algorithm

參考文獻

[1] R. Ahlswede and H. Aydinian, “On Diagnosability of Large Multiprocessor Networks,”

[2] S. B. Akers, “A Group-Theoretic Model for Symmetric Interconnection Network,”

IEEE Trans. Computers, vol. 38, no. 4, pp. 555-566, 1989.

[4] J. R. Armstrong and F. G. Gray, “Fault Diagnosis in a Boolean n Cube Array of

[5] A. Bagchi, “A Distributed Algorithm for System-Level Diagnosis in Hypercubes,”