臺灣博碩士論文加值系統

在大型平行計算中，其負責溝通與協同運作的通訊網路是否能夠支持眾多負責主要計算工作的處理器單元來完成任務是一件很重要的事情。其中尤以超立方體網路具有許多良好的特性而成為首選，但是它有一個缺點，那就是節點個數必須滿足2的乘冪。因此其他許多的拓撲變形嘗試來彌補此缺憾。我們首先建立一個簡單的分類架構，將超立方體衍生網路根據不同的非對稱程度分為六種型態，根據我們的分類架構，可以清楚知道這些變形幾乎都屬於型IV的非對稱族，該族有兩大主要特色：可能具有比較短的路徑與不受限制的節點數目等特性；比較短的路徑表示可能存在優於原始超立方體的路由演算法，並進而影響處理器單元間的協同運算效率，不受限制的節點數目可以看作是另一種形式的節點故障。所以在本篇論文中，我們探討此非對稱特性所導致的不可旋轉性對於通訊能力與計算模型的影響。
在通訊能力方面；我們則根據最接近投影點與高維優先的策略提出了在可逐步擴增超立方體的群播演算法，並證明該法比現有的方法都來得適用於可逐步擴增的超立方體衍生網路。在計算能力方面；我們採用了圖形嵌入法的觀點，分別以位元順序法與表格項目刪除法，提出了如何在節點發生故障的情形底下將完全二元樹嵌入到彈性超立方體的演算法，並達到延展度4，壅塞度1，擴張度2與負載1的結果，可以容忍的節點錯誤數目為O(n)。

In Massive Parallel Processing, many processor elements (PE''s) are together responsible for the calculation work. The communication network bridges all of PE''s to cooperate or coordinate each other. In other words, the whole effect mainly depends on the communication network whether it can make the PE''s work as they should do. Hypercube has been one of the most popular topologies because of its connectivity, regularity, and symmetry. But it has a weakness that is the node number must be power of two. Therefore many other hypercube-derived variants developed to make up this deficiency. We first propose a simple classification scheme to divide those variants into six types according to the degree of asymmetry. Hence we have found that almost all of the variants are members of type VI variant which is asymmetric. This type has two main characteristics: existence of shortcuts and unrestricted number of nodes. The shortcut means the possible existence of better routing algorithms then that developed for the Hypercube. They can then affect the efficiency. The difference between the node number and power of 2 can be regarded as another form in processor elements to break down. So in this thesis, we exploit these properties and investigate the influence which comes from the asymmetry on the communication and computation.
In the aspects of communication, we propose a multipurpose heuristic distributed multicasting algorithm customized for the Incrementally Extensible Hypercube. The algorithm follows the rules of (1) the closest image node routing and (2) the subcubes of higher dimension with higher priority. It is proven that the algorithm is better than others designed for the hypercubes. In the aspects of computation model, we propose algorithms for mapping complete binary trees into Flexible Hypercube separately by the two approaches: (1) bit ordering and (2) table lookup and item deletion. It holds dilation 4, congestion 1, expansion 2 and load 1 under the risk of O(n) faults.

Chinese Abstract i
English Abstract ii
Chapter 1 Introduction 1
1.1 Research Motivation 1
1.2 Outline of the Thesis 9
Chapter 2 Preliminaries 12
2.1 Definitions and Notations 12
2.2 Hypercube-derived Graphs 15
2.2.1 The Hypercube Graph 15
2.2.2 The Supercube Graph 18
2.2.3 The Flexible Hypercube Graph 20
2.2.4 The Incremental Extensible Hypercube Graph 23
2.3 Embedding Complete Binary Trees 29
Chapter 3 A Simple Classification of Hypercube-Derived Graphs 38
3.1 From Graphs to Groups 39
3.2 Toward a Classification 43
Chapter 4 Embedding Complete Binary Trees into Faulty Flexible Hypercubes 49
4.1 The Big-Endian Algorithm 51
4.1.1 Examples for the Big-Endian Algorithm 53
4.2 The Small Ball Algorithm 54
4.2.1 Examples for the Small Ball Algorithm 58
4.3 The Correctness of Algorithms 67
Chapter 5 Multicast in Incrementally Extensible Hypercube (IEH) Graphs 72
5.1 The Multicast Algorithm in the IEH Graphs 73
5.2 An Illustrative Example 78
5.3 The Correctness of MULTICAST_IN_IEH 82
Chapter 6 Conclusions and the Future Work 87
6.1 Conclusions 87
6.2 The Future Work 89
Bibliography 90

[1] Leon Aronson, "A Theory of Routing in Parallel Computers; From concept to analysis," Ph.D. Thesis, Advanced School for Computing and Imaging, Delft University of Technology, The Netherlands, 1999.
[2] László Babai, Automorphism groups, isomorphism, reconstruction, Chapter 27 in Handbook of Combinatorics, R. L. Graham, M. Grötschel, and L. Lovász, eds., Vol. 2, Elsevier (North-Holland), Amsterdam, Vol. 2, pp. 1447-1540, 1995.
[3] Subrata Banerjee, Vivek Jain, and Sanjay Shah, "Regular Multihop Logical Topologies for Lightwave Networks," IEEE Communications Surveys, Vol. 2, no. 1, 1st quarter, pp. 2-18, 1999.
[4] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: numerical methods, Prentice Hall, Englewood Cliffs, New Jersey, 1989.
[5] L. N. Bhuyan and D. P. Agrawal, "Generalized Hypercube and Hypercube Structure for a Computer Networks," IEEE Trans. Comput., Vol. C-33, pp. 323-333, 1984.
[6] Norman Biggs, Algebraic Graph Theory, 2nd ed., Cambridge University Press, 1996.
[7] C. Chartrand and O. R. Oellermann, Applied and Algorithmic Graph Theory, McGRAW-HILL Inc., 1993.
[8] V. Chaudhary and J. K. Aggarwal, "Generalized Mapping of Parallel Algorithms onto Parallel Architectures," Proc. International Con. on Parallel Processing, pp. 137-141, 1990.
[9] Hsin-Chou Chi and Wen-Jen Wu, "Routing Tree Construction for Interconnection Networks with Irregular Topologies," Proceedings of the Eleventh Euromicro Conference on Parallel, Distributed and Network-Based Processing, 157-164, 2003.
[10] Ralph Duncan, "A Survey of Parallel Computer Architectures," IEEE Computer, Vol. 23, No. 2, pp. 5-16, February 1990.
[11] S. Dutt, and J. P. Hayes, "An automorphism approach to the design of fault-tolerance Multiprocessor," Proc. 19th International Symp. on Fault-Tolerant Computing, 1989.
[12] Paul Erdös and Alfréd Rényi, "Asymmetric graphs," Acta mathematica Hungarica, 14, pp. 295-315, 1963.
[13] Michael J. Flynn, "Some Computer Organization and their Effectiveness," IEEE Ttransactions on Computers, Vol. c-21, No. 9, pp. 948-960, Septemper 1972.
[14] J. Folkman, "Regular Line-Symmetric Graphs." Journal of Combinatorial Theory, Vol. 3, 215-232, 1967.
[15] Chris Godsil, Gordon Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer-Verlag, New York, NY 2001.
[16] Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 2nd ed., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989.
[17] 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 Distributed Computing, Vol. 37, pp. 213-220, 1996.
[18] Frank Harary, John P. Hayes, and Horng-Jyh Wu. A survey of the theory of hypercube graphs. Computer Math. Applications, Vol. 15, No. 4, pp. 277-289, 1988.
[19] D. A. Holton and J. Sheehan, The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.
[20] J. Jastad, T. Leighton, and M. Newman, "Reconfiguring a Hypercube in the Presence of Faults," ACM Theory of Computing, pp. 274-284, 1987.
[21] S.L. Johnsson and Ching-Tieh Ho, "Optimum Broadcasting and Personalized Communication in Hypercube," IEEE Transaction on Computer, Vol. 38, No. 9, 1249-l268, 1989.
[22] H. P. Katseff, "Incomplete Hypercube," IEEE Trans. Comput., Vol. C-37, pp. 604-607, 1988.
[23] H.-C. Keh, P.-Y. Chou and J.-C. Lin, "Embedding Rings onto the Incrementally Extensible Hypercube Graphs," Proc. of the IASTED International Conf. on Modeling, Simulation and Optimization, 1996.
[24] H.-C. Keh, P.-Y. Chou and T.-H. Chi, "Multicast in Incrementally Extensible Hypercube(IEH) Graph," Proc. of International Conf. on Parallel and Distributed Processing Techniques and Applications, PDPTA ’96, 1996.
[25] Huan-Chao Keh, Po-Yu Chou and Jeh-Chih Lin, "Finding Hamiltonian Cycles on Incrementally Extensible Hypercube Graphs," Proceedings of HPC Asia ’97 Conference and Exhibition (IEEE), 361-366, 1997.
[26] Jong-Seok Kim, Eunseuk Oh, Hyeong-Ok Lee, and Yeong-Nam Heo, " Topological and Communication Aspects of Hyper-Star Graphs", Proc. The 18th International Symposium on Computer and Information Sciences (ISCIS ''03), Lecture Notes in Computer Science (LNCS), 2869, Springer-Verlag, pp. 51-58, 2003.
[27] J. Koolen, V. Moulton, and D. Stevanovic, "The structure of spherical graphs," European Journal of Combinatorics, 25, 213-227, 2004.
[28] D. W. Krumme, K. N. Venkatavaman, and G. Crbenko, "Hypercube Embedding is NP-Complete, " in proceedings of the First Conference on Hypercube Multiprocessors, Knoxville, Tennessee, pp. 148- 157, 1985.
[29] Y. Lan, Abdol-Hossein Esfahanian, and Lionel M. Ni, "Multicast in Hypercube Multiprocessors," Journal of Parallel and Distributed Computing, Vol. 8, 30-41, 1990.
[30] 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, July 1997.
[31] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, MORGAN KAUFMANN PUBLISHERS Inc., 1992.
[32] Jen-Chih Lin, "Simulation of Cycles in the IEH Graph," International Journal of High Speed Computing, Vol. 10, No. 3, 327-342, 1999.
[33] 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, 55-63, 2001.
[34] X. Lin and Linel M. Ni, "Multicast Communication in Multicomputer Networks," IEEE Transactions on Parallel and Distributed Systems, Vol. 4, No. 10, 1105-1117, 1993.
[35] K. J. Liszka, J. K. Antonio, and H. J. Siegel, "Problems with comparing interconnection networks: Is an alligator better than an armadillo?," IEEE Concurrency, Vol. 5, No. 4, Oct.-Dec. 1997, pp. 18-28.
[36] J.S. Liu and W.J. Hsu, "Distributed Algorithms for Shortest-path, Deadlock-free Routing and Broadcasting in Fibonacci Cubes," Proceedings of Intemational Phoenix Conference on Computers and Communication (IEEE), 23-30, 1992.
[37] Dragan Marušiè, Primož Potoènik. Semisymmetry of generalized Folkman graphs," European Journal of Combinatorics, Vol. 22, pp. 333-349, 2001.
[38] D.K. Pradhan, "Fault-tolerant Multiprocessor Link and Bus Network Architectures," IEEE Transaction on Computer, Vol. C-34, 33-45, 1985.
[39] F. J. Provost and R. Melhem, "A Distributed Algorithm for Embedding Trees in Hypercubes with Modifications for Run-Time Fault Tolerance," J. Parallel Distributed Computing, Vol. 14, pp. 85-89, 1992.
[40] Darcy Quesnel, "Hypercube-Like Topologies", available at http://www.scs.carleton.ca/~dquesnel/papers/topologies/paper.html, 1994
[41] D. A. Rennels, "On implementing Fault-tolerance in binary hypercubes," Proc. 16th International Symp on Fault-tolerant Computing, pp. 344- 349, 1986.
[42] Y. Saad and M. H. Schultz, "Topological Properties of Hypercube," IEEE Trans. Comput., Vol. 37, No. 7, pp. 867-872, 1988.
[43] Thomas J. Sager and Bruce M. McMillin, "A Fast O(k) Multicast Message Routing Algorithm," The 3rd Symposium on the Frontier of Massively Parallel Computation, 372-375, 1990.
[44] Barton J. Sano and Alvin M. Despain, "The 16-fold way: a microparallel taxonomy," Proceedings of the 26th annual international symposium on Microarchitecture, Austin, Texas, United States, pp. 60 - 69, 1993.
[45] C. Seitz, "The Cosmic Cube," Communication of the ACM, Vol. 28, 23-33, 1985.
[46] A. Sen, "Supercube: An Optimally Fault Tolerant Network Architecture," Acta Informatica, Vol. 26, pp. 741-748, 1989.
[47] A. Sen, A. Sengupta and S Bandyopadhyay, "Generalized Supercube: An incrementally expandable interconnection network," Proc. of the Third Symp. on Frontiers of Massively Parallel Computation Frontiers’90, pp. 384-387, 1990.
[48] Jang-Ping Sheu and Ming-Yang Su, "A Multicast Algorithm for Hypercube Multiprocessors," Proceedings of International Conference on Parallel Processing, III-18-III-22, 1992.
[49] Silicon Graphics Inc. "Hypercube Connectivity within ccNUMA Architecture", available at www.sgi.com/products/remarketed/origin/pdf/hypercube.pdf, 1998.
[50] Aad J. van der Steen and Jack J. Dongarra, "Overview of Recent Supercomputers", available at http://www.phys.uu.nl/~steen/web03/overview.html, 2003.
[51] Lewis Benjamin Stiller, "Exploiting symmetry on parallel architectures," Ph.D. Thesis, Department of Computer Science, The Johns Hopkins University, USA, 1995.
[52] S. Sur and P. K. Srimani,"IEH graphs: A novel generalization of hypercube graphs," Acta informatica, Volume 32, pp 597-609, 1995.
[53] S. Sur and P. K. Srimani, "Incrementally Extensible Hypercube Networks and Their Fault Tolerance," Mathematical and Computer Modeling, Vol. 23, pp. 1-15, 1996.
[54] S. B. Tien, C. S. Raghavendra, and M. A. Sridhar, "Generalized Hypercubes and Hyperbus structure for a computer network" Hawaii International Conf. on System Science, pp. 91-100, 1990.
[55] Jie Wu and Kaojun Yao, "Multicasting in Injured Hypercubes Using Limited Global Information," Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing, 548-555, 1993.