陳健輝臺灣大學：資訊工程學研究所洪浩舜Hung, Hao-ShunHao-ShunHung2007-11-262018-07-052007-11-262018-07-052007http://ntur.lib.ntu.edu.tw//handle/246246/54109隨著 VLSI 技術的進步，建造幾千甚至幾萬顆處理器的超大型的平行和分散式系統已經可以實現了。而這些平行和分散式的系統中，處理器之間的拓璞性質是非常重要的。在各種拓墣性質中，因為超立方體 (hypercube) 擁有最多吸引人的性質，是最被廣泛討論的。而經由調整一些超立方體連結而得到的交錯立方體 (crossed cube)，擁有許多比超立方體更好的性質。在一個系統中，處理器和他們之間的連結都有可能發生錯誤。因此考慮一個連結網路的容錯能力是非常重要的。一般來說，有兩種考量連結網路容錯能力的模型：隨機錯誤 (random fault) 和條件錯誤 (conditional fault)。假設錯誤會毫無限制的隨機發生稱為隨機錯誤。相對於隨機錯誤，條件錯誤則是假設這些錯誤發生時會滿足某些條件。 在這本論文裡，我們在考慮條件錯誤的狀態下，討論了交錯立方體上的各種容錯能力。在假設每個節點至少跟兩個健康的連結相連的情況下，我們證明了一個 n 維的交錯立方體，即使有 2n – 5 個連結發生損壞，還是可以在它上面找到一個漢米爾頓環 (Hamiltonian cycle)。接著也證明了同樣假設下，我們可以找到任何可能長度的環。以能容忍的連結損壞的角度來看，這個結果是最佳的。我們分析出這個假設發生的機率非常接近 1，更證明了這個假設是非常有意義的。另一方面，在每個節點至少有一個相鄰的點是沒有損壞的假設下，我們也證明了一個 n 維的交錯立方體的連接度 (connectivity) 是 2n – 2。而且他的 (2n – 3)-容錯直徑 (fault dameter) 是[(n + 1) / 2] + 3。這些結果都顯示了交錯立方體的容錯能力，在條件錯誤的考量下，並不亞於超立方體。Recently, advances in VLSI circuit technology made it possible to build a large parallel and distributed system involving thousands or even tens of thousands of processors. Designing the topology is very important in a parallel and distributed system. Among these networks, the hypercube is a popular interconnection network with many attractive properties. On the other hand, the crossed cube, which is a variation of the hypercube, possesses some properties superior to the hypercube. Since node and/or link faults may occur to networks, it is significant to consider faulty networks. There are two commonly used fault models, i.e., the arbitrary fault model and the conditional fault model. The arbitrary fault model assumes that the faults may occur everywhere without any restriction, whereas the conditional fault model assumes that the distribution of faults must satisfy some properties. In this thesis, we are interesting in fault tolerance of crossed cubes under conditional faults. Assuming that each node is incident with at least two fault-free links, we show that an n-dimensional crossed cube contains a fault-free Hamiltonian cycle, even if there are up to 2n-5 link faults. We further show that an n-dimensional crossed cube contains fault-free cycles of all possible lengths. The result is optimal with respect to the number of link faults tolerated. We also verify that the assumption is practically meaningful by evaluating its probability to occur, which is very close to 1. On the other hand, assuming that each node has at least one fault-free neighbor, we show that an n-dimensional crossed cube has connectivity equal to 2n-2 and (2n-3)-fault diameter equal to [(n+1)/2]+3. All these result shows the fault tolerance of crossed cube is as good as hypercube, under the conditional fault model.1 Introduction.....................................1 1.1 Crossed Cubes .................................2 1.2 Fault Tolerance ...............................3 1.3 Conditional Faults.............................4 1.4 Thesis Organization ...........................6 2 Preliminaries of Crossed Cubes...................7 3 Fault-Free Hamiltonian Cycles in Crossed Cubes with Conditional Link Faults...........................11 3.1 Properties of Crossed Cubes...................11 3.2 Proof of Theorem 3.7..........................19 3.3 Probabilities and Optimality..................23 4 Embedding Fault-Free Cycles in Crossed Cubes with Conditional Link Faults...........................26 4.1 Properties of Crossed Cubes...................26 4.2 Fault-Free Cycles of All Possible Lengths.....32 5 Connectivity and Fault Diameter of Crossed Cubes with Conditional Node Faults...........................44 5.1 Properties of Crossed Cubes...................44 5.2 Proof of Lemma 5.13...........................56 5.2.1 k is even...................................57 5.2.2 k is odd....................................66 5.3 Main Results..................................87 6 Discussion and Conclusion.......................90 6.1 Contribution..................................90 6.2 Future Research...............................941313650 bytesapplication/pdfen-US條件錯誤交錯立方體嵌入環容錯能力連結網路漢米爾頓環連接度容錯直徑conditional faultcrossed cubecycle embeddingfault toleranceinterconnectionthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54109/1/ntu-96-D90922001-1.pdf