Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving

By Yang Song, Chenlin Meng, Renjie Liao, Stefano Ermon. 2020

50 citations recorded by the source corpus.

Feedforward computation, such as evaluating a neural network or sampling from an autoregressive model, is ubiquitous in machine learning. The sequential nature of feedforward computation, however, requires a strict order of execution and cannot be easily accelerated with parallel computing. To enable parallelization, we frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point iteration method, as well as hybrid methods of both. Crucially, Jacobi updates operate independently on each equation and can be executed in parallel. Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallelizable iterations, and hence reduced time given sufficient parallel computing power. Experimentally, we demonstrate the effectiveness of our approach in accelerating (i) backpropagation of RNNs, (ii) evaluation of DenseNets, and (iii) autoregressive sampling of MADE and PixelCNN++, with speedup factors between 2.1 and 26 under various settings.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics, ML Systems & Hardware, Numerical Methods & Scientific Computing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

In ML Systems & Hardware

In Numerical Methods & Scientific Computing

Citations in the corpus

Accelerating Large Language Model Decoding with Speculative Sampling (2023, methodology): “This includes block parallel sampling (Stern et al., 2018), aggressive decoding (Ge et al., 2022), in addition to some work in parallelizing autoregressive models in the image domain (Song et al., 2021; Wiggers and Hoogeboom, 2020).”
Break the Sequential Dependency of LLM Inference Using Lookahead Decoding (2024, methodology): “…f ( y i , y 1: i − 1 , x 0 ) = y i − argmax P M ( y i | y 1: i − 1 , x 0 ) , we can transform Eqs 1 into the following non-linear system of equations (Song et al., 2021; Santilli et al., 2023): We can solve this non-linear system using Jacobi iteration by iteratively updating all y i from a…”
Continuous diffusion for categorical data (2022, methodology): “In fact, the most commonly used modelling setup for images implicitly reduces the loss weighting of high frequency content relative to likelihood-based models, allowing for a more eﬃcient use of model capacity which is well aligned with human perception (Song et al., 2021a).”