臺灣博碩士論文加值系統

　　多電腦(Multicomputer)是一種平行電腦架構，它包含了許多計算節點(Compute Node)。多電腦系統的運作效能與訊息繞路的方法息息相關，繞路演算法的好壞決定了多電腦系統運作效率的高低。在多電腦系統中節點間的通訊行為區分成點對點(Point-to-Point)通訊與叢聚性(Collective)通訊兩種，而群播(Multicast)通訊被歸類於叢聚性通訊行為中。群播經常被使用在單一程式、複數資料的計算模式上，亦即不同處理器上處理相同的資料。在多電腦架構下，計算節點是透過內連結網路(Interconnection Network)互相連接，並搭配訊息繞路演算法進行節點間的通訊，而環繞網狀網路(Torus Network)是多種內連結網路之一，近年來廣泛地受到使用，如超級電腦藍色基因(BlueGene/L)。

　　在本論文中，我們提出了一個在蟲洞繞路(Wormhole-Routed)環繞網狀網路中有效率的群播通訊演算法。首先我們會介紹在環繞網狀網路中的漢米爾頓循環模型(Hamiltonian Cycle Model)，基於此模型，我們可以在環繞網狀網路中找到一條漢米爾頓循環，接著我們提出一個多路徑(Multi-Path)群播演算法。在特殊的情況下，環繞網狀網路中的訊息繞路會有死結(Deadlock)的發生，一旦死結發生，目的節點將無法收到任何由來源節點傳送的訊息。為了避免死結，在繞路演算法中加入了漢米爾頓循環與虛擬通道的概念，使得訊息在節點之間傳遞會依照特定的順序。我們使用標號函數(Labeling Function)為每個在環繞網狀網路上的節點制訂標號，制定完成的標號順序即為漢米爾頓循環。訊息傳遞前，來源節點必須決定目的節點的個數與標號，接著使用訊息準備演算法將所有目的節點區分成四個目的節點子集合，並且將四個目的節點子集合分別放置在對應的訊息表頭當中。四個訊息的其中兩個經由高通道網路傳送，另外兩個經由低通道網路傳送。多路徑群播演算法使用四條漢米爾頓路徑(Hamiltonian Path)來做資料的傳遞，平均的使用兩個子網路(Subnetwork)來降低訊息傳送的路徑長度，相較於只使用兩條漢米爾頓路徑的繞路演算法，多路徑群播演算法提高了在環繞網狀網路中群播通訊的效率。最後我們將透過模擬實驗分析來證實所提方法確實優於先前所提出的繞路演算法。

　　Multicomputer is one of the parallel computer architectures. It contains ensembles of computational nodes. The performance of multicomputer system is highly dependent the efficiency of the message routing scheme. Communication operations for parallel and distributed computing can classified as either point-to-point or collective. Multicast is a collective communication operations. The multicast is useful in the single-program, multiple-data mode of computation, in which the same program is executed on different processors with different data. In multicomputer architecture, compute nodes to connect with each other using interconnection networks. Furthermore, an efficient message routing algorithm is to operate in cooperation for communication between compute nodes. The torus network is one of several interconnection networks. It is more popular in recent years, e.g. supercomputer BlueGene/L.

　　In this thesis, we propose an efficient multicast communication in wormhole-routed torus networks. We first introduce a hamiltonian cycle model for exploiting the feature of the torus network. Based on this model, we find a hamiltonian cycle in torus networks. Then, we propose an efficient multicast routing algorithm, multi-path multicast routing algorithm, in torus networks with wormhole routing. The message is routed in torus networks which lead to deadlock situation in special case. When deadlock occur, destination node will not receive any message from source node. For deadlock avoidance, the multi-path routing algorithm using concept of hamiltonian cycle and virtual channels. Let the message routed between two nodes according particular sequence. We use labeling function to set the label on each node in torus networks. After labeling procedure, the label sequence is hamiltonian cycle. Before message transmitting, the source node must be decision how many destination nodes will delivered and that labels. Message preparation algorithm divide all destination nodes into four message headers. Then, we put these message headers to the four corresponding messages. Two messages are routed along high-channel networks, and two messages are routed along low-channel networks. This algorithm uses four hamiltonian paths for data transmission. The proposed multicast routing algorithm utilize two subnetwork channels uniformly in order to reduce the path length of the messages. To compare with fixed multicast routing algorithm, multi-path multicast routing algorithm making the multicasting more efficient in the torus network. Finally, experimental results show that the proposed routing algorithm outperform the previous scheme.

Chapter 1 Introduction 1
1.1 Multicomputer Systems 1
1.2 Multicast Operation 3
1.3 Wormhole Routing 4
1.4 Thesis Organization 7
Chapter 2 Related Work 8
2.1 Multipath Multicast Routing 8
2.2 Md-Torus Multicast Algorithm 9
2.3 Uniform Multicast Routing Algorithm 10
2.4 Fixed Multicast Routing Algorithm 11
Chapter 3 System Model 14
3.1 Hamiltonian Cycle 14
3.2 Channel Networks 16
3.3 All-Port Model 18
Chapter 4 Multi-Path Multicast Routing Algorithm 20
4.1 Routing Function 20
4.2 Message Preparation Algorithm 23
4.3 Operation Procedures 28
Chapter 5 Performance Evaluations 30
5.1 Simulation Model 30
5.2 Results Analysis 31
Chapter 6 Conclusions and Future Work 39
6.1 Conclusions 39
6.2 Future Work 40
Appendix A 41
References 44

[1]E. Anderson, J. Brooks, C. Grassl, and S. Scott, “Performance of the Cray T3E Multiprocessor,” Proceedings of the 1997 ACM/IEEE Conference on Supercomputing, pp. 1-17, November 1997.

[2]T.-S. Chen, C.-Y. Chang, and J.-P. Sheu, “Efficient Multicast Communication in Multidestination Wormhole-Routed Mesh Networks,” Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications, Vol. 2, pp. 674-681, July 1998.

[3]T.-S. Chen, N.-C. Wang, and C.-P. Chu, “Multicast Communication in Wormhole-Routed Star Graph Interconnection Networks,” Parallel computing, pp. Vol. 26, No. 11, pp. 1459-1490, October 2000.

[4]W. J. Dally and C. L. Seitz, “The Torus Routing Chip,” Journal of Distributed Computing, Vol. 1, No. 3, pp. 187-196, October 1986.

[5]G. E. Fagg, S. S. Vadhiyar, and J. J. Dongarra, “Automatic Collective Communications Tuning,” Recent Advances in Parallel Virtual Machine and Message Passing Interface, No. 1908, pp. 354-361, September 2000.

[6]E. Fleury and P. Fraigniaud, “Strategies for Path-Based Multicasting in Wormhole-Routed Meshes,” Journal of Parallel and Distributed Computing, Vol. 53, pp. 26-62, August 1998.

[7]A. Gara, A. Blumrich, D. Chen, G. L.-T. Chiu, P. Coteus, M. E. Glampaga, R. A. Haring, P. Heidelberger, D. Hoenicke, G. V. Kopcsay, T. A. Liebsch, M. Ohmacht, B. D. SteinmacherBurow, T. Takken, and P. Vranas, “Overview of the Blue Gene/L System Architecture,” IBM Journal of Research and Development, Vol. 49, No. 2/3, pp. 195-212, April 2005.

[8]L. V. Kale, S. Kumar, and K. Vardarajan, “A Framework for Collective Personalized Communication,” Proceedings of the 17th International Parallel and Distributed Processing Symposium, pp. 69(a), April 2003.

[9]R. E. Kessler and J. L. Schwarzmeier, “CRAY T3D: A New Dimension for Cray Research,” Proceedings of the 38th IEEE Computer Society International Conference, pp. 176-182, February 1993.

[10]F. Harary, Graph Theory. Reading, MA: Addison-Wesley, 1972.

[11]C.-T. Ho and M. Kao, “Optimal broadcast on hypercubes with wormhole and e-cube routings,” Proceedings of the 1993 International Conference on Parallel and Distributed Systems, pp. 694-697, December 1993.

[12]R. Libeskind-Hadas, K. Watkins, and T. Hehre, “Fault-tolerant Multicast Routing in the Mesh with No Virtual Channels,” Proceedings of the 2nd International Symposium on High-Performance Computer Architecture, pp. 180-190, February 1996.

[13]X. Lin, P. K. McKinley, and L. M. Ni, “Deadlock-Free Multicast Wormhole Routing in 2D Mesh Multicomputers,” IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 8, pp. 793-804, October 1994.

[14]X. Lin and L. M. Ni, “Deadlock-Free Multicast Wormhole Routing in Multicomputer Network,” Proceedings of the 18th Annual International Symposium on Computer Architecture, pp. 116-125, May 1991.

[15]X. Lin and L. M. Ni, “Multicast Communication in Multicomputers Networks,” Proceedings of the 1990 International Conference on Parallel Processing, Vol. 3, pp. 114-118, August 1990.

[16]T. Marescaux, A. Bartic, D. Verkest, S. Vernalde, and R. Lauwereins, "Interconnection Networks Enable Fine-Grain Dynamic Multi-Tasking on FPGAs," The 12th Conference on Field-Programmable Logic and Applications, pp. 795-805, September 2002.

[17]P. K. McKinley, H. Xu, A.-H. Esfahanian, and L. M. Ni, “Unicast-Based Multicast Communication in Wormhole-Routed Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 5, Issue 12, pp. 1252-1265, December 1994.

[18]L. M. Ni and P. K. McKinley, “A Survey of Wormhole Routing Techniques in Direct Networks,” IEEE Computer, Vol. 26, No. 2, pp. 62-76, February 1993.

[19]M. Noakes and W. J. Dally, “System Design of the J-machine,” Proceedings of the 6th MIT conference on Advanced research in VLSI, pp. 179-194, April 1990.

[20]D. K. Panda, S. Singal, and P. Prabhakaran, "Multidestination Message Passing Mechanism Conforming to Base Wormhole Routing Scheme," Proceedings of the Parallel Computer Routing and Communication Workshop, No. 853, pp. 131-145, May 1994.

[21]R. Rabenseifner and G. Wellein, "Communication and Optimization Aspects of Parallel Programming Models on Hybrid Architectures," International Journal of High-Performance Computing Applications, Vol. 17, No. 1, pp. 49-62, Spring 2003.

[22]D. F. Robinson, P. K. McKinley, and B. H. C. Cheng, “Path-Based Multicast Communication in Wormhole-routed Unidirectional Torus Networks,” Journal of Parallel and Distributed Computing, Vol. 45, No. 2, pp. 104-121, September 1997.

[23]L. Schwiebert, “There is No Optimal Routing Policy for the Torus,” Information Processing Letters, Vol. 83, Issue 6, pp. 331-336, September 2002.

[24]R. Thakur, W. Gropp, and B. Toonen, “Optimizing the Synchronization Operations in MPI One-Sized Communication,” International Journal of High-Performance Computing Applications, Vol. 19, No. 2, pp. 119-128, Summer 2005.

[25]Y.-C. Tseng, D. K. Panda, and T.-H. Lai, “A Trip-Based Multicasting Model for Wormhole-Routed Networks with Virtual Channels,” IEEE Transactions on Parallel and Distributed Systems, Vol. 7, No. 2, pp. 138-150, February 1996.

[26]Y.-C. Tseng, M.-H. Yang, and T.-Y. Juang, “Achieving Fault-Tolerant Multicast in Injured Wormhole-Routed Tori and Meshes Based on Euler Path Construction,” IEEE Transactions on Computers, Vol. 49, No. 3, pp. 1282-1296, March 2000.

[27]N.-C. Wang, C.-P. Yen, and C.-P. Chu, “Multicast Communication in Wormhole-routed Symmetric Networks with Hamiltonian Cycle Model,” Journal of System Architecture, Vol. 51, No. 3, pp. 165-183, March 2005.