CMU-CS-90-190, November 1990.

**Abstract:**
Experienced algorithm designers rely heavily on a set of building blocks
and on the tools needed to put the blocks together into an algorithm.
The understanding of these basic blocks and tools is therefore critical
to the understanding of algorithms. Many of the blocks and tools needed
for parallel algorithms extend from sequential algorithms, such as
dynamic-programming and divide-and-conquer, but others are new. This
paper introduces one of the simplest and most useful building blocks for
parallel algorithms: the all-prefix-sums operation. The paper defines
the operation, shows how to implement it on a PRAM and illustrates many
applications of the operation. In addition to being a useful building
block, the all-prefix-sums operation is a good example of a computation
that seems inherently sequential, but for which there is an efficient
parallel algorithm.

@techreport{BlellochTR90, author = "Guy~E. Blelloch", title = "Prefix Sums and Their Applications", institution = "School of Computer Science, Carnegie Mellon University", number = "CMU-CS-90-190", month = nov, year = 1990 }