多處理器網路的錯誤診斷問題

Abstract

在超大型平行計算的處理器(processor)網路中，通常會用一個圖G=(V,E)來代表其內部的連結網路，其中處理器使用點(V)來表示，而處理器之間的連接線則用邊(E)來表示之。因此討論一個圖G的特性，相當於討論這個大型連結網路的特性。錯誤(fault)診斷能力(diagnosability)對網路的容錯能力(fault-tolerant)與可靠度(reliability)是一項極為重要的特性。因為網路架構中處理器或網路連線均有可能發生錯誤，所以很多網路結構的錯誤診斷(fault diagnosis)性質均已被探討。 關於多處理器系統的錯誤自我診斷問題，在文獻中已有幾個不同的模式被提出。Preparata, Metze 與 Chien 三人最早提出一種構想及模式，現在稱為PMC-Model。在此模式下，兩個相連接的處理器可以互相偵測是否錯誤。Maeng與Malek 在之後提出一種comparison model稱為MM-model。他們對錯誤診斷的基本構想是由一個處理器向相鄰的兩個處理器送出信號，然後由回收的訊號，比較並判斷是否有錯誤。為了要收集到最多的資料以供錯誤診斷，在MM*-model下,規定任一個處理器都對其所有相鄰的兩個處理器作偵測及比較。 在本論文中，我們研究一種配對合成網路(matching composition network,MCN)的診斷能力，在MM*-comparison model下，配對合成網路的診斷能力，與它的組成成分(Components)之間的診斷能力與連通度(connectivity)有一定關係，我們研究其間的關係，可將文獻中有關各種cube，如：hypercube，crossed cube，twisted cube與Mobius cube等的診斷能力研究結果有一個統一的解釋。另外，我們也探討了卡迪生乘積(cartesian product)網路在MM* model下的的診斷能力，對Mesh、Tori、k-ary n-cubes及generalized hypercubes 等結構網路，也說明他們的診斷能力。 然而，對許多已知的網路結構來說，傳統的錯誤診斷能力經常受限於最小的鄰接點數(minimum degree)，但對網路中任一個處理器而言，他所有的鄰接處理器均是錯誤的機率不高。因此對PMC-model下的錯誤診斷，我們介紹“強 t-可診斷系統(strongly t-diagnosable systems)”及“條件式診斷能力(conditional diagnosability)”的觀念。並證明在假設“對網路中任一個處理器，他所有的鄰接處理器不會全是錯誤”的條件下，網路的錯誤診斷能力將會大幅提升，如：超立方體結構網路(hypercube)的條件式錯誤診斷能力在符合此條件下，上升為約傳統錯誤診斷能力的四倍。

Interconnection networks have been an active research area for parallel and distributed computer systems. 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. There are a lot of interconnection network properties proposed in literature. The diagnosability has played an important role in the reliability of an interconnection network. Since processors or links may fail sometimes, diagnosable properties are also concerned in many studies on network topologies. The classical problem of diagnosability is discussed widely and the diagnosability of many well-known networks have been explored. In this thesis, we consider the diagnosabilities of two families of networks, one is called the Matching Composition Network (MCN); two M-components (which will be defined subsequently) are connected by a perfect matching. The diagnosability of MCN under the comparison model is shown to be one larger than that of the M-component, provided some connectivity constraints are satisfied. Applying our result, the diagnosability of the Hypercube Qn, the Crossed cube CQn, the Twisted cube TQn, and the M¨obius cube MQn can all be proved to be n, for n ≥ 4. In particular, we show that the diagnosability of the 4-dimensional Hypercube Q4 is 4 which is not previously known. Another family is the product networks, constructed by applying cartesian product operation on factor networks. It would be interesting to combine two known topologies with established properties to obtain a new one that inherits properties from both. We prove that the product network of G1 and G2 is (t1+t2)-diagnosable, where Gi is either ti-diagnosable or ti-connected with regularity ti for i = 1, 2. Furthermore, we use different combinations of ti-diagnosability and ti-connectivity to study the diagnosability of the product networks. We show that the product network of G1, G2, . . . , and Gk is (t1 +t2 + . . .+tk)-diagnosable, where each Gi is either ti-diagnosable or ti-connected with regularity ti for 1 ≤ i ≤ k. In this thesis, we introduce a new measure of conditional diagnosability by restricting that any faulty set cannot contain all the neighbors of any vertex in the graph. Based on this requirement, the conditional diagnosability of the n-dimensional Hypercube is shown to be 4(n − 2) + 1, which is about four times as large as the classical diagnosability. Besides, we propose some useful conditions for verifying if a system is t-diagnosable, and introduce a new concept, called strongly t-diagnosable system, under PMC model. Applying these concepts and conditions, we investigate some t-diagnosable networks which are also strongly t-diagnosable.