HAP: SPMD DNN Training on Heterogeneous GPU Clusters with Automated Program Synthesis

Shiwei Zhang, Lansong Diao, Chuan Wu, Zongyan Cao, Siyu Wang, Wei Lin

Introduction

State-of-the-art Deep Learning models are increasingly trained on large-scale distributed systems. While standard frameworks like Megatron-LM and DeepSpeed excel in homogeneous environments, real-world data centers often consist of heterogeneous clusters with varying GPU generations (e.g., NVIDIA P100s mixed with V100s) and non-uniform network interconnects. In these "messy" clusters, standard Single-Program-Multiple-Data (SPMD) training suffers from the "straggler" problem—where faster GPUs idle while waiting for slower ones—and inefficient communication due to rigid data-splitting rules.

HAP is an automated system designed to overcome these challenges. By combining automated program synthesis with linear programming, HAP intelligently shards models and balances workloads, achieving up to a 2.41x speedup over standard distributed training methods.

The HAP Framework: Synthesis and Optimization

HAP employs a two-pronged iterative approach to optimize distributed training:

1. Automated Program Synthesis

Instead of relying on hard-coded transformation rules, HAP treats model partitioning as a formal logic problem. It uses Syntax-Guided Synthesis to generate a distributed program from scratch. The system defines the semantics of DNN operations using Hoare triples (preconditions and postconditions), ensuring that the resulting distributed program is mathematically equivalent to the single-device version. An A*-based search algorithm explores the vast space of possible sharding strategies to minimize execution time.

HAP synthesizes distributed programs, enabling optimizations like Sufficient Factor Broadcasting (c) compared to standard All-Reduce (b).

2. Linear Programming for Workload Balancing

Once a sharding strategy is selected, HAP determines the precise amount of data to assign to each GPU using Linear Programming (LP). By modeling computation and communication costs as linear functions of sharding ratios, HAP uses off-the-shelf solvers to find the mathematically optimal balance for a specific hardware configuration.

Key Insights: The CP vs. EV Trade-off

A critical insight of the HAP paper is the trade-off between Computation-Proportional (CP) and Even (EV) sharding. CP sharding assigns more work to faster GPUs, which is ideal when computation is the primary bottleneck. However, when network bandwidth is limited, EV sharding (splitting data equally) may be superior because it avoids the overhead of uneven communication primitives.

The optimal sharding strategy (CP vs. EV) depends heavily on the computation-to-communication ratio of the workload and hardware.

HAP's synthesis approach allows it to discover novel optimizations, such as Sufficient Factor Broadcasting (SFB), which can significantly reduce data transfer volumes for specific layers compared to standard All-Reduce operations.

Evaluation and Results

The authors evaluated HAP across four representative workloads: VGG19, Vision Transformer (ViT), BERT-Base, and BERT-MoE (Mixture-of-Experts). Key findings include:

  • Significant Speedups: HAP achieved up to a 2.41x speedup on heterogeneous clusters compared to standard data-parallel baselines.
  • Scalability and Efficiency: On a 64-GPU mixed cluster, HAP consistently outperformed specialized systems like DeepSpeed and TAG.
  • MoE Support: HAP successfully trained BERT-MoE models that otherwise triggered "Out of Memory" errors by intelligently sharding massive expert layers across devices.
  • Low Overhead: Despite the complexity of the A* search, program synthesis typically completes in a few seconds, making it viable for production use.

Conclusion

HAP demonstrates that automated program synthesis is a powerful tool for managing the complexity of heterogeneous hardware. By decoupling performance optimization from manual implementation, HAP enables efficient, balanced, and mathematically sound distributed training on the diverse hardware found in modern data centers.

Summary updated

BibTeX
@inproceedings{zhang2024hap,
  author = {Shiwei Zhang and Lansong Diao and Chuan Wu and Zongyan Cao and Siyu Wang and Wei Lin},
  title = {{HAP: SPMD DNN Training on Heterogeneous GPU Clusters with Automated Program Synthesis}},
  booktitle = {EuroSys},
  year = {2024},
  url = {https://openreview.net/forum?id=gRbpb7e9k1},
}
Figure