Parallelization techniques have become ubiquitous to accelerate inference and training of deep neural networks. Despite this, several operations are still performed sequentially. For example, 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 present DeepPCR, a novel algorithm that parallelizes typically sequential operations to accelerate inference and training of neural networks. DeepPCR is based on the interpretation of a sequence of steps such as the solution of a specific system of equations, which we recover using the Parallel Cyclic Reduction algorithm. This reduces the complexity of calculating sequential operations of to thus generating an acceleration for large . To verify the lower theoretical complexity of the algorithm and identify speedup regimes, we tested the effectiveness of DeepPCR in parallelizing forward and backward passing in multilayer perceptrons and achieved speedups of up to for the forward and for the backward pass. Furthermore, we show the flexibility of DeepPCR by parallelizing the training of ResNets with up to 1024 layers and the generation in diffusion models, allowing up to faster training and faster generation, respectively, compared to the sequential approach.
