network topology high-performance

**HPC Network Topologies** define **the interconnection structure of compute nodes and switches, directly impacting scalability, bandwidth, latency, and cost of supercomputing systems at various scales.** **Fat-Tree (Clos Network) Architecture** - **Hierarchical Structure**: Multiple levels of switches creating tree topology. Level 0 (edge switches) connect hosts; higher levels connect to spine/core. - **Bandwidth Conservation**: Bandwidth at each level maintained constant. If k hosts per edge switch, then k links upward to next level. No bandwidth bottleneck across levels. - **Oversubscription**: Common in enterprise networks (8:1 oversubscription = 8 hosts per 1 uplink). HPC typically 1:1 or 2:1 (low oversubscription, expensive). - **Radix and Scalability**: Edge switch radix determines max hosts directly connected. Radix-48 switches: 48 downlinks (hosts) + 48 uplinks (spine). Typical HPC fat-tree: 10,000+ nodes. **Dragonfly Topology** - **Hierarchical Groups**: Local group (ring of ~64 hosts, connected to local spine), global spine (full mesh or high-radix connections between groups). - **Advantages**: Lower radix switches (48 typical vs 256+ for fat-tree). Lower switch cost for large systems. Reduced hop count for non-local traffic (2 hops vs 4-5 in fat-tree). - **Disadvantages**: All-to-all pattern congests global spine (bottleneck). More complex routing/load balancing required. - **Scalability**: Suitable for 10,000-100,000 node systems. Fat-tree more scalable for <10,000; Dragonfly preferred for larger systems. **3D Torus (Blue Gene, Fugaku)** - **3D Mesh Topology**: Nodes arranged in 3D grid (x, y, z dimensions). Each node connected to 6 neighbors (±x, ±y, ±z). Wrap-around edges = torus (reduced diameter). - **Bandwidth Characteristics**: Bisection bandwidth = (number of nodes in 3D grid) × (link bandwidth per direction). Diagonal cuts minimal. - **Latency**: Diameter (max hops) = ⌈(max_dimension) / 2⌉. For 256×256×256 torus, diameter = 128 hops. Fat-tree typically 4-6 hops. - **Routing**: Dimension-ordered routing (DOR) deadlock-free but may not use all bandwidth. Adaptive routing improves utilization but adds complexity. **Butterfly and Other Topologies** - **Butterfly Network**: Log(N)-level structure. Each level expands nodes into 2N branches, then reduces. Optimal for specific packet routing algorithms. - **Hyper Cube**: Logarithmic degree (# connections per node = log N). Efficient for certain algorithms, rarely deployed in modern HPC. - **Fat-Tree vs Torus Trade-off**: Fat-tree high switch cost, excellent latency. Torus low switch cost, higher latency. Dragonfly balance between both. **All-to-All Communication Patterns** - **Collective Pattern**: Every node sends to every other node (alltoall). Total data volume: N(N-1) per node (N nodes total → N²(N-1) edge transits). - **Network Saturation**: Alltoall saturates network regardless of topology (fundamental information requirement). Execution time proportional to message size × N. - **Routing**: Single-path routing creates congestion at shared links. Multi-path routing (adaptive) spreads load, improves performance. - **MPI_Alltoall Implementation**: Recursive doubling, direct send, bruck's algorithm. Algorithm selection depends on message size and network topology. **Bisection Bandwidth Concept** - **Definition**: Minimum bandwidth across any cut dividing network in half. Bisection = network cut achieving minimum bandwidth. - **Fat-Tree Bisection**: Equal to (number of nodes / 2) × (link bandwidth per direction). Fat-tree designed for uniform bisection across all possible cuts. - **Torus Bisection**: Planar cuts minimize bandwidth (fewer edges). Diagonal cuts may have higher bandwidth. Bisection varies depending on cut orientation. - **Bisection for Scaling**: Higher bisection supports larger all-to-all operations. Bisection ~100 Gbps per 1000 nodes typical for current HPC systems. **Topology-Aware Process Mapping** - **Process Placement**: MPI ranks assigned to compute nodes considering topology. Goal: minimize inter-switch traffic, maximize intra-switch local bandwidth. - **Graph Partitioning**: Treat process communication graph as undirected graph. Partition minimizing edge cuts (inter-switch traffic). Heuristic algorithms (multilevel KL, Scotch). - **Recursive Bisection**: Recursively partition process graph and map to topology hierarchy. Excellent for balanced process graphs. - **Benefits**: 10-20% performance improvement from topology-aware mapping vs random (measured on large HPC systems). **Collective Algorithm Selection** - **Topology-Dependent**: Allreduce implemented via tree (fat-tree), ring (torus), or hybrid. Different topologies favor different algorithms. - **Automatic Selection**: Modern MPI libraries (Open MPI, MPICH) profile network topology, select best algorithm per operation/message size. - **Performance Variation**: Ring allreduce on fat-tree 2-3x slower than tree (uses non-optimal paths). Topology awareness crucial.