在大型平行計算機器中，超立方體結構圖(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.

Contents	                                                IV
List of Figures	                                        V
Chapter 1 Introduction	                               1
1.1 Motivations	                                        1
1.2 Outline of the Dissertation	                      7
Chapter 2 Related works and preliminaries	             8
2.1 Definitions and notations	                      8
2.2 Hypercubes	                                       10
2.3 Incremental Extensible Hypercube	                     14
2.4 Rings and linear arrays	                              18
2.5 Mesh	                                                26
2.6 Trees	                                                27
2.7 Fibonacci cube	                                       42
Chapter 3 Embedding applications of IEH graphs	  45
3.1 Embedding of rings and linear arrays	            45
3.2 Embedding of mesh	                              49
3.3 Embedding of complete binary tree	            52
Chapter 4 Fault-tolerant embedding applications of IEH graphs	                                                54
4.1 Ring can be embedded into faulty IEH graph	  54
4.2 Mesh can be embedded into faulty IEH graph	  69
4.3 Complete binary tree can be embedded into faulty IEH graph	                                                80
Chapter 5 Fibonacci cube can be embedded into faulty hypercube	                                                90
Chapter 6 Conclusions and future works	            97
6.1 Conclusions	                                       97
6.2 Future works	                                       98
Bibliography	                                      100
Appendix A. Publication List	                    106
List of Figures
Figure  1: Examples of hypercubes with dimension 1,2, and 3.	12
Figure  2: The IEH graph contains 14 nodes	17
Figure  3: The Hamiltonian cycle of G3(10)	25
Figure  4: 22x22  2-dimensional mesh	26
Figure  5:  3-dimensional mesh	27
Figure  6: A double-rooted complete binary tree contains 2d node.	29
Figure  7: The process of the transformation (1)	29
Figure  8: The process of the transformation (2)	29
Figure  9: The process of the transformation (3)	30
Figure  10: A double-rooted complete binary tree with 2d+1 nodes	30
Figure  11: A double-rooted with 4 nodes can be embedded into a 2-cube	31
Figure  12: The transformation of mapping (1)	31
Figure  13: The transformation of mapping (2)	32
Figure  14: The transformation of mapping (3)	32
Figure  15: A double-rooted tree with 8 nodes can be embedded into a 3-cube	32
Figure  16: A complete binary tree T3 can be embedded into F2	37
Figure  17: T4 is embedded into F3	39
Figure  18: T5 is embedded into F4	40
Figure  19: Fibonacci cube	43
Figure  20:  can be embedded into H4	44
Figure  21: A ring with 9 nodes can be embedded into an IEH with 12 nodes	49
Figure  22: 2-dimensional BRGC for an 22×21 mesh	50
Figure  23: 22×21 mesh can be embedded into G3(13) with 2-expansion	52
Figure  24: Three steps of T3 embedding to G3(11)	53
Figure  25: R8 can be embedded into a H3 of F8 (case1)	57
Figure  26: R8 can be embedded into a H3 of F8 (case2)	58
Figure  27: R6 can be embedded into a H3 of G3(11) with dilation 1	65
Figure  28: R5 can be embedded into a H3 of G3(11) with dilation 1	66
Figure  29: R5 can be embedded into a H3 of G3(12) with dilation 2	66
Figure  30: 4 2 mesh (with 8 nodes) can be embedded into faulty G3(15) with 2-expansion.	72
Figure  31: 21×21 mesh can be embedded into G3(13)	74
Figure  32: 21×21 mesh can be embedded into faulty G3(15)	78
Figure  33: T3 can be embedded into faulty G3(11)	82
Figure  34: T2 can be embedded into faulty G3(15)	88
Figure  35:   be embedded into faulty H4	94

Bibliography
[1]	Akers, S. B. and Krishnamurthy, B., “A Group-Theoretic Model for Symmetric Interconnection Networks,” IEEE Trans. on Computers, Vol. 38, pp. 555-565, 1989.
[2]	Armstrong, J. R. and Gray, F. G., “Fault Diagnosis in a Boolean n Cube Array of Microprocessors,” IEEE Trans. on Computers, Vol. 30, No. 8, pp. 587-590, 1981.
[3]	Auletta, V., Rescigno, A. A., and Scarano, V., “Embedding Graphs onto the Supercube,” IEEE Trans. on Computers, Vol. 44, No. 4, pp. 593-597, 1995.
[4]	Bertsekas, D. P. and Tsitsiklis, J. N., Parallel and Distributed Computation: numerical methods, Prentice Hall, Englewood Ciffs, NJ, U.S.A., 1989.
[5]	Bhatt, S.N., Chung, F., Leighton, F.T. and Rosenberg, A., “Optimal Simulations of Tree Machines,” Proc. 27th Annu. Symp. Foundations Comput. Sci., pp. 274-282, 1986.
[6]	Bhuyan, L. and Agrawal, D.P., “Generalized Hypercubes and Hyperbus structure for a computer network,” IEEE Trans. on Computers, Vol. 33, pp. 323-333, 1984.
[7]	Chartand, C. and Oellermann, O. R., Applied and Algorithmic Graph Theory, McGRAW-HILL Inc., 1993.
[8]	Day, K. and Al-Ayyoub, A. E., “Fault Diameter of k-ary n-cube Networks,” IEEE Trans. on parallel and distributed systems, Vol. 8, No. 9, pp. 903-907, 1997.
[9]	Dutt, S. and Hayes, J. P., “An automorphic approach to the design of fault-tolerance Multiprocessor,” Proc. of 19th Inter. Symp. on Fault-Tolerant Computing, Chicago, IL, Jun., pp. 496-503, 1989. 
[10]	Efe, K., “Embedding large Complete Binary Trees in Hypercubes with load balancing,” J. Parallel and Distrib. Comput., Vol. 35, pp. 104-109, 1996.
[11]	Hameenanttila, T., Guan, X. L., Carothers, J. D. and Chen, J. X., “The Flexible Hypercube: A New Fault-Tolerant Architecture for Parallel Computing,” J. Parallel and Distrib. Comput., Vol. 37, pp. 213-220, 1996.
[12]	Hayes , J. P. and Mudge, T.N., “Hypercube supercomputing,” Proc. IEEE, Vol. 77, No. 12, pp. 1829-1842, 1989.
[13]	Hastad, J., Leighton, T., and Newman, M., “Reconfiguring a Hypercube in the Presence of Faults,” Proc. of 19th ACM Conf. on Theory of Computing, pp. 274-284, 1987.
[14]	Katseff, H.P., “Incomplete Hypercubes,” IEEE Trans. on Computers, Vol. 37, No. 5, pp. 604-608, 1988.
[15]	Leighton, F. T., Introduction to parallel algorithms and architectures: Arrays, Trees, Hypercubes, MORGAN KAUFMANN PUBLISHERS, Inc., 1992.
[16]	Jen-Chih Lin, “Simulation of Cycles in the IEH Graph,” International Journal of Hjgh Speed Computing, Vo1. 10, No. 3, pp. 327-342, 1999. 
[17]	Lin, J. C. and Keh, H. C, “Reconfiguration of Complete Binary Trees in Full IEH Graphs and Faulty Hypercubes,” International Journal of High performance computing Applications, Vo1. 15, No. 1, pp.55-63, 2001.
[18]	Lin, J. C and Hsien, N. C., “Reconfiguring Binary Tree Structures in a Faulty Supercube with Unbounded Expansion,” Parallel Computing, Vo1. 8, No. 32, pp. 471-483, 2002.
[19]	Lin, J. C and Lo, S. K.C., “Embedding Complete Binary Trees into Faulty Flexible Hypercubes with Unbounded Expansion” Informatica, Vol. 27, No. 1, pp.75-80, 2003.
[20]	Preparata, F. P. and Vuillemin, J., “The cube-connected cycles: A versatile network for parallel computation,” Commun. ACM, Vol. 24, No. 5, pp. 300-309, 1981.
[21]	Rennels, D. A., “On Implemanting Fault-tolerance in binary hypercubes,” Proc. 16th Inter . Symp. on Fault-tolerant Computing, pp. 344-349, 1986.
[22]	Saad, Y. and Schultz, M., “Topological properties of Hypercube,” IEEE Trans. on Computers, Vol. 37, No. 7, pp. 867-871, 1988.
[23]	Seitz, C., “The Cosmic Cube,” Commun. ACM, Vol. 28, pp. 22-33, 1985.
[24]	Sen, A., “Supercube: An Optimally Fault Tolerant Network Architecture,” Acta Informatica, Vol. 26, pp. 741-748, 1989.
[25]	Sen, A., Sengupta, A. and Bandyopadhyay, S., “Generalized Supercube: An incrementally expandable interconnection network,” Proc. of 3rd Symp. on Frontiers of Massively Parallel Computation-Frontiers'90, pp. 384-387, 1990.
[26]	Sullivan, H. and Bashkow, T., “A large scale, homogeneous, fully distributed parallel machine, I,” Proc. of 4th Symp. Computer Architecture, ACM, pp. 105-177, 1977. 
[27]	Sur, S. and Srimani, P. K., “Incrementally Extensible Hypercube Networks and Their Fault Tolerance,” Mathematical and Computer Modelling, Vol. 23, pp. 1-15, 1996.
[28]	Sur, S. and Srimani, P. K., “IEH graphs: A novel generalization of hypercube graphs,” Acta Informatica, Vol. 32, pp 597-609, 1995.
[29]	Tseng, Y.C. and Lai, T.H., “On the Embedding of a class of Regular Graphs in a Faulty Hypercube,” J. Parallel and Distrib. Comput., Vol. 37, pp. 200-206, 1996.
[30]	Tucker, L. W. and Robertson, G. G., “Architecture and applications of the connection machine,” IEEE Trans. on Computer, Vol. 21, pp.26-38, 1988.
[31]	Tzeng, N. F. and Chen, H. L., “An Effective Approach to the Enhancement of Incomplete Hypercube Computers,” J. Parallel and Distrib. Comput., Vol. 14, pp. 163-174, 1992.
[32]	Tzeng, N. F. and Chen, H. L., “Fast Compaction in Hypercubes,” IEEE Trans. on parallel and distributed systems, Vol. 9, No. 1, pp. 50-55, 1998.
[33]	Wittie, L.D., “Communications structures for largenetworks of microcomputers,” IEEE Trans. on Computers, Vol. 30, pp.264-273, 1981.
[34]	Xu, C. and Lau, F. C. M., Load Balancing in Parallel Computers-Theory and Practice, Kluwer Academic Publishers, Inc., 1997.
[35]	Yang, P. J., Tien, S. B. and Raghavendra, C.S., “Embedding of Rings and Meshes onto Faulty Hypercube Using Free Dimensions,” IEEE Trans. on Computers, Vol. 43, No. 5 , pp. 608-618, 1994.
[36]	Yuan, S. M., “Topological properties of supercube,” Information Processing Letters, Vol. 37, pp. 241-245, 1991. 
[37]	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.
[38]	Ralph P. Grimaldi, Discrete and Combinational Mathematics: An Applied Introduction, 4nd ed., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999.
[39]	Thuy Trong Le and Tri Cao Huu, “Advances in Parallel Computing for the Year 2000 and Beyond,” Proceedings of Vacets Technical International Conference(VTIC97), San Jose State University, Jul. 1997.
[40]	D.K. Pradhan, “Fault-tolerant Multiprocessor Link and Bus Network Architectures, “IEEE Trans. on Computer Vol. 34, pp.33-45, 1985.
[41]	Huan-Chao Keh, Po-Yu Chou and Jen-Chih Lin, “Finding Hamiiltonian Cycles on Incrementally Extensible Hypercube Graphs,” Proceedings of HPC Asia ’97 Conference and Exhibition (IEEE), 361-366, 1997.
[42]	Bertsekas D. P. and Tsitsiklis J. N., Parallel and Distributed Computation: numerical methods, Prentice Hall, Englewood Ciffs, New Jersey, 1989.
[43]	D. Lenoski, et al., “The StanfordDASH Multiprocessor, “Computer, Vol. 224, pp63-79, Feb. 1971.
[44]	J. Kuskin, et al. “The Stanford FLASH Multiprocessor,” Proceedings of the 21st Annual International Symposium on Computer Architecture, pp.302~313, Chicago, Apr. 1994.
[45]	A. Agrawal, et al., “The MIT Alewife Machine: Architecture and Performance,” Proceedings of the 22nd Annual International Symposium on Computer Architecture, Santa Margherita Ligure, pp. 2-13, Italy, Jun. 1995.
[46]	Chui-Cheng Chen, “Dynamic Reconfiguration of Complete Binary Trees in Faulty Hypercubes”, Journal of Information Science and Engineering, Vol. 21, Num 1, Jan. 2005.
[47]	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.
[48]	C. Chartrand and O. R. Oellermann, Applied and Algorithmic Graph Theory, McGRAW-HILL Inc. 1993.
[49]	F.J. Provost, R. Melhem, “A distributed algorithm for embedding trees in hypercubes with modifications for run-time fault-tolerance,” J. Parallel Distrib. Comput., Vol. 14, pp. 85-89, 1992.
[50]	J. Koolen, V. Moulton, and D. Stevanovic, “The structure of spherical graphs,” European Journal of Combinatorics, Vol. 25, pp. 213-227, 2004.
[51]	D.E. Knuth, The Art of Computer Programming, Vol. 1, Fundamental Algorithms, 2nd ed. Reading, MA:Addison-Wesley, 1973.
[52]	W.-J. Hsu and J.S. Liu, Fibonacci codes as formal language, Tech. Rep. CPS-91-04, Michigan State Unvi., May 1991.