Demystifying Pipeline Parallelism: First Theory for PipeDream

We study pipeline model parallelism through the lens of PipeDream ($\textbf{PD}$) (Harlap et al., 2018), whose one-forward-one-backward (1F1B) schedule keeps stages busy at the price of gradients computed on stale, stage-wise weight versions. We introduce Randomized PipeDream ($\textbf{RPD}$), a stale block-SGD abstraction that yields, to our knowledge, the first clean nonconvex convergence guarantee for a $\textbf{PD}$-style method, and we prove that the delay induced by steady-state $\textbf{PD}$ grows as $S^2 - S/2 + O(1)$ for $S$ stages, so the stale-read term of the bound scales as $\Theta(\gamma^2 S^4)$, or $\Theta(S^4/K)$ after stepsize tuning. Finally, we compare $\textbf{PD}$ with $\textbf{LocalSGD}$, whose periodic model averaging trades weight staleness for synchronization bubbles; in simulated-time experiments the better method depends on the objective.