TL;DR
This paper presents a comprehensive catalog of "optimal" regular graphs, meticulously constructed using supercomputer enumerations. These graphs are characterized by desirable properties for network design, including minimal diameter, minimal mean path length, large bisection width, and high symmetry, offering a valuable resource for building efficient interconnection networks.
What Problem Does This Paper Address?
The relentless growth of computing power, particularly in next-generation supercomputers and multi-core processors, necessitates highly efficient and scalable interconnection networks. These networks are the backbone of communication between processing units, and their performance directly impacts overall system speed, latency, and energy efficiency. Traditional network topologies, while effective, often have limitations in terms of scalability and the ability to maintain desired properties like low latency and high throughput as the number of nodes increases. The challenge lies in discovering and cataloging graph structures that exhibit a superior combination of key performance metrics, especially when considering the complex interplay between diameter, mean path length, bisection width, and graph symmetry. This paper aims to fill this gap by systematically identifying and presenting such optimal graphs.
Methods
The authors employ a rigorous, exhaustive search methodology on supercomputers to enumerate regular graphs with specific numbers of vertices ($N$) and degrees ($k$). The core of their approach involves filtering these enumerated graphs based on a set of prioritized criteria:
- Minimal Diameter: The longest shortest path between any two nodes in the graph.
- Minimal Mean Path Length (MPL): The average shortest path length over all pairs of nodes.
- Maximal Bisection Width: The minimum number of edges that must be removed to divide the graph into two roughly equal halves, representing the bottleneck for communication.
- Maximal Automorphism Group Size: A measure of graph symmetry, where a larger group indicates more symmetries, which can lead to better load balancing and robustness in networks.
The paper leverages established theoretical lower bounds for diameter (Moore bound) and MPL to guide their search and identify graphs that approach or meet these theoretical optima. For calculating bisection widths, they utilize the KaHIP tool, and for automorphism group sizes, they employ GAP and SageMath. The results are then organized into structured tables for easy reference.
Datasets
The paper does not rely on pre-existing datasets for training or evaluation in the traditional machine learning sense. Instead, it generates and analyzes a vast number of candidate graphs through computational enumeration. The "dataset" is effectively the collection of optimal graphs discovered and characterized by the authors, presented in their tables. They also reference existing graph databases (like Wolfram Mathematica's "graphdata") to confirm the properties of some of their discovered optimal graphs, which they refer to as "named graphs."
Key Insights and Ideas
- Systematic Cataloging of "Optimal" Graphs: The paper moves beyond ad-hoc discoveries to provide a structured, comprehensive table of graphs that are demonstrably optimal across multiple critical network performance metrics.
- Prioritization of Network Design Metrics: The authors clearly define and prioritize diameter, MPL, bisection width, and symmetry, reflecting their importance in designing high-performance interconnection networks.
- The Power of Symmetry: The emphasis on automorphism group size highlights the crucial role of symmetry in achieving robust and efficient network performance, particularly in load balancing and fault tolerance.
- Discovery of New Optimal Graphs: Many of the graphs presented are noted as newly discovered, suggesting that traditional approaches may have overlooked certain optimal structures.
- Foundation for Larger Networks: The presented optimal "base" graphs can serve as building blocks for constructing larger, more complex networks through methods like Cartesian products or hierarchical designs.
Key Results
The paper presents extensive tables (Tables 2-4) detailing optimal graphs for various combinations of vertices ($N$) and degrees ($k$). For instance, they identify optimal graphs for $N$ up to 32 and $k$ up to 7. The tables include the Mean Path Length (MPL), Diameter (D), Bisection Width (BW), and the size of the Automorphism Group (Aut(G)) for each optimal graph. Many of these graphs are shown to achieve theoretical lower bounds for diameter and MPL, while others, marked with an asterisk, are the minimum achievable even if not matching the theoretical bound. The paper also provides finite presentations of semidirect product groups associated with some of these optimal graphs (Table 5) and summarizes properties of known named graphs that are also found to be optimal (Table 6).
Limitations and Future Work
The authors acknowledge that for certain graph parameters (e.g., (32, 4)), the number of non-isomorphic graphs is too massive to exhaustively search. This implies that their catalog, while extensive, may not be exhaustive for all possible $(N, k)$ combinations.
Future work suggested by the paper includes:
- Expanding the Catalog: Continuing the search for optimal graphs with larger orders and degrees.
- Application in Network Design: Applying these newly discovered optimal graphs to design more efficient interconnection networks for microchips and data centers.
- Further Exploration of Properties: Investigating other potential properties and applications of these optimal graphs, which could lead to further discoveries.
- Constructing Larger Networks: Using these optimal base graphs as building blocks to construct larger and more diverse interconnection networks through methods like Cartesian products and hierarchical designs.
Summary updated