淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1907200715035800
中文論文名稱 映射對稱圖至超立方體衍生圖之錯誤避免法
英文論文名稱 Fault-Avoiding Methods for Mapping Symmetric Graphs on the Hypercube Derivatives
校院名稱 淡江大學
系所名稱(中) 資訊工程學系博士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 95
學期 2
出版年 96
研究生中文姓名 藍冠麟
研究生英文姓名 Kuan-Lin Lan
學號 891190109
學位類別 博士
語文別 英文
口試日期 2007-06-07
論文頁數 83頁
口試委員 指導教授-葛煥昭
委員-莊淇銘
委員-蔣定安
委員-施國琛
委員-王亦凡
委員-葛煥昭
中文關鍵字 超立方體  漢米爾頓路徑  漢米爾頓迴路  環路  網格  完全二元樹  費伯納茲立方體 
英文關鍵字 Hypercube  Hamiltonian path  Hamiltonian cycle  Ring  Mesh  Complete Binary Tree  Fibonacci cube 
學科別分類 學科別應用科學資訊工程
中文摘要 在平行計算機器上,嵌入法是一項很重要的應用。在每一項平行的應用中,具有其個別的傳輸架構。這一些傳輸架構,可被映射成為多處理器架構下的拓撲,因此與其相符合的應用將可被執行。本篇論文在具有故障節點的超立方體圖或超立方體衍生圖中,提出一項新的正規圖形階層演算法,包括漢米爾頓路徑(Hamiltonian path),漢米爾頓迴路(Hamiltonian cycle),環路(ring),網格(mesh),完全二元樹(complete binary tree),以及費伯納茲立方體(Fibonacci cube)。
首先,在具有故障的節點圖中,找出一個可取代故障節點的點,當n個故障節點出現時,容錯可達擴張度2,延展度3,壅塞度1及負載度1。此外,這種方法也可擴展至超立方體或超立方體衍生圖中。不同於許多目前所見的演算法只能嵌入單一類型的圖,這種演算法以一致的方法嵌入到上述的圖型中。藉由這個結果,我們可以輕鬆的將平行演算法發展到超立方體或超立方體衍生圖的正規圖型架構。此一嵌入的方法非常適合使用於高速的平行電腦中。
英文摘要 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.
論文目次 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
參考文獻 Bibliography
[1] B. Aiello and T. Leighton, “Coding theory, hypercube embedding, and fault tolerance,”in Proc. 3rd Ann. ACM Symp. Parallel Algorithms Arch., 1991.
[2] P. Banerjee, “Strategies for reconfiguring hypercube under faults,”in Proc. 20th Int. Symp. Foult-Tolerant Comput., 1990.
[3] D. P. Bertsekas and J. N. Tsitsiklis,“Parallel and Distributed Computation: numerical methods,”Prentice Hall, Englewood Ciffs, New Jersey, 1989.
[4] J. Bruck, R. Cypher, and D. Soroker, “Running algorithms efficiently on faulty hypercubes,”Comput. Arch. News, Vol. 19, No. 1, pp. 89-96, 1991.
[5] S. Dutt, and J.P. Hayes,“An automorphic approach to the design of fault-tolerance Multiprocessor,”in Proceedings of the 19th International Symposium on Fault-Tolerant Computing,1989.
[6] J. Hastad, T. Leighton, and M. Newman,Reconfiguring a Hypercube in the Presence of Faults,” ACM Theory of Computing, pp. 274-284, 1987.
[7] C.-T. Ho, M.T. Raghunath, and S. Lennart Johnsson, “An Efficient Algorithm for Gray-to-Binary Permutation on Hypercubes,” Journal of Parallel and Distributed Computing, Vol. 20, pp.114-120, 1994.
[8] Huan-Chao Keh and Jen-Chih Lin,“On Fault-Tolerant Embedding of Hamiltonian Cycles, Linear Arrays and Rings in a Flexible Hypercube,”Parallel Computing, Vol. 26, No. 6, pp. 769-781, 2000.
[9] F. T. Leighton, Introduction to parallel algorithms and architectures: Arrays, Trees, Hypercubes, MORGAN KAUFMANN PUBLISHERS, Inc., 1992.
[10] Jen-Chih Lin and Huan-Chao Keh,“Reconfiguration of Complete Binary Trees in Full IEH Graphs and Faulty Hypercubes,” International Journal of High Performance Computing Applications, Vol.15, No.1, pp.55-63, 2001.
[11] Jen-Chih Lin, “Simulation of Cycles in the IEH Graph,” International Journal of High Speed Computing, Vol. 10, No. 3, pp. 327-342, 1999.
[12] Jen-Chih Lin and Nan-Chen Hsien“Reconfiguring Binary Tree Structures in a Faulty Supercube with Unbounded Expansion,” Parallel Computing, Vol. 28, No. 3, pp.471-483, 2002.
[13] Jen-Chih Lin and Steven K.-C. Lo,“Embedding Complete Binary Trees into Faulty Flexible Hypercubes with Unbounded Expansion,” Informatica, No. 27, pp. 75-80, 2003.
[14] Y. Saad, and M. Schultz,“Topological properties of Hypercube,” IEEE Trans. on Computers, Vol. 37, No. 7, pp. 867-871, July 1988.
[15] C. Seitz, “The Cosmic Cube,”Commun. ACM, Vol. 28, pp. 22-33, 1985.
[16] S. B. Tien, C. S. Raghavendra, and M. A. Sridhar. “Reconfiguration embedded task graphs in faulty hypercubes by automorphisms,” in Proc. Hawaii Int. Conf.Syst. Sci., 1990, pp. 91-100.
[17] Bhuyan, L. N., and Agrawal, D. P., “Generalized Hypercube and Hypercube Structure for a Computer Network,” IEEE Trans. on Computers, Vol. 33, 1984, pp.323-333.
[18] D.A. Rennels, “On implemainting fault-tolerance in binary hypercube,” in Proceedings of the 16th Internation Symposium on Fault-tolerant Computing, 1985, pp.344-349.
[19] Hayes, J. P., Mudge, T., and Stour, Q. F., “A Microprocessor-based Hypercube Super-computer,”IEEE Micro, 1986, pp. 6-17.
[20] Hills, W. D., The Connection Machine. MIT Press, 1985.
[21] Jen-Chih Lin, Tzong-Heng Chi, Huan-Chao Keh and Ay-Hwa Andy Liou, “Embedding of Complete Binary Tree with 2-expansion in a Faulty Flexible Hypercube,” Journal of Systems Architecture, Vol. 47, No. 6, 2001, pp.543-548.
[22] Jen-Chih Lin, “Embedding Hamiltonian Cycles, Linear Arrays and Rings in a Faulty Supercube,”International Journal of High Speed Computing, Vol. 11, No. 3, 2000, pp. 189-201.
[23] Jen-Chih Lin“Simulation of a Class of Regular Graphs in Faulty Hypercube-Derived Computers,”WSEAS Transactions on Circuits and Systems, Vol. 5, 2006, pp.530-535.
[24] Jen-Chih Lin, “Load Balancing and Embedding Rings in Faulty Incrementally Extensible Hypercubes, WSEAS Transactions on Computers, Vol. 5, 2006, pp.1867-1872.
[25] NCUBE Corp. NCUBE 6400 Processor Manual. 1990.
[26] F.J. Provost, and R. Melhem, “A distributed algorithm for embedding trees in hypercubes with modifications for run-time fault-tolerance,” J. Parallel Distrib. Comput., Vol. 14, 1992, pp. 85-89.
[27] Wen-Jing Hsu, “Fibonacci Cubes-A New Interconnection Topology,” IEEE Trans. Parallel and Distributed Systems, Vol.4, No.1, 1993, pp. 3-12.
[28] W.-J. Hsu, and J.S. Liu, Fibonacci codes as formal language, Tech. Rep. CPS-91-04, Michigan State Unvi., May 1991.
[29] Bhatt, S. N., Chung, F. R. K., Leighton, F. T., and Rosenberg, A. L. Efficient embeddings of trees in hypercubes. SIAM J. Comput. 21, 1992, pp.151-162
[30] C. Chartrand and O. R. Oellermann, Applied and Algorithmic Graph Theory, McGRAW-HILL Inc. 1993.
[31] R. Hen, Another cycle structure theorem for Hamiltonian graphs, Discrete Math. 1999, pp.237-243
[32] M. Sohel Rahman, and M. Kaykobad “On Hamiltonian cycles and Hamiltonian paths” information Processing Letters, Volume 94, Issue 1, 15 April 2005, pp.37-41
[33] D.B. West, Introduction to Graph Theory, Prentice-Hall, Englewood Cliffs, NJ, 2001
[34] Wu, A. Embedding of tree networks into hypercubes. J.Parallel Distribut. Comput. 2, 1985. pp238-249
[35] Akers, S. B. and Krishnamurthy, B., “A Group-Theoretic Model for Symmetric Interconnection Networks,” IEEE Trans. on Computers, Vol. 38, pp. 555-565, 1989.
[36] Hayes , J. P. and Mudge, T.N., “Hypercube supercomputing,” Proc. IEEE, Vol. 77, No. 12, pp. 1829-1842, 1989.
[37] C. Chartrand and O. R. Oellermann, Applied and Algorithmic Graph Theory, McGRAW-HILL Inc. 1993.
[38] Shih-Chang Wang, Yuh-Rong Leu, Sy-Yen Kuo, “Distributed Fault-Tolerant Embedding of Several Topologies in Hypercubes.” Journal of Information Science and Engineering, Vol. 20, Num 4, Jul. 2004.
[39] Chui-Cheng Chen, “Dynamic Reconfiguration of Complete Binary Trees in Faulty Hypercubes”, Journal of Information Science and Engineering, Vol. 21, Num 1, Jan. 2005.
[40] T. Hameenanttila, X-L. Guan, J. D. Carothers and J.-X. Chen, “The Flexible Hypercube: A New Fault-Tolerant Architecture for Parallel Computing,” J. Parallel and Distrib. Comput., Vol. 37, pp. 213-220, 1996.
[41] F. Harary, J.P. Hayes, and H.J. Wu, “A survey of the theory of hypercube graphs”, Computers and Math. with Applications, 1988.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-07-26公開。
  • 同意授權瀏覽/列印電子全文服務,於2012-07-26起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信