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 design practical algorithms
for this NP-hard problem and show that they are nearly optimal in practice by
comparing against strong lower bounds obtained via novel mixed-integer
programming (MIP) formulations. We apply these algorithms and lower-bound
methods to production models to achieve substantially improved approximation
guarantees compared to standard combinatorial lower bounds. For example,
evaluated via geometric means across production data with $k=16$ pipeline
stages, our MIP formulations more than double the lower bounds, improving the
approximation ratio from $2.175$ to $1.058$. This work shows that while
max-throughput partitioning is theoretically hard, we have a handle on the
algorithmic side of the problem in practice and much of the remaining challenge
is in developing more accurate cost models to feed into the partitioning
algorithms.

通过将模型图分成 k 个阶段并减少瓶颈阶段的运行时间，我们通过最小化通信成本来优化深度神经网络（DNN）推理的流水线并行性。我们设计了针对这个 NP 困难问题的实际算法，并通过与通过新颖的混合整数规划（MIP）公式获得的强下界进行比较，证明它们在实践中几乎是最优的。我们将这些算法和下界方法应用于生产模型，从而在与标准组合下界相比，获得了显著改进的近似保证。这项工作表明，尽管最大吞吐量划分在理论上很困难，但我们在实践中对该问题的算法方面有所掌握，剩下的挑战主要在于开发更准确的成本模型以提供给划分算法。