Optimal Routing for a Family of Scalable Interconnection Networks.

Zhipeng Xu, Xiaolong Huang, Yuefan Deng

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.

Construction of a nested network via the Cartesian product of two base graphs.

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.

Diameter (D) vs. Network Size (N) showing the scalability of nested networks compared to hypercubes.

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:

  1. Path Enumeration: All possible shortest paths between every pair of nodes are identified.
  2. 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

Abstract

Scalability of interconnection networks for the supercomputers, particularly, for next-generation exascale systems with tens of millions of cores, is one of the essential features for enhancement of performance. One of the required properties of the scalable and low-radix for interconnection networks is the minimum-diameter-based scalable (MDBs) network. The MDBs network combines the desired features of some optimal topologies with different orders, such as small diameter, high connectivity, symmetry, and regularity. The diameter of the MDBs network grows up linearly while the size of the network measured in nodes increases exponentially. We designed the vertex-balanced routing algorithm for the base network by considering the pressure of the data transit in each node. The benchmarks on a real small-scale cluster show amazing improvements in performance after adapting the new routing algorithm. Each node of MDBs generated from base topologies can also sustain balanced transit loading if we apply the optimized routing algorithm to the base network. The simulation results show that our algorithm can substantially enhance communication performance for MDBs.
BibTeX
@misc{xu2019optimal,
  author = {Zhipeng Xu and Xiaolong Huang and Yuefan Deng},
  title = {{Optimal Routing for a Family of Scalable Interconnection Networks.}},
  year = {2019},
  eprint = {1909.06497},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.06497},
}
Figure