Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving

Yang Song, Chenlin Meng, Renjie Liao, Stefano Ermon
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:9791-9800, 2021.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-song21a, title = {Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving}, author = {Song, Yang and Meng, Chenlin and Liao, Renjie and Ermon, Stefano}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {9791--9800}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/song21a/song21a.pdf}, url = {https://proceedings.mlr.press/v139/song21a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving %A Yang Song %A Chenlin Meng %A Renjie Liao %A Stefano Ermon %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-song21a %I PMLR %P 9791--9800 %U https://proceedings.mlr.press/v139/song21a.html %V 139 %X 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.
APA
Song, Y., Meng, C., Liao, R. & Ermon, S.. (2021). Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:9791-9800 Available from https://proceedings.mlr.press/v139/song21a.html.

Related Material