Total exchange routing on hierarchical dual-nets

Yamin Li, Wanming Chu

TL;DR

This paper introduces the Hierarchical Dual-Net (HDN), a novel interconnection network designed for massive parallel computers. The authors propose an efficient routing algorithm for the "total exchange" communication pattern on HDNs, demonstrating its effectiveness compared to traditional architectures.

What Problem Does This Paper Address?

As supercomputers continue to grow, with projections of millions of nodes, traditional interconnection networks face challenges. Hypercubes, while offering short diameters, suffer from increasing node degrees with scale. Conversely, 2D/3D meshes and tori have fixed, small node degrees but exhibit large diameters, hindering communication efficiency. This paper addresses the need for interconnection networks that can scale to millions of nodes while maintaining both a small node degree and a short diameter, crucial for high-performance parallel computing. Specifically, it focuses on optimizing the "total exchange" communication pattern, a fundamental operation in many parallel applications.

Methods

The core contribution is the introduction of the Hierarchical Dual-Net (HDN). HDNs are built upon a symmetric product graph (the "base network") and are constructed recursively using a "dual-construction" process. Unlike previous recursive dual-nets (RDNs) that grow uncontrollably, HDNs offer a mechanism to control their size and growth rate through a set of parameters (B, k, S). This allows for flexible scaling.

The paper also presents an efficient routing algorithm for the total exchange communication pattern on HDNs. This algorithm is designed to leverage the hierarchical structure of the HDN, breaking down the problem into stages that involve routing within clusters and via cross-edges between clusters at different levels. The algorithm is formally described and its correctness is proven by induction.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Scalability with Controlled Growth: The HDN offers a significant advantage over RDNs by providing a mechanism to control the network's size and growth rate, making it more practical for large-scale systems.
  • Balancing Degree and Diameter: HDNs aim to strike a balance between the node degree and diameter, two critical metrics for interconnection network performance, outperforming traditional networks like hypercubes and tori in this regard.
  • Efficient Total Exchange Algorithm: The proposed routing algorithm effectively utilizes the HDN's hierarchical structure to perform total exchange, a complex communication pattern, efficiently.
  • Weighted Cost Ratio (CRw): The paper introduces a weighted cost ratio metric to evaluate network performance, combining node degree and diameter. HDNs show promising results with this metric, suggesting their effectiveness.

Key Results

The paper demonstrates that HDNs can connect a large number of nodes with a small node degree and short diameter. For instance, using a 2x3x5 torus as a base network, HDNs can scale to millions of nodes while maintaining node degrees of 7 or 8 and relatively small diameters. The total exchange algorithm's time complexity is derived as $T_k(m) = (2^{k+1} – 2)(t_s + t_w m n_k/2) + 2^k T_0(m n_k/2)$, where $n_k$ is the total number of nodes and $T_0$ is the time complexity for total exchange in the base network. While the total exchange time for HDNs might be longer than for hypercubes of similar size, HDNs achieve this with significantly fewer links.

Limitations and Future Work

The authors acknowledge that the total exchange times for HDNs can be longer than for hypercubes, though this comes at the cost of fewer links. They suggest that further research could explore other problems on recursive dual-nets, such as disjoint path and fault-tolerant routing, which are worth investigating. The paper also leaves the theoretical or experimental optimal value of the weighted cost ratio as an open question.

Summary updated

BibTeX
@inproceedings{li2013total,
  author = {Yamin Li and Wanming Chu},
  title = {{Total exchange routing on hierarchical dual-nets}},
  booktitle = {NPC},
  year = {2013},
  doi = {10.1007/978-3-642-40820-5\_16},
}
Figure