Prefix Sum - Parallel Algorithm

Parallel Algorithm

A prefix sum can be calculated in parallel by the following steps.

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.

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. 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.