Prefix sum

The prefix sum (also known as the scan, prefix reduction, or partial sum) is an operation on lists in which each element in the result list is obtained from the sum of the elements in the operand list up to its index. There are two types of prefix sum, inclusive prefix sum and exclusive prefix sum: in the inclusive prefix sum, all the operand elements are used; whereas in the exclusive prefix sum, the first element in the result list is the identity element (0 for add operation) and the last element of the operand list is not used.

Formulae

Inclusive prefix sum:$r\; =\; [a\_0,\; a\_0+a\_1,\; a\_0+a\_1+a\_2,\; ...,\; a\_0+a\_1+a\_2+...+a\_\{n\}]$

Exclusive prefix sum:$r\; =\; [I,\; a\_0,\; a\_0+a\_1,\; a\_0+a\_1+a\_2,\; ...,\; a\_0+a\_1+a\_2+...+a\_\{n-1\}]$

Message Passing Interface

Scans may be performed with any associative operation applicable to the elements of the list. As an example, the operations defined by the MPI standard are:

In this case, the constants are used with the "MPI_Scan" function.

See also

* Data parallelism
* Fold (higher-order function)
* List ranking

External links

* [http://graphics.idav.ucdavis.edu/publications/print_pub?pub_id=915 Scan Primitives for GPU Computing]