# DeepPCR: Parallelizing Sequential Operations in Neural Networks

arXiv: https://arxiv.org/abs/2309.16318 · HTML: https://mlsanity.com/paper/2309.16318/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 31 of its 44 references that are in the map.
- First posted on arXiv 28 Sep 2023.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Fully Convolutional Networks for Semantic Segmentation](https://mlsanity.com/paper/1411.4038/) (2014)
- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [DeepLab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFs](https://mlsanity.com/paper/1606.00915/) (2016)
- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [Arbitrary Style Transfer in Real-time with Adaptive Instance Normalization](https://mlsanity.com/paper/1703.06868/) (2017)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [PixelCNN++: Improving the PixelCNN with Discretized Logistic Mixture Likelihood and Other Modifications](https://mlsanity.com/paper/1701.05517/) (2017)
- [MADE: Masked Autoencoder for Distribution Estimation](https://mlsanity.com/paper/1502.03509/) (2015)
- [cuDNN: Efficient Primitives for Deep Learning](https://mlsanity.com/paper/1410.0759/) (2014)
- [TPU v4: An Optically Reconfigurable Supercomputer for Machine Learning with Hardware Support for Embeddings](https://mlsanity.com/paper/2304.01433/) (2023)
- [Pruning Neural Networks at Initialization: Why are We Missing the Mark?](https://mlsanity.com/paper/2009.08576/) (2020)
- [Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/1802.09941/) (2018)
- [Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving](https://mlsanity.com/paper/2002.03629/) (2020)
- [Layer-Parallel Training of Deep Residual Neural Networks](https://mlsanity.com/paper/1812.04352/) (2018)
- [Differentiable Multiple Shooting Layers](https://mlsanity.com/paper/2106.03885/) (2021)
- [Layer-Wise Data-Free CNN Compression](https://mlsanity.com/paper/2011.09058/) (2020)
- [Predictive Sampling with Forecasting Autoregressive Models](https://mlsanity.com/paper/2002.09928/) (2020)
- [Layer-Parallel Training with GPU Concurrency of Deep Residual Neural Networks via Nonlinear Multigrid](https://mlsanity.com/paper/2007.07336/) (2020)
- [Parallel Training of GRU Networks with a Multi-Grid Solver for Long Sequences](https://mlsanity.com/paper/2203.04738/) (2022)
- [Parallel Complexity of Forward and Backward Propagation](https://mlsanity.com/paper/1712.06577/) (2017)
- [Apple Silicon Performance in Scientific Computing](https://mlsanity.com/paper/2211.00720/) (2022)

## Built on by (most cited first, 9 of 9)

- [Predictability Enables Parallelization of Nonlinear State Space Models](https://mlsanity.com/paper/2508.16817/) (2025)
- [Pretraining Recurrent Networks without Recurrence](https://mlsanity.com/paper/2606.06479/) (2026)
- [Accelerated Training through Iterative Gradient Propagation Along the Residual Path](https://mlsanity.com/paper/2501.17086/) (2025)
- [A Unifying Framework for Parallelizing Sequential Models with Linear Dynamical Systems](https://mlsanity.com/paper/2509.21716/) (2025)
- [Layer-Parallel Training for Transformers](https://mlsanity.com/paper/2601.09026/) (2026)
- [SNLP: Layer-Parallel Inference via Structured Newton Corrections](https://mlsanity.com/paper/2605.17842/) (2026)
- [Generalized Orders of Magnitude for Scalable, Parallel, High-Dynamic-Range Computation](https://mlsanity.com/paper/2510.03426/) (2025)
- [LBI: Parallel Scan Backpropagation via Latent Bounded Interfaces](https://mlsanity.com/paper/2605.09204/) (2026)
- [Switching Linear Attention](https://mlsanity.com/paper/2609.39034/) (2026)

## Abstract (arXiv)

Parallelization techniques have become ubiquitous for accelerating inference and training of deep neural networks. Despite this, several operations are still performed in a sequential manner. For instance, the forward and backward passes are executed layer-by-layer, and the output of diffusion models is produced by applying a sequence of denoising steps. This sequential approach results in a computational cost proportional to the number of steps involved, presenting a potential bottleneck as the number of steps increases. In this work, we introduce DeepPCR, a novel algorithm which parallelizes typically sequential operations in order to speed up inference and training of neural networks. DeepPCR is based on interpreting a sequence of L steps as the solution of a specific system of equations, which we recover using the Parallel Cyclic Reduction algorithm. This reduces the complexity of computing the sequential operations from O(L) to O(log2L), thus yielding a speedup for large L. To verify the theoretical lower complexity of the algorithm, and to identify regimes for speedup, we test the effectiveness of DeepPCR in parallelizing the forward and backward pass in multi-layer perceptrons, and reach speedups of up to 30× for the forward and 200× for the backward pass. We additionally showcase the flexibility of DeepPCR by parallelizing training of ResNets with as many as 1024 layers, and generation in diffusion models, enabling up to 7× faster training and 11× faster generation, respectively, when compared to the sequential approach.