In plain words: Sequential models like recurrent networks process one step at a time; this algorithm spreads the work across the sequence so GPUs can run many steps at once, needing no special architecture. It runs up to 1,000 times faster with identical outputs and training results.
Abstract
Sequential models, such as Recurrent Neural Networks and Neural Ordinary Differential Equations, have long suffered from slow training due to their inherent sequential nature. For many years this bottleneck has persisted, as many thought sequential models could not be parallelized. We challenge this long-held belief with our parallel algorithm that accelerates GPU evaluation of sequential models by up to 3 orders of magnitude faster without compromising output accuracy. The algorithm does not need any special structure in the sequential models' architecture, making it applicable to a wide range of architectures. Using our method, training sequential models can be more than 10 times faster than the common sequential method without any meaningful difference in the training results. Leveraging this accelerated training, we discovered the efficacy of the Gated Recurrent Unit in a long time series classification problem with 17k time samples. By overcoming the training bottleneck, our work serves as the first step to unlock the potential of non-linear sequential models for long sequence problems.
Yi Heng Lim, Qi Zhu, Joshua Selfridge, Muhammad Firmansyah Kasim
arXiv:2309.12252 · cs.LG, cs.DC, physics.comp-ph · submitted Sep 21, 2023 · updated Jan 16, 2024
abstract · pdf · html
If that's right, it means that in practice the proposed parallelization method will likely be much slower and much less efficient than modern implementations of self-attention, which have O(n²) time complexity and O(n) space complexity (for example, with FlashAttention). Ouch.
og_kalu, have you had a chance to look at this closely or tinker with it?