Prefix sum

In computer science, the prefix sum, of a sequence of numbers x₀, x₁, x₂, ... is a second sequence of numbers y₀, y₁, y₂, ..., the sums of prefixes (running totals) of the input sequence:

y₀ = x₀

y₁ = x₀ + x₁

y₂ = x₀ + x₁+ x₂

...

Prefix sums are trivial to compute in sequential models of computation, by using the formula y_i = y_{i − 1} + x_i to compute each number in the prefix sum in sequence. However, despite their ease of computation, prefix sums are a useful primitive in certain algorithms such as counting sort,^[1] 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.^[2][3]

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.

Functional programming

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. For instance, in Haskell, there are two variants of scan, called scanl and scanl1, differing slightly in their argument signature, and the prefix sum operation may be written scanl1 (+). The corresponding suffix operations are also available as scanr and scanr1.^[4] 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.

Parallel algorithm

Circuit representation of a 16-input parallel prefix sum

A prefix sum can be calculated in parallel by the following steps.^[2][5][6]

1. Compute the sums of consecutive pairs of items in which the first item of the pair has an even index: z₀ = x₀ + x₁, z₁ = x₂ + x₃, etc.
2. Recursively compute the prefix sum w₀, w₁, w₂, ... of the sequence z₀, z₁, z₂, ...
3. Expand each term of the sequence w₀, w₁, w₂, ... into two terms of the overall prefix sum: y₀ = x₀, y₁ = w₀, y₂ = w₀ + x₂, y₃ = w₁, etc. After the first value, each successive number y_i 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.^[2]

Parallel algorithms for prefix sums can often be generalized to other scan operations on associative binary operations,^[2][3] and they can also be computed efficiently on modern parallel hardware such as a GPU.^[7]

Applications

Counting sort is an integer sorting algorithm that uses the prefix sum of a histogram of key frequencies to calculate the position of each key in the sorted output array. It runs in linear time for integer keys that are smaller than the number of items, and is frequently used as part of radix sort, a fast algorithm for sorting integers that are less restricted in magnitude.^[1]

List ranking, the problem of transforming a linked list into an array that represents the same sequence of items, can be viewed as computing a prefix sum on the sequence 1, 1, 1, ... and then mapping each item to the array position given by its prefix sum value; by combining list ranking, prefix sums, and Euler tours, many important problems on trees may be solved by efficient parallel algorithms.^[3]

An early application of parallel prefix sum algorithms was in the design of binary adders, Boolean circuits that can add two n-bit binary numbers. In this application, the sequence of carry bits of the addition can be represented as a scan operation on the sequence of pairs of input bits, using the majority function to combine the previous carry with these two bits. Each bit of the output number can then be found as the exclusive or of two input bits with the corresponding carry bit. By using a circuit that performs the operations of the parallel prefix sum algorithm, it is possible to design an adder that uses O(n) logic gates and O(log n) time steps.^[2][5][6]

In the parallel random access machine model of computing, prefix sums can be used to simulate parallel algorithms that assume the ability for multiple processors to access the same memory cell at the same time, on parallel machines that forbid simultaneous access. By means of a sorting network, a set of parallel memory access requests can be ordered into a sequence such that accesses to the same cell are contiguous within the sequence; scan operations can then be used to determine which of the accesses succeed in writing to their requested cells, and to distribute the results of memory read operations to multiple processors that request the same result.^[8]

In the construction of Gray codes, sequences of binary values with the property that consecutive sequence values differ from each other in a single bit position, a number n can be converted into the Gray code value at position n of the sequence simply by taking the exclusive or of n and n/2 (the number formed by shifting n right by a single bit position). The reverse operation, decoding a Gray-coded value x into a binary number, is more complicated, but can be expressed as the prefix sum of the bits of x, where each summation operation within the prefix sum is performed modulo two. A prefix sum of this type may be performed efficiently using the bitwise Boolean operations available on modern computers, by computing the exclusive or of x with each of the numbers formed by shifting x to the left by a number of bits that is a power of two.^[9]

References