A Work-Efficient Step-Efficient Prefix Sum Algorithm
Shubhabrata Sengupta, Aaron Lefohn, John D. Owens · eScholarship (California Digital Library) · 2006
The Prefix-sum algorithm [Hillis and Steele Jr. 1986] is one of the most important building blocks for data-parallel computation. Its applications include parallel implementations of deleting marked elements from an array (stream-compaction), radix-sort, solving recurrence equations, solving tri-diagonal linear systems, and quicksort. In addition to being a useful building block, the prefix-sum algorithm is a good example of a computation that seems inherently sequential, but for which there are efficient data-parallel algorithms.