Abstract
Scalability of interconnection networks for supercomputers, particularly for next-generation exascale systems with tens of millions of cores, is essential for performance. One required property is the minimum-diameter-based scalable (MDBs) network, which combines small diameter, high connectivity, symmetry, and regularity. The diameter of an MDBs network grows linearly while the size increases exponentially. We designed a vertex-balanced routing algorithm for the base network to manage data transit pressure. Benchmarks on a small-scale cluster and simulations show significant performance improvements, demonstrating that balanced transit loading in base topologies translates to the larger MDBs generated from them.
Introduction
As high-performance computing moves toward the exascale era ($10^{18}$ calculations per second), the primary bottleneck shifts from raw processing power to network efficiency. Traditional topologies like hypercubes and fat-trees struggle with scalability and load imbalance. Even with shortest-path routing, certain nodes often become "hotspots," leading to congestion and reduced throughput. This research addresses these challenges by proposing a family of nested topologies coupled with a load-balanced routing strategy.
Nested Network Topologies
The proposed architecture utilizes the Cartesian product of graphs to construct large-scale networks from smaller, optimal base graphs. By nesting graphs like the Peterson or Heawood graphs—which possess the smallest possible diameter for their order—researchers can create massive networks where the total node count ($N$) grows exponentially while the diameter ($D$) remains low and grows only linearly.
This mathematical approach ensures that the desirable properties of the base graphs, such as symmetry and regularity, are preserved in the larger structure.
Scalability and Performance
A critical advantage of these nested networks is their superior scalability compared to standard topologies like hypercubes. As shown in the comparative analysis of diameter versus network size, nested networks maintain a significantly lower diameter as the number of nodes increases.
This low diameter is crucial for minimizing latency in large-scale systems. The linear growth of the diameter against the exponential growth of nodes allows for efficient communication even in systems with millions of cores.
Load-Balanced Routing Strategy
To prevent node congestion, the authors developed a two-stage routing optimization:
- Path Enumeration: All possible shortest paths between every pair of nodes are identified.
- MINLP Optimization: A Mixed-Integer Nonlinear Programming (MINLP) model selects specific paths to minimize the variance of the "forwarding load" across all nodes.
A key theoretical finding is that balancing the load for the small base graphs automatically ensures balance in the resulting large nested network. This allows for deterministic routing that achieves high throughput without the packet-reordering overhead associated with adaptive routing.
Experimental Results
The methodology was validated using the Taishan physical cluster (32 nodes) and SimGrid simulations for larger configurations. Key benchmarks included Graph500, MPI All-to-all, and NAS Parallel Benchmarks (NPB) FT.
- Throughput: Graph500 results showed a 12% to 17% increase in Millions of Traversed Edges Per Second (MTEPS).
- Latency: MPI All-to-all messaging time was reduced by nearly 50% for small packets.
- Computational Efficiency: The NPB FT benchmark saw a 48% improvement in operations per second (from 41.3 to 61.4 Mops/s) solely through routing optimization.
Conclusion
The combination of nested topologies and load-balanced routing provides a robust framework for exascale interconnection networks. By optimizing at the base-graph level, researchers can achieve high-performance, scalable communication across massive systems. Future work will focus on introducing fault tolerance to these static routing tables and addressing the computational complexity of MINLP for larger base configurations.
Summary updated