Practical Performance Guarantees for Pipelined DNN Inference
Not on the map. Why?
Abstract (arXiv)
We optimize pipeline parallelism for deep neural network (DNN) inference by partitioning model graphs into k stages and minimizing the running time of the bottleneck stage, including communication. We give practical and effective algorithms for this NP-hard problem, but our emphasis is on tackling the practitioner's dilemma of deciding when a solution is good enough. To this end, we design novel mixed-integer programming (MIP) relaxations for proving lower bounds. Applying these methods to a diverse testbed of 369 production models, for k ∈ 2, 4, 8, 16, 32, 64, we empirically show that these lower bounds are strong enough to be useful in practice. Our lower bounds are substantially stronger than standard combinatorial bounds. For example, evaluated via geometric means across a production testbed with k = 16 pipeline stages, our MIP formulations raise the lower bound from 0.4598 to 0.9452, expressed as a fraction of the best partition found. In other words, our improved lower bounds close the optimality gap by a factor of 9.855x.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 28 of its 61 references that are in the map. First posted on arXiv 7 Nov 2023.
Builds on
28 of 61 references.
References · 28
- 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
- 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,673
- 2019Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelismcited by 1,868
- 2020GShard: Scaling Giant Models with Conditional Computation and Automatic Shardingcited by 1,631
- 2017In-Datacenter Performance Analysis of a Tensor Processing Unitcited by 618
- 2023TPU v4: An Optically Reconfigurable Supercomputer for Machine Learning with Hardware Support for Embeddingscited by 202
- 2015MXNet: A Flexible and Efficient Machine Learning Library for Heterogeneous Distributed Systemscited by 195
- 2018Mesh-TensorFlow: Deep Learning for Supercomputerscited by 169
- 2020Memory-Efficient Pipeline-Parallel DNN Trainingcited by 134
- 2021GSPMD: General and Scalable Parallelization for ML Computation Graphscited by 111
- 2021MCUNetV2: Memory-Efficient Patch-based Inference for Tiny Deep Learningcited by 89
- 2022Decentralized Training of Foundation Models in Heterogeneous Environmentscited by 87
16 more
- 2021TeraPipe: Token-Level Pipeline Parallelism for Training Large-Scale Language Modelscited by 75
- 2023SWARM Parallelism: Training Large Models Can Be Surprisingly Communication-Efficientcited by 59
- 2019PipeMare: Asynchronous Pipeline Parallel DNN Trainingcited by 55
- 2020HetPipe: Enabling Large DNN Training on (Whimpy) Heterogeneous GPU Clusters through Integration of Pipelined Model Parallelism and Data Parallelismcited by 46
- 2020Ordering Chaos: Memory-Aware Scheduling of Irregularly Wired Neural Networks for Edge Devicescited by 27
- 2020torchgpipe: On-the-fly Pipeline Parallelism for Training Giant Modelscited by 26
- 2019Reinforced Genetic Algorithm Learning for Optimizing Computation Graphscited by 17
- 2015Dissecting GPU Memory Hierarchy through Microbenchmarkingcited by 6
- 2022Efficient Pipeline Planning for Expedited Distributed DNN Trainingcited by 4
- 2017Graph Partitioning with Acyclicity Constraintscited by 2
- 2020Multilevel Acyclic Hypergraph Partitioningcited by 2
- 2021A Transferable Approach for Partitioning Machine Learning Models on Multi-Chip-Modulescited by 2
- 2013A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrayscited by 1
- 2021TENSILE: A Tensor granularity dynamic GPU memory scheduling method toward multiple dynamic workloads systemcited by 1
- 2022A Simple and Elegant Mathematical Formulation for the Acyclic DAG Partitioning Problemcited by 1
- 2022Partitioning Hypergraphs is Hard: Models, Inapproximability, and Applicationscited by 1
Built on by
Not cited yet.