||Fault-tolerant Simulation of a Class of Regular Graphs in Hypercubes and Incrementally Extensible Hypercubes
||Department of Computer Science and Information Engineering
Incrementally Extensible Hypercube
IEH Fibonacci cube
||在大型平行計算機器中，超立方體結構圖(hypercube)是最為廣泛使用的。其結構上的正規性(regularity)可使得電腦系統能較容易地被建立起來，而平行演算法上的容錯性使得一般與網路拓蹼結構相關的平行演算法不須經過大幅修改就能容易地被移植到超立方體結構電腦系統上來執行。可逐步擴充超立方體(Incrementally Extensible Hypercube)是超立方體的變形結構，它可以有任意的節點個數，並且保證其直徑(diameter)為節點個數和的對數值，以及每一個節點的鏈結分支度(degree)相差最多為1。本論文中，我們討論將一些正規的網路拓蹼，例如，環路(ring)、網格(mesh)及樹(tree)，嵌入至有容錯能力的可逐步擴充超立方體結構的演算法。
||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.
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
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
 Akers, S. B. and Krishnamurthy, B., “A Group-Theoretic Model for Symmetric Interconnection Networks,” IEEE Trans. on Computers, Vol. 38, pp. 555-565, 1989.
 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.
 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.
 Bertsekas, D. P. and Tsitsiklis, J. N., Parallel and Distributed Computation: numerical methods, Prentice Hall, Englewood Ciffs, NJ, U.S.A., 1989.
 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.
 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.
 Chartand, C. and Oellermann, O. R., Applied and Algorithmic Graph Theory, McGRAW-HILL Inc., 1993.
 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.
 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.
 Efe, K., “Embedding large Complete Binary Trees in Hypercubes with load balancing,” J. Parallel and Distrib. Comput., Vol. 35, pp. 104-109, 1996.
 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.
 Hayes , J. P. and Mudge, T.N., “Hypercube supercomputing,” Proc. IEEE, Vol. 77, No. 12, pp. 1829-1842, 1989.
 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.
 Katseff, H.P., “Incomplete Hypercubes,” IEEE Trans. on Computers, Vol. 37, No. 5, pp. 604-608, 1988.
 Leighton, F. T., Introduction to parallel algorithms and architectures: Arrays, Trees, Hypercubes, MORGAN KAUFMANN PUBLISHERS, Inc., 1992.
 Jen-Chih Lin, “Simulation of Cycles in the IEH Graph,” International Journal of Hjgh Speed Computing, Vo1. 10, No. 3, pp. 327-342, 1999.
 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.
 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.
 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.
 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.
 Rennels, D. A., “On Implemanting Fault-tolerance in binary hypercubes,” Proc. 16th Inter . Symp. on Fault-tolerant Computing, pp. 344-349, 1986.
 Saad, Y. and Schultz, M., “Topological properties of Hypercube,” IEEE Trans. on Computers, Vol. 37, No. 7, pp. 867-871, 1988.
 Seitz, C., “The Cosmic Cube,” Commun. ACM, Vol. 28, pp. 22-33, 1985.
 Sen, A., “Supercube: An Optimally Fault Tolerant Network Architecture,” Acta Informatica, Vol. 26, pp. 741-748, 1989.
 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.
 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.
 Sur, S. and Srimani, P. K., “Incrementally Extensible Hypercube Networks and Their Fault Tolerance,” Mathematical and Computer Modelling, Vol. 23, pp. 1-15, 1996.
 Sur, S. and Srimani, P. K., “IEH graphs: A novel generalization of hypercube graphs,” Acta Informatica, Vol. 32, pp 597-609, 1995.
 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.
 Tucker, L. W. and Robertson, G. G., “Architecture and applications of the connection machine,” IEEE Trans. on Computer, Vol. 21, pp.26-38, 1988.
 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.
 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.
 Wittie, L.D., “Communications structures for largenetworks of microcomputers,” IEEE Trans. on Computers, Vol. 30, pp.264-273, 1981.
 Xu, C. and Lau, F. C. M., Load Balancing in Parallel Computers-Theory and Practice, Kluwer Academic Publishers, Inc., 1997.
 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.
 Yuan, S. M., “Topological properties of supercube,” Information Processing Letters, Vol. 37, pp. 241-245, 1991.
 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.
 Ralph P. Grimaldi, Discrete and Combinational Mathematics: An Applied Introduction, 4nd ed., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999.
 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.
 D.K. Pradhan, “Fault-tolerant Multiprocessor Link and Bus Network Architectures, “IEEE Trans. on Computer Vol. 34, pp.33-45, 1985.
 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.
 Bertsekas D. P. and Tsitsiklis J. N., Parallel and Distributed Computation: numerical methods, Prentice Hall, Englewood Ciffs, New Jersey, 1989.
 D. Lenoski, et al., “The StanfordDASH Multiprocessor, “Computer, Vol. 224, pp63-79, Feb. 1971.
 J. Kuskin, et al. “The Stanford FLASH Multiprocessor,” Proceedings of the 21st Annual International Symposium on Computer Architecture, pp.302~313, Chicago, Apr. 1994.
 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.
 Chui-Cheng Chen, “Dynamic Reconfiguration of Complete Binary Trees in Faulty Hypercubes”, Journal of Information Science and Engineering, Vol. 21, Num 1, Jan. 2005.
 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.
 C. Chartrand and O. R. Oellermann, Applied and Algorithmic Graph Theory, McGRAW-HILL Inc. 1993.
 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.
 J. Koolen, V. Moulton, and D. Stevanovic, “The structure of spherical graphs,” European Journal of Combinatorics, Vol. 25, pp. 213-227, 2004.
 D.E. Knuth, The Art of Computer Programming, Vol. 1, Fundamental Algorithms, 2nd ed. Reading, MA:Addison-Wesley, 1973.
 W.-J. Hsu and J.S. Liu, Fibonacci codes as formal language, Tech. Rep. CPS-91-04, Michigan State Unvi., May 1991.