臺灣博碩士論文加值系統

連結網路的效能對於所有被連結的計算節點整合起來之協同運算能力影響甚鉅，而網路架構、網路拓樸以及訊息繞徑演算法則是決定連結網路效能的三大要素。InfiniBand是一種新的工業標準網路架構，InfiniBand架構具有高頻寬以及高速度、低延遲等優點，因此可以用來作為很好的高速連結網路架構。此外，fat-tree拓樸所具備的許多良好特性使得它常常成為建構連結網路時所使用的網路拓樸。本論文主要研究的目標即是以InfiniBand網路架構以及fat-tree拓樸建構連結網路，並且依據InfiniBand以及fat-tree各自的特性，對於兩者結合所構成之連結網路設計一合適且有效率的通訊方法。此通訊方法包含了運算節點的位址指定，InfiniBand網路交換器的轉送表產生以及訊息溝通時的訊息遞送法。模擬的實驗結果顯示出我們所設計出來的通訊方法在InfiniBand與fat-tree結合的網路中運作良好，能在InfiniBand架構下有效地利用fat-tree網路拓樸所提供的通訊頻寬。

Performance of the interconnection network greatly affects the computation power generated together from all interconnected processing nodes. Network architecture, interconnection topology, and routing algorithm are three key elements dominating the performance of interconnection networks. InfiniBand is a new industry standard architecture; it defines a high-bandwidth, high-speed, and low-latency message switching network that is good for constructing high-speed interconnection networks. Besides, Fat-trees are well-adopted as the topology of interconnection networks because of many nice properties they have. The main objective of this thesis is to design a message communication scheme for interconnection networks constructed under the combination of InfiniBand and fat-tree. The proposed communication scheme is composed of processing node addressing, forwarding table generation and message delivery scheme. The simulation results show that the proposed scheme runs well on constructed interconnection networks and is able to effectively utilize the bandwidth that fat-tree topology offer under InfiniBand architecture.

中文摘要 i
Abstract ii
Table of Contents iii
List of Figures v
List of Tables vii
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Thesis Organization 2
Chapter 2 Background and Related Work 3
2.1 InfiniBand Architecture 3
2.2 Fat-Tree Topology 4
2.2.1 Routing on Fat-Trees 5
Chapter 3 Fat-Tree Construction 6
3.1 k-ary n-trees 6
3.2 m-port n-trees 7
Chapter 4 Communication Scheme 10
4.1 Routing in InfiniBand 10
4.2 Channel Congestion Problem 12
4.3 Endnode Addressing 13
4.4 Forwarding Table Generation 14
4.4 Message Delivery Scheme Based on Multiple LID 15
Chapter 5 Performance Evaluation 16
Chapter 6 Conclusions and Future Work 26
References 27
誌謝 28
Vita 29

[1] C. E. Leiserson, “Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing,” IEEE Transactions on Computers, vol. 34, no.10, October 1985, pp. 892-901.
[2] F. Petrini and M. Vanneschi, “k-ary n-trees: High Performance Networks for Massively Parallel Architectures,” in Proceedings of the 11th International Parallel Processing Symposium, IPPS’97, April 1997, pp. 87-93.
[3] InfiniBand. Trade Association, InfiniBand. Architecture Specification Volume 1, Release 1.1, November 2002.
[4] InfiniBand. Trade Association, http://www.infinibandta.com.
[5] C. E. Leiserson et al., “The Network Architecture of the Connection Machine CM-5,” in Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1992, pp. 272-285.
[6] H. L. Muller, P. W. A. Stallard, and D. H. D. Warren, “An evaluation Study of a Link-Based Data Diffusion Machine,” in Proceedings of the 98th International Parallel Processing Symposium, IPPS’94, (Cancun, Mexico), April 1994, pp.115-128.
[7] Meiko World Incorporated, Computing Surface 2 reference manuals, preliminary edition, 1993.
[8] C. E. Leiserson and B.M. Maggs, “Communication-Efficient Parallel Algorithms for Distributed Random Access Machines,” Algorithmica, vol. 3, 1988, pp.53-77.