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）公式获得的强下界进行比较，证明它们在实践中几乎是最优的。我们将这些算法和下界方法应用于生产模型，从而在与标准组合下界相比，获得了显著改进的近似保证。这项工作表明，尽管最大吞吐量划分在理论上很困难，但我们在实践中对该问题的算法方面有所掌握，剩下的挑战主要在于开发更准确的成本模型以提供给划分算法。

具备实际性能保证的深度神经网络推断的线程并行