Practical Performance Guarantees for Pipelined DNN Inference

Aaron Archer, Matthew Fahrbach, Kuikui Liu, Prakash Prabhu

TL;DR

This paper tackles the "practitioner’s dilemma" in Deep Neural Network (DNN) pipelining: knowing when a model partition is truly "good enough." By developing novel Mixed-Integer Programming (MIP) relaxations, the authors provide significantly tighter lower bounds on performance. Their approach closes the optimality gap by nearly 10x compared to standard methods, proving that their heuristic solutions are often near-optimal in real-world scenarios.

What Problem Does This Paper Address?

When running massive DNNs, a single processor often lacks the fast memory (such as SRAM or HBM) required to hold all model parameters and activations simultaneously. To solve this, engineers rely on pipeline parallelism: splitting the model into $k$ distinct stages, each running on a different computational unit (CU).

Illustration of pipeline parallelism across multiple computational units (CUs) over time.

However, this introduces a difficult optimization challenge known as the Max-Throughput Partitioning Problem (MTPP). Engineers must balance two competing goals:

  1. Minimize Communication: Moving data between CUs is slow and consumes valuable bandwidth.
  2. Balance the Load: The entire pipeline’s throughput is strictly limited by its slowest stage (the "bottleneck").

Because MTPP is NP-hard, practitioners typically use heuristics to find workable partitions. This leads to the "practitioner's dilemma": without a strong lower bound (a mathematical proof of the best possible theoretical performance), an engineer doesn't know if their 10ms bottleneck is a masterpiece of optimization or if a 5ms solution is hiding just around the corner. Standard combinatorial bounds are often too loose to be useful—for instance, predicting a 2ms theoretical limit when 10ms is the true physical minimum.

Methods

The authors introduce a hierarchy of techniques to both solve the partitioning problem and, crucially, prove how close those solutions are to the theoretical limit.

1. SliceGraph (The Solver)

To find high-quality partitions quickly, the authors developed SliceGraph. It reduces the complex partitioning problem into a search over topological orderings of the model graph.

  • It uses Dynamic Programming (DP) to find the mathematically optimal way to "slice" a specific ordering into $k$ stages.
  • It employs a Biased Random-Key Genetic Algorithm (BRKGA) to evolve and discover the best topological orderings over time.

2. MIP Relaxations (The Prover)

To provide rigorous performance guarantees, the team formulated the problem as a Mixed-Integer Program (MIP). Because an exact MIP is computationally prohibitive for large models, they designed two clever relaxations:

  • Three-Superblock Formulation: Instead of modeling all $k$ stages, this formulation models the bottleneck stage and "lumps" everything before it into one block, and everything after it into another. This drastically simplifies the math while keeping the bound highly relevant.
  • "Guess the Bottleneck" Formulation: This approach assumes a specific stage $j$ is the bottleneck and calculates a lower bound for that specific scenario. By iterating this for all possible $j$ and taking the minimum, they achieve an even tighter bound.

Datasets

The researchers evaluated their methods on two massive testbeds:

  • Production Dataset: 369 computation graphs from real-world Google production models, including architectures like BERT, ResNet, MobileNet, LSTMs, and WaveRNN.
  • REGAL Dataset: 1,000 publicly available synthetic model graphs specifically designed to be challenging for memory scheduling and partitioning algorithms.

Key Insights and Ideas

  • Standard Bounds are Too Weak: Simple combinatorial bounds (like simply looking at the single heaviest operation) only reached about 46% of the best-found solution's value. This makes them practically useless for proving a solution is "good."
  • The Power of "Lumping": You don't need to solve the entire $k$-stage problem to get a strong lower bound. Modeling just the bottleneck and its immediate neighbors (the superblocks) captures the most critical constraints of the system.
  • Closing the Gap: The MIP-based lower bounds are "strong enough to be useful." For $k=16$ stages, the new bounds reached ~94.5% of the best-found solution, effectively telling the engineer, "You are within 5.5% of perfection; stop searching."

Key Results

The quantitative improvements in performance guarantees are striking:

Comparison of lower bounds and exact solutions across different graph sizes for k=64.
  • Optimality Gap: For 16 pipeline stages, the MIP formulations raised the lower bound from 0.4598 to 0.9452 (expressed as a fraction of the best partition found). This represents a massive 9.855x reduction in the optimality gap.
  • Heuristic Effectiveness: The SliceGraph algorithm, despite being a heuristic, was shown to be highly effective. In many cases, the gap between the SliceGraph solution and the exact MIP lower bound was less than 1%.
  • Scalability: While the exact MIP is slow, the "bottleneck-guess" relaxation provides a practical middle ground. It offers much tighter bounds than simple methods while remaining computationally feasible for offline analysis, even as the number of nodes scales up.

Limitations and Future Work

  • Offline Only: The MIP-based lower bound calculations are roughly four orders of magnitude slower than the SliceGraph heuristic. This makes them excellent for offline "gold standard" analysis but too slow to run inside a real-time ML compiler.
  • Simplified Memory Model: To keep the MIP tractable, the authors ignored certain "overflow" terms related to peak activation memory, assuming a fixed buffer instead. Integrating dynamic peak memory scheduling into the MIP remains an open challenge.
  • Heterogeneity: The current model assumes all CUs are identical. Future work could extend this to heterogeneous systems, such as a mix of different GPU generations or specialized accelerators.

Summary updated

Abstract

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 \in \\{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.
BibTeX
@inproceedings{archer2024practical,
  author = {Aaron Archer and Matthew Fahrbach and Kuikui Liu and Prakash Prabhu},
  title = {{Practical Performance Guarantees for Pipelined DNN Inference}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=S3xqyEaST9},
}
Figure