[[alternative]]映射對稱圖至超立方體衍生圖之錯誤避免法

博士[[abstract]]在平行計算機器上，嵌入法是一項很重要的應用。在每一項平行的應用中，具有其個別的傳輸架構。這一些傳輸架構，可被映射成為多處理器架構下的拓撲，因此與其相符合的應用將可被執行。本篇論文在具有故障節點的超立方體圖或超立方體衍生圖中，提出一項新的正規圖形階層演算法，包括漢米爾頓路徑(Hamiltonian path)，漢米爾頓迴路(Hamiltonian cycle)，環路(ring)，網格(mesh)，完全二元樹(complete binary tree)，以及費伯納茲立方體(Fibonacci cube)。 首先，在具有故障的節點圖中，找出一個可取代故障節點的點，當n個故障節點出現時，容錯可達擴張度2，延展度3，壅塞度1及負載度1。此外，這種方法也可擴展至超立方體或超立方體衍生圖中。不同於許多目前所見的演算法只能嵌入單一類型的圖，這種演算法以一致的方法嵌入到上述的圖型中。藉由這個結果，我們可以輕鬆的將平行演算法發展到超立方體或超立方體衍生圖的正規圖型架構。此一嵌入的方法非常適合使用於高速的平行電腦中。[[abstract]]Embedding is of great importance in the applications of parallel computing. Every parallel application has its intrinsic communication pattern. The communication pattern graph is mapped into the topology of multiprocessor structures so that the corresponding application can be executed. This thesis proposes a novel algorithm for emulation a class of regular graphs in the faulty hypercube or hypercube derivatives, including the Hamiltonian path, the Hamiltonian cycle, the linear array, the ring, the mesh, the complete binary tree, and the Fibonacci cube. First, to obtain the replaceable node of the faulty node, n faults can be tolerated with expansion 2, dilation 3, congestion 1, and load 1. Furthermore, our method is also extending the distributed fault-tolerant emulation of a class of regular graphs in hypercube or hypercube derivatives. Unlike many existing algorithms which are capable of embedding only type of graphs, our algorithm embeds the above graphs in a unified way. By the results, we can easily port the parallel algorithms developed for the structure of a class of regular graphs to hypercube or hypercube derivatives. This methodology of embedding enables extremely high-speed parallel computation.[[tableofcontents]]1 Introduction 1 1.1 Motivations 1 1.2 Outline of the Dissertation 6 2 Related works and preliminaries 7 2.1 Definitions and notations 7 2.2 Hypercubes 9 2.3 Rings and linear arrays 13 2.4 Mesh 16 2.5 Trees 18 2.6 Fibonacci cube 21 3 Embedding applications of Hypercube 23 3.1 Embedding of rings and linear arrays 23 3.2 Embedding of mesh 25 3.3 Embedding of complete binary tree 26 3.4 Embedding of Fibonacci cube 33 4 Fault-Avoiding Methods for Mapping Symmetric Graphs on a Faulty Hypercube Derivative 34 4.1 Embedding Rings on a Faulty Hypercube Derivative 34 4.2 Embedding Meshes on a Faulty Hypercube Derivative 40 4.3 Embedding Complete binary trees on a Faulty Hypercube Derivative 43 4.4 Embedding the Fibonacci cube on the Faulty Hypercube 46 5 Conclusions and Future Works 54 5.1 Conclusions 54 5.2 Future works 55 Bibliography 56 Appendix A."Fault Tolerant Emulation of a Class of Regular Graphs in Hypercubes" WSEAS TRANSATIONS ON SYSTEMS 61 Appendix B. "Embedding the Fibonacci Cube into the Faulty Hypercube" WSEAS TRANSACTIONS ON COMPUTERS 72 List of Figures Figure 2.1 One-dimensional cube 9 Figure 2.2 Two-dimensional cube 9 Figure 2.3 Three-dimensional cube 10 Figure 2.4 The Four-dimensional hypercube with 16 nodes 10 Figure 2.5 An example of Ring topology 13 Figure 2.6 An example of linear arrays topology 13 Figure 2.7 A 3-bits ring of length 8 14 Figure 2.8 A Hamiltonian cycle on the hypercube 14 Figure 2.9 mesh network 16 Figure 2.10 Example of 2-dimensional mesh 17 Figure 2.11 Example of d-dimensional mesh 17 Figure 2.12 An example of the tree 18 Figure 2.13 An example of the complete binary tree 18 Figure 2.14 Emulation DTh in H3 20 Figure 2.15 Fibonacci cube 22 Figure 3.1 The transformation of double-rooted complete binary tree 26 Figure 3.2 A double-rooted complete binary tree contains 2d node 27 Figure 3.3 The process of the transformation(1) 27 Figure 3.4 The process of the transformation(2) 28 Figure 3.5 The process of the transformation(3) 28 Figure 3.6 A double-rooted complete binary tree with 2d+1 nodes 29 Figure 3.7 A double-rooted complete binary tree with 4 nodes can be embedded on a hypercube with 4 nodes 30 Figure 3.8 The transformation of mapping(1) 30 Figure 3.9 The transformation of mapping(2) 30 Figure 3.10 The transformation of mapping(3) 31 Figure 3.11 A double-rooted complete binary tree with 8 nodes 31 Figure 3.12 A double-rooted complete binary tree with 8 nodes can be embedded on a hypercube with 8 nodes 31 Figure 3.13 can be embedded to 33 Figure 4.1 The searching sequence of the replaceable node of the faulty node 36 Figure 4.2 Fault-tolerant emulation of a class of regular graph in a hypercube 45 Figure 4.3 can be embedded on faulty 52[[note]]學號: 891190109, 學年度: 9