Contents

• Contents
• List of Figures
• List of Tables
• 1. Introduction
  • 1.1 Commodity Supercomputing
  • 1.2 Thesis Statement and Contributions
  • 1.3 Organization of the Thesis
• 2. Communication Model
  • 2.1 Introduction
  • 2.2 Commodity Cluster - Another Message Passing Machine
    • 2.2.1 Architectural Model
    • 2.2.2 Data Transfers
    • 2.2.3 The Communication Model
    • 2.2.4 Simple Examples
  • 2.3 Related Models
  • 2.4 Summary
• 3. Performance Signatures
  • 3.1 Directed Point
  • 3.2 The Performance of DP
    • 3.2.1 Latency with Performance Breakdowns
    • 3.2.2 Uni-directional Bandwidth
    • 3.2.3 Bi-directional Bandwidth
  • 3.3 Summary
• 4. Congestive Loss on High-Speed Communication
  • 4.1 Reliability
  • 4.2 Reliable Transmission Protocol for Low-Latency Communication System
    • 4.2.1 Our Go-Back-N ARQ Protocol Definitions
  • 4.3 Congestion Loss under the Many-To-One Data Flow
    • 4.3.1 Many-To-One Data Flow
    • 4.3.2 Congestion Behavior on Input-Buffered Architecture
    • 4.3.3 Congestion Behavior on Output-Buffered Architecture
    • 4.3.4 Discussion of the Models and Their Implications
  • 4.4 Related Work
  • 4.5 Summary
• 5. Complete Exchange on Non-Blocking Network
  • 5.1 Complete Exchange
  • 5.2 Non-Blocking Switch
  • 5.3 Complete Exchange Algorithms
    • 5.3.1 Shift Exchange
    • 5.3.2 Generalized Pairwise Exchange
    • 5.3.3 Synchronous Shuffle Exchange
    • 5.3.4 Group Shuffle Exchange
  • 5.4 Experimental Results
    • 5.4.1 Complete Exchange Performance
    • 5.4.2 Effects on Group Size $\omega$
    • 5.4.3 Scalability on Problem Size k
    • 5.4.4 Comparing Switching Mechanisms
    • 5.4.5 Comparison with MPICH
  • 5.5 Summary
• 6. Complete Exchange on Hierarchical Network
  • 6.1 Hierarchical Network
    • 6.1.1 System Model
  • 6.2 Modified Synchronous Shuffle Exchange
    • 6.2.1 Global Window Congestion Control
    • 6.2.2 Contention-Aware Permutation
  • 6.3 Experimental Analyses
    • 6.3.1 16-Node Single Switch - 16X1
    • 6.3.2 16-Node Hierarchical Configuration - 8X2
    • 6.3.3 24-Node Hierarchical Configurations - 8X3 and 6X4
    • 6.3.4 32-Node Hierarchical Configuration - 8X4
  • 6.4 Related Work
  • 6.5 Summary
• 7. Conclusions and Direction for Future Works
  • 7.1 Contributions
  • 7.2 Future Directions
• A. Benchmark Methodologies
  • A.1 Microbenchmark for the $B_{L}$ Parameter
  • A.2 Microbenchmark for the $O_{r}$ Parameter
  • A.3 Microbenchmark for the $g_{r}$ Parameter
  • A.4 Microbenchmark for the $O_{s}$ and $g_{s}$ Parameters
  • A.5 Microbenchmark for the $L$ parameter
• Bibliography