Modeling Universal Globally Adaptive Load-Balanced Routing

Md Atiqul Mollah, Wenqi Wang, Peyman Faizian, Md Shafayat Rahman, Xin Yuan, Scott Pakin, Michael LangACM Transactions on Parallel Computing 2019 · DOI

Abstract

Universal globally adaptive load-balanced (UGAL) routing has been proposed for various interconnection networks and has been deployed in a number of current-generation supercomputers. Although UGAL-based schemes have been extensively studied, most existing results are based on either simulation or measurement. Without a theoretical understanding of UGAL, multiple questions remain: For which traffic patterns is UGAL most suited? In addition, what determines the performance of the UGAL-based scheme on a particular network configuration? In this work, we develop a set of throughput models for UGAL based on linear programming. We show that the throughput models are valid across the torus, Dragonfly, and Slim Fly network topologies. Finally, we identify a robust model that can accurately and efficiently predict UGAL throughput for a set of representative traffic patterns across different topologies. Our models not only provide a mechanism to predict UGAL performance on large-scale interconnection networks but also reveal the inner working of UGAL and further our understanding of this type of routing.

Introduction

In high-performance computing (HPC), the interconnect—the network connecting thousands of processors—is often a primary performance bottleneck. To mitigate congestion, modern supercomputers like the Cray Aries utilize Universal Globally Adaptive Load-balanced (UGAL) routing. UGAL dynamically selects between a minimal path (the shortest route) and a Valiant (VLB) path (a longer route through a random intermediate node) based on network conditions.

Despite its widespread adoption, a deep theoretical understanding of UGAL's performance characteristics has been lacking. Historically, researchers have relied on time-consuming cycle-accurate simulations to evaluate network designs. This work introduces the first theoretical throughput models for UGAL using linear programming (LP), providing a mathematical framework to predict performance across diverse topologies such as the Dragonfly and Torus.

Methodology and Network Topologies

The proposed models utilize Linear Programming to solve the Maximum Concurrent Flow (MCF) problem, seeking the maximum data rate supportable for all communicating pairs without exceeding link capacities. The researchers evaluated a hierarchy of six models (Model 0 through Model 5) representing different levels of routing control:

  • Individual Control: Perfect tuning of data rates for every possible path.
  • Path-Length-Based Random Control: Traffic distribution based on path length groups.
  • All-Random Control: Uniform traffic distribution across all paths.

The models were validated against flit-level simulations in Booksim across several key topologies, including the Dragonfly and 2D Torus structures.

The Dragonfly topology, one of the primary network structures used to validate the UGAL throughput models.
A 2D Torus network topology, illustrating the grid-based connectivity analyzed in the study.

Key Insights

A significant finding is that UGAL-G (the idealized version of UGAL) acts as a "group" optimizer rather than an individual path optimizer. It effectively balances traffic across groups of paths categorized by their lengths. Among the tested models, Model 3 (path-length-based control) emerged as the most robust and efficient. It accurately predicts performance with minimal variables per flow, making it suitable for modeling massive systems with tens of thousands of nodes.

Furthermore, the models are "topology-oblivious." The same mathematical formulation applies regardless of whether the underlying network is a Torus or a Dragonfly, suggesting that path length is the fundamental metric governing adaptive routing performance.

Results and Performance

Model 3 demonstrated high accuracy, with prediction errors ranging from only 4.3% to 8.6% for Dragonfly networks when compared to cycle-accurate simulations. The study also established performance bounds: "Model 0" (individual control) consistently serves as an upper bound, while "Model 5" (all-random) serves as a lower bound, effectively "sandwiching" the actual performance of UGAL.

Limitations and Future Directions

While the models are highly effective for standard topologies, some anomalies were observed in "shift" traffic patterns on the Slim Fly topology due to its non-symmetrical nature. Additionally, the current work focuses on UGAL-G, which assumes global network knowledge. Future research will aim to adapt these LP models for UGAL-L (local knowledge) and to capture transient network behaviors beyond steady-state throughput.

Summary updated

Abstract

Universal globally adaptive load-balanced (UGAL) routing has been proposed for various interconnection networks and has been deployed in a number of current-generation supercomputers. Although UGAL-based schemes have been extensively studied, most existing results are based on either simulation or measurement. Without a theoretical understanding of UGAL, multiple questions remain: For which traffic patterns is UGAL most suited? In addition, what determines the performance of the UGAL-based scheme on a particular network configuration? In this work, we develop a set of throughput models for UGALbased on linear programming. We show that the throughput models are valid across the torus, Dragonfly, and Slim Fly network topologies. Finally, we identify a robust model that can accurately and efficiently predict UGAL throughput for a set of representative traffic patterns across different topologies. Our models not only provide a mechanism to predict UGAL performance on large-scale interconnection networks but also reveal the inner working of UGAL and further our understanding of this type of routing.
BibTeX
@article{mollah2019modeling,
  author = {Md Atiqul Mollah and Wenqi Wang and Peyman Faizian and Md Shafayat Rahman and Xin Yuan and Scott Pakin and Michael Lang},
  title = {{Modeling Universal Globally Adaptive Load-Balanced Routing}},
  journal = {ACM Transactions on Parallel Computing},
  year = {2019},
  doi = {10.1145/3349620},
}
Figure