Exact makespan formulas clarify gpu pipeline performance biases
Exact Makespan Bounds and the GPipe Homogeneity Bias for Heterogeneous LLM Inference Pipelines
Distributed, Parallel, and Cluster Computing
Summary
Running large language models (LLMs) on mixed GPUs can slow down processing in ways that previous formulas didn’t fully capture. The authors found precise formulas that describe how the slowest stage and communication delays affect overall speed, showing where older estimates go wrong. They showed that balancing compute load across pipeline stages matters more than reducing communication for steady throughput. Their math matches real test cases closely, including mixed GPU setups.
What this means in practice
- •For distributed system engineers: Calculate exact pipeline throughput on mixed GPU clusters to optimize LLM inference scheduling and resource allocation.
- •For cloud infrastructure operators: Predict performance impacts of GPU heterogeneity and communication methods in multi-stage AI inference pipelines for cost-effective scaling.
Authors
Zhu Wenbo
Abstract
We give an exact critical-path characterization of the makespan of micro-batch pipelines serving LLMs on heterogeneous GPU clusters, quantifying how the classic homogeneous GPipe formula errs. In the pure-forward, communication-free, infinite-buffer setting, T(M) = (M-1)tau_max + Sum_j tau_j, where tau_j is stage j's per-micro-batch service time and M the micro-batch count (Theorem 1). Under asynchronous communication -- modern NCCL-based serving -- it extends to T(M) = Sum_j tau_j + Sum_j d_j + (M-1)tau_max, with Sum_j d_j a purely additive constant (Theorem 2); under blocking communication, T(M) = (M-1)sigma_max + Sum_s sigma_s with sigma_s = tau_s + d_s, so communication enters the steady-state slope iff some d_s > tau_max - tau_s (Theorem 3). These results quantify the GPipe overestimate, decompose the bias into a homogeneity term Sum_j (tau_max - tau_j) and a communication-ignoring term Sum_j d_j, and imply that balancing per-stage compute dominates communication reduction for steady-state throughput. A real system with partial overlap is sandwiched between Theorems 2 and 3, with a closed-form bound on the overlap throughput gain. All claims are validated pointwise (error < 10^-9) on eleven configurations and a 1.6x10^5-point fuzz, including a mixed RTX 5090/3090/GTX 1070 partition. We situate the results in flow-shop scheduling and list open extensions: bandwidth-limited communication, bounded buffers, prefill-decode interleaving.