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.
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.
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