三種凱利圖上的邊容錯路徑/迴圈嵌入問題之研究

Abstract

當前VLSI技術的進步，使得建造數千甚至數萬顆處理器的超大型平行分散式系統已經可以實現了。而在這些平行分散式系統當中，其中一個重要的步驟就是決定各個處理器之間連結的拓樸性質（稱之為連結網路）。網路的拓樸性質影響了平行分散式系統的硬體層面和軟體層面的各種設計。有許多的連結網路已經被提出來研究，其中有一類被稱為凱利圖的網路引起廣泛的注意和興趣。 對於連結網路來說，有一類重要的問題，是在某一個網路上模擬另外一個網路。這個問題稱為「嵌入網路」問題。在這當中，線性陣列和環是對於平行與分散式計算的連結網路來說，兩種最基本的網路。它們適合發展簡單而有效的演算法，並且同時只需花費相當低的通訊代價。線性陣列和環在實際層面上的廣泛運用給了我們在圖上做「嵌入路徑」和「嵌入圈」問題的動機。先前在「嵌入路徑」和「嵌入圈」問題上的研究多半聚焦於在圖上找出最長的路徑或最長的圈，另外有一類問題則聚焦於在圖上找出所有可能長度的圈。 在一個系統當中，處理器和它們彼此之間的鏈結都有可能發生錯誤，因此考慮一個連結網路的容錯能力是非常重要的。也就是說，連結網路在發生某些處理器錯誤或者鏈結錯誤時，這個網路仍能保有原先的性質。一般來說，有兩種考量連結網路容錯能力的模型：隨機錯誤(random fault)與條件錯誤(conditional fault)。若假設錯誤會毫無限制的隨機發生，就稱之為隨機錯誤。反之，若假設錯誤的發生會滿足某些條件，則稱之為條件錯誤。 在這本論文裡，我們研究在邊錯誤下的其中三類凱利圖上的無錯嵌入路徑、嵌入圈問題：星網絡(star graph)，交替群圖(alternating group graph)，與煎餅網絡(pancake graph)。我們證明了在隨機錯誤模型中，一個n維交替群圖在至多2n-6個鏈結損壞的情形下，仍然可以找到所有可能長度的環。以能容忍鏈結損壞的角度來看，這個結果是最佳的。另一方面，我們也在條件錯誤模型中討論了三個問題。假設每個節點至少和兩個健康的鏈結相連的情況下，我們證明了一個n維星網絡在至多2n-7個鏈結損壞的情形下，仍能在任意兩點之間找到最長的路徑；一個n維交替群圖在至多4n-13個鏈結損壞的情形下，仍然可以找到最長的環；一個n維煎餅網絡在至多2n-7個鏈結損壞的情形下，仍然可以找到最長的環。上述三個在條件錯誤模型的結果中，在星網絡與交替群圖的兩個結果，以能容忍鏈結損壞的角度來看，這兩個結果是最佳的。 最後，我們在條件錯誤模型中，針對這三個不同的圖另外找出三個小性質，做為對上述主要問題的補充與對照。此外，針對我們在條件錯誤模型中的假設（假設每個節點至少和兩個健康的鏈結相連），我們也透過計算機率的方式來說明該假設是有實質應用上的意義的。

Advances in technology, especially the advent of VLSI circuit technology, have made it possible to build a large parallel and distributed system involving thousands or even tens of thousands of processors. One crucial step on designing a large-scale parallel and distributed system is to determine the topology of the interconnection network (network for short). The network topology not only affects the hardware architecture but also the nature of the system software that can be used in a parallel and distributed system. A number of network topologies have been proposed. Among them, a class of graphs called Cayley graphs is of interest for the design and analysis of interconnection networks. For interconnection networks, the problem of simulating one network by another is modelled as a network embedding problem. Linear arrays and rings, which are two of the most fundamental interconnection networks for parallel and distributed computation, are suitable to develop simple and efficient algorithms with low communication costs. The wide applications of linear arrays and rings motivate us to investigate path and cycle embedding in networks. Some of previous researches on path or cycle embedding focused on finding longest paths or cycles (i.e., the Hamiltonian problem, in terms of graph theory). Some others focused on finding cycles of all possible lengths (i.e., the pancycle problem, in terms of graph theory). Since node faults and/or link faults may occur to networks, it is significant to consider faulty networks. Fault tolerance ability is an important consideration for interconnection network topology. That is, the network is still functional when some node faults and/or link faults occur. Among them, two fault models were adopted; one is the random fault model, and the other is the conditional fault model. The random fault model assumed that the faults might occur everywhere without any restriction, whereas the conditional fault model assumed that the distribution of faults must satisfy some properties. It is more difficult to solve problems under the conditional fault model than the random fault model. In this dissertation, we investigate fault-free path/cycle embedding problems with edge faults on three instances of Cayley graphs: star graphs, alternating group graphs, and pancake graphs. If the random fault model is adopted, we show that an n-dimensional alternating group graph is (2n−6)-edge-fault-tolerant pancyclic. This result is optimal with respect to the number of edge faults tolerated. On the other hand, under the conditional fault model and with the assumption of at least two non-faulty links incident to each node, we show that an n-dimensional star graph is (2n−7)-edge-fault-tolerant strongly Hamiltonian laceable and (n−4)-edge-fault-tolerant hyper Hamiltonian laceable, an n-dimensional alternating group graph is (4n−13)-edge-fault-tolerant Hamiltonian and (2n−7)-edge-fault-tolerant Hamiltonian connected, and an n-dimensional pancake graph is (2n−7)-edge-fault-tolerant Hamiltonian and (n−4)-edge-fault-tolerant Hamiltonian connected. The results on star graphs and alternating group graphs are optimal with respect to the number of edge faults tolerated. We also verify that the assumption is meaningful in practical by evaluating its probability of occurrence, which is very close to 1, even if n is small.