Introduction
Deep Neural Network (DNN) inference for massive models often requires partitioning the computation graph across multiple computational units (CUs). This technique, known as pipeline parallelism, aims to maximize throughput by minimizing the execution time of the slowest stage—the bottleneck. However, determining the optimal partition is an NP-hard problem. Practitioners often rely on heuristics but lack a way to measure how close their solutions are to the theoretical optimum. This paper introduces a hierarchy of Mixed-Integer Programming (MIP) relaxations to provide tight lower bounds on performance and a fast partitioning algorithm, SliceGraph, that achieves near-optimal results.
The Partitioning Challenge
In a pipelined system, a model is divided into $k$ stages. Each stage $i$ processes a batch of data and passes the output to stage $i+1$. The overall throughput is limited by the stage with the longest latency.
The "practitioner’s dilemma" arises when a heuristic produces a partition with a specific bottleneck latency (e.g., 10ms). Without a tight lower bound, it is impossible to know if a significantly better solution (e.g., 5ms) exists. Standard combinatorial bounds are often too loose to be actionable.
Methodology
The authors propose a dual approach: generating high-quality partitions and certifying their optimality.
Proving Lower Bounds: The MIP Hierarchy
To establish tight performance guarantees, the authors developed several MIP formulations for the Max-Throughput Partitioning Problem (MTPP):
- Exact MIP: Provides the absolute optimal partition but is computationally intensive for large graphs.
- "Guess the Bottleneck" Relaxation: By assuming a specific block is the bottleneck, the solver can simplify constraints and produce a tighter lower bound more quickly than the exact method.
- Three-Superblock Relaxation: Further accelerates the process by grouping stages around a hypothetical bottleneck into "superblocks," significantly reducing the variable count.
A key innovation in these formulations is the use of redundant binary variables to represent node assignments, which surprisingly improves solver performance by enabling more effective pruning during the branch-and-bound search.
Finding Solutions: The SliceGraph Algorithm
To generate practical partitions, the authors introduced SliceGraph. This algorithm transforms the graph-partitioning problem into a search over topological orderings. It employs a Biased Random-Key Genetic Algorithm (BRKGA) to evolve node priorities. For any given priority-based ordering, SliceGraph uses Dynamic Programming to find the mathematically optimal way to "slice" the sequence into $k$ stages.
Experimental Evaluation
The methods were tested on two datasets:
- Production Testbed: 369 real-world Google computation graphs (e.g., BERT, ResNet, WaveRNN).
- Synthetic Graphs (REGAL): 1,000 challenging synthetic models designed to test memory scheduling and partitioning.
Key Results
The MIP-based relaxations significantly improved the quality of performance certificates. For 16-stage pipelines, standard bounds only reached 46% of the best-found solution's value, whereas the new MIP formulations reached 94.5%. This represents a nearly 10x reduction in the "optimality gap."
SliceGraph also demonstrated high efficiency, with solutions averaging within 4.5% of the proven theoretical optimum for $k \le 16$.
Conclusion and Future Work
This work provides practitioners with the tools to not only find efficient DNN partitions but also to know when further optimization is unnecessary. While the MIP lower bounds are currently best suited for offline benchmarking due to their computational cost, they set a new standard for performance guarantees in pipeline parallelism. Future research may extend these techniques to heterogeneous hardware clusters and integrate more complex compiler optimizations like operator fusion.
Summary updated