In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x0, x1, x2, ... is a second sequence of numbers y0, y1, y2, ..., the sums of prefixes (running totals) of the input sequence:
y0 = x0 y1 = x0 + x1 y2 = x0 + x1+ x2 ... 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 = yi − 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 xi when computing output yi (i.e., y i = ⨁ j = 0 i x j {\textstyle y_{i}=\bigoplus _{j=0}^{i}x_{j}} ) while an exclusive scan does not (i.e., y i = ⨁ j = 0 i − 1 x j {\textstyle y_{i}=\bigoplus _{j=0}^{i-1}x_{j}} ). In the latter case, implementations either leave y0 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 log2(n) do for j <- 0 to n - 1 do in parallel if j < 2i then xi+1j <- xij else xi+1j <- xij + xij - 2i
In the above, the notation x j i {\displaystyle x_{j}^{i}} means the value of the jth 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.
Compute the sums of consecutive pairs of items in which the first item of the pair has an even index: z0 = x0 + x1, z1 = x2 + x3, etc. Recursively compute the prefix sum w0, w1, w2, ... of the sequence z0, z1, z2, ... Express each term of the final sequence y0, y1, y2, ... as the sum of up to two terms of these intermediate sequences: y0 = x0, y1 = z0, y2 = z0 + x2, y3 = w1, etc. After the first value, each successive number yi is either copied from a position half as far through the w sequence, or is the previous value added to one value in the x sequence. 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.
… excerpt ends here. Continue reading the full article.
