Symmetry-guided design of topologies for supercomputer networks

Alan U. Sabino, Miguel F. S. Vasconcelos, Yuefan Deng, Alexandre F. Ramos

TL;DR

This paper proposes a novel method for designing supercomputer network topologies by leveraging the mathematical framework of symplectic algebras. This approach generates graphs with optimized properties like minimal diameter and average path length, offering a more efficient alternative to current mesh and hypercube designs.

What Problem Does This Paper Address?

Supercomputers are constantly growing in size and complexity, demanding increasingly efficient ways to connect their numerous processing units. The "topology" of these connections – how nodes are linked – is crucial for communication speed and overall performance. Current popular topologies like meshes and hypercubes, while effective, have limitations. As the number of nodes increases, their diameter (the longest shortest path between any two nodes) and average path length can become bottlenecks. This paper addresses the need for new, systematically designed topologies that can overcome these limitations, offering better scalability and performance for future exascale computing.

Methods

The core of this paper's approach lies in using group theory, specifically the Cartan classification of Lie algebras, to design network topologies. The authors establish a correspondence between:

  • Supercomputers and Graphs: Nodes in the network become vertices, and connections become edges.
  • Graph Theory and Group Theory:
  • Graph vertices are represented by weight vectors of a Lie algebra's irreducible representation.
  • Graph edges are represented by root vectors of the Lie algebra.

They focus on symplectic algebras (sp(2n, C)) and their anti-symmetric irreducible representations. By constructing graphs from the roots and weights lattices of these representations, they generate new network topologies. The paper details how to map these mathematical structures to graph vertices and edges, and then derives formulas for adjacency matrices and distances within these new "symplectic topologies."

Datasets

Not discussed in the paper. The paper focuses on theoretical design and mathematical construction rather than empirical evaluation on existing datasets.

Key Insights and Ideas

  • Group Theory as a Design Tool: The paper demonstrates that abstract mathematical structures like Lie algebras can provide a powerful and systematic way to design practical network topologies.
  • Symplectic Algebras Offer Advantages: The use of symplectic algebras, particularly their anti-symmetric representations, leads to graphs with desirable properties for supercomputing networks.
  • Optimized Path Lengths: Symplectic topologies consistently show shorter average path lengths compared to hypercubes and meshes for a similar number of nodes or diameter.
  • Higher Node Density: For a given diameter, symplectic topologies can accommodate a significantly larger number of nodes, leading to better network density.
  • Unified Framework: The approach unifies the representation of existing topologies (mesh, hypercube) and the generation of new ones within a single theoretical framework.

Key Results

  • Construction of Symplectic Topologies: The paper provides a method to construct graphs based on the roots and weights lattices of symplectic algebras.
  • Comparison with Existing Topologies:
    • Symplectic graphs exhibit shorter average path lengths than hypercubes and meshes. For example, a symplectic graph with ~4.8 million vertices and diameter 20 has an average path length of 8, while a hypercubic graph with ~1 million vertices and diameter 20 has an average path length of 11.
  • Symplectic topologies can achieve higher node densities for a given diameter, meaning they can connect more nodes within the same "volume" or network constraints.
  • Mathematical Characterization: Formulas for adjacency matrices and distance calculations are derived for these new topologies.

Limitations and Future Work

  • Theoretical Focus: The paper primarily focuses on the theoretical design and mathematical properties of symplectic topologies. While it compares them to hypercubes and meshes, a full-scale implementation and performance evaluation on actual supercomputing hardware is not presented.
  • Scalability of Implementation: While the mathematical framework is sound, the practical implementation and routing algorithms for these complex symplectic topologies on real hardware would require further research.
  • Future Work Suggestions: The authors imply that further exploration of different irreducible representations of symplectic algebras could yield even more diverse and optimized topologies. Investigating the practical implementation and performance of these topologies in real-world supercomputing environments would be a natural next step.

Summary updated

Abstract

A family of graphs optimized as the topologies for interconnection networks is proposed. The needs of such topologies with minimal diameters and minimal mean path lengths are met by special constructions of the weight vectors in a representation of the symplectic algebra. Such design of topologies can conveniently reconstruct the mesh and hypercube, widely used as network topologies, as well as many other classes of graphs potentially suitable for network topologies.
BibTeX
@article{sabino2018symmetry,
  author = {Alan U. Sabino and Miguel F. S. Vasconcelos and Yuefan Deng and Alexandre F. Ramos},
  title = {{Symmetry-guided design of topologies for supercomputer networks}},
  journal = {International Journal of Modern Physics C},
  year = {2018},
  doi = {10.1142/s0129183118500481},
}
Figure