Sequence in computer science
In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers "x"0, "x"1, "x"2, ... is a second sequence of numbers "y"0, "y"1, "y"2, ..., the sums of prefixes (running totals) of the input sequence:
"y"0 = "x"0
"y"1 = "x"0 + "x"1
"y"2 = "x"0 + "x"1+ "x"2
For instance, the prefix sums of the natural numbers are the triangular numbers:
Prefix sums are trivial to compute in sequential models of computation, by using the formula "yi" = "y""i" − 1 + "xi" to compute each output value in sequence order. However, despite their ease of computation, prefix sums are a useful primitive in certain algorithms such as counting sort,
and they form the basis of the scan higher-order function in functional programming languages. Prefix sums have also been much studied in parallel algorithms, both as a test problem to be solved and as a useful primitive to be used as a subroutine in other parallel algorithms.
Abstractly, a prefix sum requires only a binary associative operator ⊕, making it useful for many applications from calculating well-separated pair decompositions of points to string processing.
Mathematically, the operation of taking prefix sums can be generalized from finite to infinite sequences; in that context, a prefix sum is known as a partial sum of a series. Prefix summation or partial summation form linear operators on the vector spaces of finite or infinite sequences; their inverses are finite difference operators.
Scan higher order function.
In functional programming terms, the prefix sum may be generalized to any binary operation (not just the addition operation); the higher order function resulting from this generalization is called a scan, and it is closely related to the fold operation. Both the scan and the fold operations apply the given binary operation to the same sequence of values, but differ in that the scan returns the whole sequence of results from the binary operation, whereas the fold returns only the final result. For instance, the sequence of factorial numbers may be generated by a scan of the natural numbers using multiplication instead of addition:
Inclusive and exclusive scans.
Programming language and library implementations of scan may be either "inclusive" or "exclusive". An inclusive scan includes input "x""i" when computing output "y""i" (i.e., formula_1) while an exclusive scan does not (i.e., formula_2). In the latter case, implementations either leave "y"0 undefined or accept a separate ""x"−1" value with which to seed the scan. Either type of scan can be transformed into the other: an inclusive scan can be transformed into an exclusive scan by shifting the array produced by the scan right by one element and inserting the identity value at the left of the array. Conversely, an exclusive scan be transformed into an inclusive scan by shifting the array produced by the scan left and inserting the sum of the last element of the scan and the last element of the input array at the right of the array.
The following table lists examples of the inclusive and exclusive scan functions provided by a few programming languages and libraries:
The directive-based OpenMP parallel programming model supports both inclusive and exclusive scan support beginning with Version 5.0.
Parallel algorithms.
There are two key algorithms for computing a prefix sum in parallel. The first offers a shorter span and more parallelism but is not work-efficient. The second is work-efficient but requires double the span and offers less parallelism. These are presented in turn below.
Algorithm 1: Shorter span, more parallel.
Hillis and Steele present the
following parallel prefix sum algorithm:
 for "i" ;- 0 to floor(log2("n")) do
 for "j" ;- 0 to "n" - 1 do in parallel
 if "j" ; 2"i" then
 "x" ;- "x"
 else
 "x" ;- "x" + "x"
In the above, the notation formula_3 means the value of the "j"th element of array "x" in timestep "i".
With a single processor this algorithm would run in "O"("n" log "n") time. However if the machine has at least "n" processors to perform the inner loop in parallel, the algorithm as a whole runs in "O"(log "n") time, the number of iterations of the outer loop.
Algorithm 2: Work-efficient.
A work-efficient parallel prefix sum can be computed by the following steps.
If the input sequence has n steps, then the recursion continues to a depth of "O"(log "n"), which is also the bound on the parallel running time of this algorithm. The number of steps of the algorithm is "O"("n"), and it can be implemented on a parallel random access machine with "O"("n"/log "n") processors without any asymptotic slowdown by assigning multiple indices to each processor in rounds of the algorithm for which there are more elements than processors.
Discussion.
Each of the preceding algorithms runs in "O"(log "n") time. However, the former takes exactly log2 "n" steps, while the latter requires 2 log2 "n" − 2 steps. For the 16-input examples illustrated, Algorithm 1 is 12-way parallel (49 units of work divided by a span of 4) while Algorithm 2 is only 4-way parallel (26 units of work divided by a span of 6). However, Algorithm 2 is work-efficient—it performs only a constant factor (2) of the amount of work required by the sequential algorithm—while Algorithm 1 is work-inefficient—it performs asymptotically more work (a logarithmic factor) than is required sequentially. Consequently, Algorithm 1 is likely to perform better when abundant parallelism is available, but Algorithm 2 is likely to perform better when parallelism is more limited.
Parallel algorithms for prefix sums can often be generalized to other scan operations on associative binary operations, and they can also be computed efficiently on modern parallel hardware such as a GPU. The idea of building in hardware a functional unit dedicated to computing multi-parameter prefix-sum was patented by Uzi Vishkin.
Many parallel implementations follow a two pass procedure where partial prefix sums are calculated in the first pass on each processing unit; the prefix sum of these partial sums is then calculated and broadcast back to the processing units for a second pass using the now known prefix as the initial value. Asymptotically this method takes approximately two read operations and one write operation per item.
Concrete implementations of prefix sum algorithms.
An implementation of a parallel prefix sum algorithm, like other parallel algorithms, has to take the parallelization architecture of the platform into account. More specifically, multiple algorithms exist which are adapted for platforms working on shared memory as well as algorithms which are well suited for platforms using distributed memory, relying on message passing as the only form of interprocess communication.
Shared memory: Two-level algorithm.
The following algorithm assumes a shared memory machine model; all processing elements (PEs) have access to the same memory. A version of this algorithm is implemented in the Multi-Core Standard Template Library (MCSTL), a parallel implementation of the C++ standard template library which provides adapted versions for parallel computing of various algorithms.
In order to concurrently calculate the prefix sum over n data elements with p processing elements, the data is divided into formula_4 blocks, each containing formula_5 elements (for simplicity we assume that formula_4 divides n). Note, that although the algorithm divides the data into formula_4 blocks, only p processing elements run in parallel at a time.
In a first sweep, each PE calculates a local prefix sum for its block. The last block does not need to be calculated, since these prefix sums are only calculated as offsets to the prefix sums of succeeding blocks and the last block is by definition not succeeded.
The p offsets which are stored in the last position of each block are accumulated in a prefix sum of their own and stored in their succeeding positions. For p being a small number, it is faster to do this sequentially, for a large p, this step could be done in parallel as well.
A second sweep is performed. This time the first block does not have to be processed, since it does not need to account for the offset of a preceding block. However, in this sweep the last block is included instead and the prefix sums for each block are calculated taking the prefix sum block offsets calculated in the previous sweep into account.
function prefix_sum(elements) {
 n := size(elements)
 p := number of processing elements
 prefix_sum := [0...0] of size n
 do parallel i = 0 to p-1 {
 // i := index of current PE
 from j = i * n / (p+1) to (i+1) * n / (p+1) - 1 do {
 // This only stores the prefix sum of the local blocks
 store_prefix_sum_with_offset_in(elements, 0, prefix_sum)
 x = 0
 for i = 1 to p { // Serial accumulation of total sum of blocks 
 x += prefix_sum[i * n / (p+1) - 1] // Build the prefix sum over the first p blocks
 prefix_sum[i * n / (p+1)] = x // Save the results to be used as offsets in second sweep
 
 do parallel i = 1 to p {
 // i := index of current PE
 from j = i * n / (p+1) to (i+1) * n / (p+1) - 1 do {
 offset := prefix_sum[i * n / (p+1)]
 // Calculate the prefix sum taking the sum of preceding blocks as offset
 store_prefix_sum_with_offset_in(elements, offset, prefix_sum)
 return prefix_sum
Improvement: In case that the number of blocks are too much that makes the serial step time-consuming by deploying a single processor, the can be used to accelerate the second phase.
Distributed memory: Hypercube algorithm.
The Hypercube Prefix Sum Algorithm is well adapted for distributed memory platforms and works with the exchange of messages between the processing elements. It assumes to have formula_8 processor elements (PEs) participating in the algorithm equal to the number of corners in a d-dimensional hypercube.
Throughout the algorithm, each PE is seen as a corner in a hypothetical hyper cube with knowledge of the total prefix sum formula_9 as well as the prefix sum x of all elements up to itself (according to the ordered indices among the PEs), both in its own hypercube.
In a d-dimensional hyper cube with formula_14 PEs at the corners, the algorithm has to be repeated d times to have the formula_14zero-dimensional hyper cubes be unified into one d-dimensional hyper cube.
Assuming a duplex communication model where the formula_9 of two adjacent PEs in different hyper cubes can be exchanged in both directions in one communication step, this means formula_17 communication startups.
i := Index of own processor element (PE)
m := prefix sum of local elements of this PE
d := number of dimensions of the hyper cube
x = m; // Invariant: The prefix sum up to this PE in the current sub cube
σ = m; // Invariant: The prefix sum of all elements in the current sub cube
for (k=0; k ;= d-1; k++) {
 y = σ @ PE(i xor 2^k) // Get the total prefix sum of the opposing sub cube along dimension k
 σ = σ + y // Aggregate the prefix sum of both sub cubes
 if (i &amp; 2^k) {
 x = x + y // Only aggregate the prefix sum from the other sub cube, if this PE is the higher index one.
Large message sizes: pipelined binary tree.
The Pipelined Binary Tree Algorithm is another algorithm for distributed memory platforms which is specifically well suited for large message sizes.
Like the hypercube algorithm, it assumes a special communication structure. The processing elements (PEs) are hypothetically arranged in a binary tree (e.g. a Fibonacci Tree) with infix numeration according to their index within the PEs. Communication on such a tree always occurs between parent and child nodes.
The infix numeration ensures that for any given PEj, the indices of all nodes reachable by its left subtree formula_18 are less than j and the indices formula_19 of all nodes in the right subtree are greater than j. The parent's index is greater than any of the indices in PEj's subtree if PEj is a left child and smaller if PEj is a right child. 
This allows for the following reasoning:
Note the distinction between subtree-local and total prefix sums. The points two, three and four can lead to believe they would form a circular dependency, but this is not the case. Lower level PEs might require the total prefix sum of higher level PEs to calculate their total prefix sum, but higher level PEs only require subtree local prefix sums to calculate their total prefix sum. The root node as highest level node only requires