| Abstract: | 在大型平行計算機器中，超立方體結構圖(hypercube)是最為廣泛使用的。其結構上的正規性(regularity)可使得電腦系統能較容易地被建立起來，而平行演算法上的容錯性使得一般與網路拓蹼結構相關的平行演算法不須經過大幅修改就能容易地被移植到超立方體結構電腦系統上來執行。可逐步擴充超立方體(Incrementally Extensible Hypercube)是超立方體的變形結構，它可以有任意的節點個數，並且保證其直徑(diameter)為節點個數和的對數值，以及每一個節點的鏈結分支度(degree)相差最多為1。本論文中，我們討論將一些正規的網路拓蹼，例如，環路(ring)、網格(mesh)及樹(tree)，嵌入至有容錯能力的可逐步擴充超立方體結構的演算法。
而費伯納茲立方體結構(Fibonacci Cube)，也是近年熱門的超立方體變形結構，本論文也一並討論將它嵌入至有容錯能力之超立方體結構的方法。在這些議題中，我們利用位元移動的方法，提出了一些容錯演算法，並且得到了重要的結果。在可逐步擴充超立方體有節點發生故障的情形下，可將環路結構完全嵌入，並達到延展度4、擴張度N、壅塞度1及負載度1。容錯程度達到O(n*log2m)。網格與樹的嵌入也有O(n2-(r+s)2)及O(n2-h2)的容錯程度。此外我們也對於費伯納茲立方體結構嵌入至有錯誤節點的超立方體結構的演算法作一討論，並達到延展度3、擴張度N、壅塞度1及負載度1及O(m2-n2)的容錯程度。
The hypercube is a widely-used interconnection architecture in the parallel machine. The Incrementally Extensible Hypercube (IEH), which is derived from the hypercube, is a generalization of interconnection network. Unlike the hypercube, the IEH can be constructed for any number of nodes. In other words, the IEH is incrementally expandable. In this thesis, the problem of embedding and reconfiguring some regular structures is considered in an IEH with faulty nodes. In recent years, the Fibonacci cube is a new interconnection architecture derived from hypercube. It also has some properties differ from hypercube. Thus we discuss the embedding of Fibonacci cube into the faulty hypercube. Some fault-tolerant embedding algorithms are proposed in this thesis. First, the algorithm in the present study enables us to obtain the good embedding of a ring into a faulty IEH with 2-expansion. Such result can be tolerated up to (n+1) faults with congestion 1, load 1, and dilation 3. When we allow unbounded expansion, the result of embedding of a ring into a faulty IEH can be tolerated up to O(n*log2m) faults with congestion 1, load 1, and dilation 4. The embedding methods in the study are mainly optimized for balancing the processor loads, under the situation of minimizing dilation and congestion as far as possible. Next we consider embedding of mesh into faulty IEH. In 2-expansion, it can be tolerated (n+1) faults with dilation 3, congestion 1, and load 1. Moreover, it can be tolerated up to O(n2-(r+s)2) in unbounded expansion. We discuss embedding of a complete binary tree into faulty IEH in the third. The cost is dilation 4, congestion 1, and load 1. In 2-expansion and unbounded expansion, embedding of a complete binary tree into faulty IEH can be tolerated (n+1) and O(n2-h2) faults. Finally, embedding of Fibonacci cube into faulty hypercube with dilation 3, congestion 2, load 1, unbounded expansion and O(m2-n2) faults can be tolerated, induced by our algorithm. |
