Parallel Prefix Computation

By Richard E. Ladner, Michael J. Fischer. 1980

Subfields: Algorithms & Complexity

How researchers see this paper

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

In Algorithms & Complexity

1. Krzysztof Marcin Choromanski
2. Adrian Weller
3. Tamás Sarlós
4. David Belanger
5. Lucy J. Colwell
6. Jared Davis
7. Xingyou Song
8. David Dohan

Citations in the corpus

• Rethinking Attention with Performers (2020, methodology): “Unidirectional FAVOR+ using fast prefix-sum pre-computation in parallel (Ladner & Fischer, 1980; Cormen et al., 2009) has O(mLd) space complexity to store GPS which can be reduced to O(md+ Ld+mL) by running a simple (though non-parallel in L) aggregation of GPSi,:,: without storing the whole tensor…”
• Sub-Linear Memory: How to Make Performers SLiM (2020, methodology): “Alternatively, [11] employ a parallel prefix-sum algorithm [21, 39], which, for a tensor Z ∈ RL×.”