Reproduce “DeepPCR: Parallelizing Sequential Operations in Neural Networks” on OpenResearch

About this paper

Federico Danieli, Miguel Sarabia, Xavier Suau, Pau Rodríguez, Luca Zappella

Researchers at Apple introduced DeepPCR, an algorithm that parallelizes inherently sequential operations in neural networks by reformulating them into a system solvable with Parallel Cyclic Reduction. This method reduces computational complexity from O(L) to O(log2 L), achieving up to 200x speedup for backward passes and 11.2x for diffusion model inference while preserving model quality.

Key insights

• Markovian sequential operations in deep learning can be transformed into a system of block bidiagonal equations, allowing for a fundamental algorithmic acceleration from linear to logarithmic complexity.
• The Parallel Cyclic Reduction (PCR) algorithm is effective at solving these block bidiagonal systems in parallel, enabling substantial speedups for tasks like forward/backward passes and diffusion model generation.
• Newton's method, when applied to the non-linear systems, converges reliably within a small, largely L-independent number of iterations, making the overall O(cN log L) complexity practical for achieving significant performance gains.

Summary by alphaXiv.