# Efficient Parallelization of a Ubiquitous Sequential Computation

arXiv: https://arxiv.org/abs/2311.06281 · HTML: https://mlsanity.com/paper/2311.06281/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 4 references that are in the map.
- First posted on arXiv 27 Oct 2023.

## Built on by (most cited first, 5 of 5)

- [Gated Linear Attention Transformers with Hardware-Efficient Training](https://mlsanity.com/paper/2312.06635/) (2023)
- [Exploring Performance-Complexity Trade-Offs in Sound Event Detection Models](https://mlsanity.com/paper/2503.11373/) (2025)
- [Minimal Convolutional RNNs Accelerate Spatiotemporal Learning](https://mlsanity.com/paper/2508.03614/) (2025)
- [Scalable Memristive-Friendly Reservoir Computing for Time Series Classification](https://mlsanity.com/paper/2604.19343/) (2026)
- [NeuralBES: A Differentiable, Control-Aware Emulator for Scalable Building Energy Modeling](https://mlsanity.com/paper/2610.10459/) (2026)

## Abstract (arXiv)

We find a succinct expression for computing the sequence xt = at xt-1 + bt in parallel with two prefix sums, given t = (1, 2, dots, n), at ∈ ℝn, bt ∈ ℝn, and initial value x0 ∈ ℝ. On n parallel processors, the computation of n elements incurs O(log n) time and O(n) space. Sequences of this form are ubiquitous in science and engineering, making efficient parallelization useful for a vast number of applications. We implement our expression in software, test it on parallel hardware, and verify that it executes faster than sequential computation by a factor of fracnlog n.