Prefix sum
Encyclopedia
In computer science
, the prefix sum, or scan, of a sequence of numbers is a second sequence of numbers , the sum
s of prefix
es (running total
s) of the input sequence:
In functional programming
terms, the prefix sum is the fold
of the addition
operation. Prefix sums are trivial to compute in sequential models of computation, by using the formula 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
. Prefix sums have also been much studied in parallel algorithm
s, both as a test problem to be solved and as a useful primitive to be used as a subroutine in other parallel algorithms.
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 space
s of finite or infinite sequences; their inverses are finite difference
operators.
If the input sequence has steps, then the recursion continues to a depth of , which is also the bound on the parallel running time of this algorithm. The number of steps of the algorithm is , and it can be implemented on a parallel random access machine
with 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 fold operations, and they can also be computed efficiently on modern parallel hardware such as a GPU.
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.
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.
An early application of parallel prefix sum algorithms was in the design of binary adder
s, Boolean circuits that can add two -bit binary numbers. In this application, the sequence of carry bits of the addition can be represented as a fold operation on pairs of input bits, and 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 logic gates and time steps.
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; fold 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.
In the construction of Gray code
s, sequences of binary values with the property that consecutive sequence values differ from each other in a single bit position, a number can be converted into the Gray code value at position of the sequence simply by taking the exclusive or of and (the number formed by shifting right by a single bit position). The reverse operation, decoding a Gray-coded value into a binary number, is more complicated, but can be expressed as the prefix sum of the bits of , 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 with each of the numbers formed by shifting to the left by a number of bits that is a power of two.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the prefix sum, or scan, of a sequence of numbers is a second sequence of numbers , the sum
SUM
SUM can refer to:* The State University of Management* Soccer United Marketing* Society for the Establishment of Useful Manufactures* StartUp-Manager* Software User’s Manual,as from DOD-STD-2 167A, and MIL-STD-498...
s of prefix
Prefix
A prefix is an affix which is placed before the root of a word. Particularly in the study of languages,a prefix is also called a preformative, because it alters the form of the words to which it is affixed.Examples of prefixes:...
es (running total
Running total
A running total is the summation of a sequence of numbers which is updated each time a new number is added to the sequence, simply by adding the value of the new number to the running total....
s) of the input sequence:
- ...
In functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
terms, the prefix sum is the fold
Fold (higher-order function)
In functional programming, fold – also known variously as reduce, accumulate, compress, or inject – are a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its...
of the addition
Addition
Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....
operation. Prefix sums are trivial to compute in sequential models of computation, by using the formula 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
Counting sort
In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to...
. Prefix sums have also been much studied in parallel algorithm
Parallel algorithm
In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...
s, both as a test problem to be solved and as a useful primitive to be used as a subroutine in other parallel algorithms.
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
Series (mathematics)
A series is the sum of the terms of a sequence. Finite sequences and series have defined first and last terms, whereas infinite sequences and series continue indefinitely....
. Prefix summation or partial summation form linear operators on the vector space
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
s of finite or infinite sequences; their inverses are finite difference
Finite difference
A finite difference is a mathematical expression of the form f − f. If a finite difference is divided by b − a, one gets a difference quotient...
operators.
Parallel algorithm
A prefix sum can be calculated in parallel by the following steps.- Compute the sums of consecutive pairs of items in which the first item of the pair has an even index: , , etc.
- Recursively compute the prefix sum of the sequence
- Expand each term of the sequence into two terms of the overall prefix sum: , , , , etc. After the first value, each successive number is either copied from a position half as far through the sequence, or is the previous value added to one value in the sequence.
If the input sequence has steps, then the recursion continues to a depth of , which is also the bound on the parallel running time of this algorithm. The number of steps of the algorithm is , and it can be implemented on a parallel random access machine
Parallel Random Access Machine
In computer science, Parallel Random Access Machine is a shared memory abstract machine. As its name indicates, the PRAM was intended as the parallel computing analogy to the random access machine...
with 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 fold operations, and they can also be computed efficiently on modern parallel hardware such as a GPU.
Applications
Counting sortCounting sort
In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to...
is an integer sorting
Integer sorting
In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by numeric keys, each of which is an integer. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers or text strings...
algorithm that uses the prefix sum of a histogram
Histogram
In statistics, a histogram is a graphical representation showing a visual impression of the distribution of data. It is an estimate of the probability distribution of a continuous variable and was first introduced by Karl Pearson...
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
Radix sort
In computer science, radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value...
, a fast algorithm for sorting integers that are less restricted in magnitude.
List ranking, the problem of transforming a linked list
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
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
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
may be solved by efficient parallel algorithms.
An early application of parallel prefix sum algorithms was in the design of binary adder
Adder (electronics)
In electronics, an adder or summer is a digital circuit that performs addition of numbers.In many computers and other kinds of processors, adders are used not only in the arithmetic logic unit, but also in other parts of the processor, where they are used to calculate addresses, table indices, and...
s, Boolean circuits that can add two -bit binary numbers. In this application, the sequence of carry bits of the addition can be represented as a fold operation on pairs of input bits, and 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 logic gates and time steps.
In the parallel random access machine
Parallel Random Access Machine
In computer science, Parallel Random Access Machine is a shared memory abstract machine. As its name indicates, the PRAM was intended as the parallel computing analogy to the 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
Sorting network
A sorting network is an abstract mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sorts the values by outputting the smaller value to one wire, and the larger to the other...
, 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; fold 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.
In the construction of Gray code
Gray code
The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit. It is a non-weighted code....
s, sequences of binary values with the property that consecutive sequence values differ from each other in a single bit position, a number can be converted into the Gray code value at position of the sequence simply by taking the exclusive or of and (the number formed by shifting right by a single bit position). The reverse operation, decoding a Gray-coded value into a binary number, is more complicated, but can be expressed as the prefix sum of the bits of , 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 with each of the numbers formed by shifting to the left by a number of bits that is a power of two.