{"history":[],"article":{"id":"9f8a8978-0971-420d-a61b-e894e908694d","title":"Prefix sum","slug":"prefix-sum","content":":::summary\n:::\n\n# \nIn [computer science](https://bliptext.com/articles/computer-science), the **prefix sum**, **cumulative sum**, **inclusive **scan****, or simply **scan** of a sequence of numbers\nx0, x1, x2, ...\nis a second sequence of numbers\ny0, y1, y2, ...\n, the [sums](https://bliptext.com/articles/summation) of [prefixes](https://bliptext.com/articles/prefix-computer-science) ([running totals](https://bliptext.com/articles/running-total)) of the input sequence:\ny0 = x0\ny1 = x0 + x1\ny2 = x0 + x1+ x2\nFor instance, the prefix sums of the [natural numbers](https://bliptext.com/articles/natural-number) are the [triangular numbers](https://bliptext.com/articles/triangular-number):\n!input numbers\n!prefix sums\nPrefix sums are trivial to compute in sequential models of computation, by using the formula\nyi = yi − 1 + xi\nto compute each output value in sequence order.\nHowever, despite their ease of computation, prefix sums are a useful primitive in certain algorithms such as [counting sort](https://bliptext.com/articles/counting-sort),\nand they form the basis of the **scan** higher-order function in [functional programming](https://bliptext.com/articles/functional-programming) languages.\nPrefix sums have also been much studied in [parallel algorithms](https://bliptext.com/articles/parallel-algorithm), both as a test problem to be solved and as a useful primitive to be used as a subroutine in other [parallel algorithms](https://bliptext.com/articles/parallel-algorithm).\nAbstractly, a prefix sum requires only a [binary associative operator ⊕](https://bliptext.com/articles/semigroup), making it useful for many applications from calculating [well-separated pair decompositions](https://bliptext.com/articles/well-separated-pair-decomposition) of points to string processing.\nMathematically, 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](https://bliptext.com/articles/partial-sum) of a [series](https://bliptext.com/articles/series-mathematics).\nPrefix summation or partial summation form [linear operators](https://bliptext.com/articles/linear-operator) on the [vector spaces](https://bliptext.com/articles/vector-space) of finite or infinite sequences; their inverses are [finite difference](https://bliptext.com/articles/finite-difference) operators.\n\n# Scan higher order function\nIn [functional programming](https://bliptext.com/articles/functional-programming) terms, the prefix sum may be generalized to any binary operation (not just the [addition](https://bliptext.com/articles/addition) operation); the [higher order function](https://bliptext.com/articles/higher-order-function) resulting from this generalization is called a **scan**, and it is closely related to the [fold](https://bliptext.com/articles/fold-higher-order-function) operation.\nBoth 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.\nFor instance, the sequence of [factorial](https://bliptext.com/articles/factorial) numbers may be generated by a scan of the natural numbers using multiplication instead of addition:\n!input numbers\n!prefix products\n\n## Inclusive and exclusive scans\nProgramming language and library implementations of scan may be either inclusive or exclusive.\nAn inclusive scan includes input\nxi\nwhen computing output\nyi\n(i.e., ) while an exclusive scan does not (i.e., ).\nIn the latter case, implementations either leave\ny0\nundefined or accept a separate \"\nx−1\n\" 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.\nThe following table lists examples of the inclusive and exclusive scan functions provided by a few programming languages and libraries:\nThe directive-based [OpenMP](https://bliptext.com/articles/openmp) parallel programming model supports both inclusive and exclusive scan support beginning with Version 5.0.\n\n# Parallel algorithms\nThere are two key algorithms for computing a prefix sum in parallel.\nThe first offers a shorter [span](https://bliptext.com/articles/analysis-of-parallel-algorithms) and more [parallelism](https://bliptext.com/articles/analysis-of-parallel-algorithms) but is not work-efficient.\nThe second is work-efficient but requires double the span and offers less parallelism.\nThese are presented in turn below.\n\n## Algorithm 1: Shorter span, more parallel\n[Hillis](https://bliptext.com/articles/danny-hillis) and [Steele](https://bliptext.com/articles/guy-l-steele-jr) present the\nfollowing parallel prefix sum algorithm:\n**for** i <- 0 to floor(log2(n)) **do**\n**for** j <- 0 to n - 1 **do in parallel**\n**if** j < 2i **then**\nxi+1 j <- xi j **else**\nxi+1 j <- xi j + xi j - 2i\nIn the above, the notation x^i_j means the value of the\nj\nth element of array\nx\nin timestep\ni\n.\nWith a single processor this algorithm would run in\nO(n log n)\ntime.\nHowever if the machine has at least\nn\nprocessors to perform the inner loop in parallel, the algorithm as a whole runs in\nO(log n)\ntime, the number of iterations of the outer loop.\n# [Circuit representation of a highly parallel 16-input parallel prefix sum | upload.wikimedia.org/wikipedia/commons/e/ec/Hillis-Steele///Prefix///Sum.svg]\n\n## Algorithm 2: Work-efficient\nA work-efficient parallel prefix sum can be computed by the following steps.\nz0 = x0 + x1\n,\nz1 = x2 + x3\n, etc.\nw0, w1, w2, ...\nof the sequence\nz0, z1, z2, ...\ny0, y1, y2, ...\nas the sum of up to two terms of these intermediate sequences:\ny0 = x0\n,\ny1 = z0\n,\ny2 = z0 + x2\n,\ny3 = w1\n, etc. After the first value, each successive number\nyi\nis 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.\nIf the input sequence has n steps, then the recursion continues to a depth of\nO(log n)\n, which is also the bound on the parallel running time of this algorithm.\nThe number of steps of the algorithm is\nO(n)\n, and it can be implemented on a [parallel random access machine](https://bliptext.com/articles/parallel-random-access-machine) with\nO(n/log n)\nprocessors without any asymptotic slowdown by assigning multiple indices to each processor in rounds of the algorithm for which there are more elements than processors.\n# [Circuit representation of a work-efficient 16-input parallel prefix sum | upload.wikimedia.org/wikipedia/commons/8/81/Prefix///sum///16.svg]\n\n## Discussion\nEach of the preceding algorithms runs in\nO(log n)\ntime.\nHowever, the former takes exactly\nlog2 n\nsteps, while the latter requires\n2 log2 n − 2\nsteps.\nFor the 16-input examples illustrated, Algorithm 1 is 12-way parallel (49 units of work divided by a span of 4) while Algorithm 2 is only 4-way parallel (26 units of work divided by a span of 6).\nHowever, Algorithm 2 is work-efficient—it performs only a constant factor (2) of the amount of work required by the sequential algorithm—while Algorithm 1 is work-inefficient—it performs asymptotically more work (a logarithmic factor) than is required sequentially.\nConsequently, Algorithm 1 is likely to perform better when abundant parallelism is available, but Algorithm 2 is likely to perform better when parallelism is more limited.\nParallel algorithms for prefix sums can often be generalized to other scan operations on [associative binary operations](https://bliptext.com/articles/associative-property), and they can also be computed efficiently on modern parallel hardware such as a [GPU](https://bliptext.com/articles/gpu).\nThe idea of building in hardware a functional unit dedicated to computing multi-parameter prefix-sum was patented by [Uzi Vishkin](https://bliptext.com/articles/uzi-vishkin).\nMany 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.\nAsymptotically this method takes approximately two read operations and one write operation per item.\n\n## Concrete implementations of prefix sum algorithms\nAn implementation of a parallel prefix sum algorithm, like other parallel algorithms, has to take the [parallelization architecture](https://bliptext.com/articles/parallel-programming-model) of the platform into account.\nMore specifically, multiple algorithms exist which are adapted for platforms working on [shared memory](https://bliptext.com/articles/shared-memory) as well as algorithms which are well suited for platforms using [distributed memory](https://bliptext.com/articles/distributed-memory), relying on [message passing](https://bliptext.com/articles/message-passing) as the only form of interprocess communication.\n\n### Shared memory: Two-level algorithm\nThe following algorithm assumes a [shared memory](https://bliptext.com/articles/shared-memory) machine model; all processing elements (PEs) have access to the same memory.\nA version of this algorithm is implemented in the Multi-Core Standard Template Library (MCSTL), a parallel implementation of the [C++ standard template library](https://bliptext.com/articles/standard-template-library) which provides adapted versions for [parallel computing](https://bliptext.com/articles/parallel-computing) of various algorithms.\nIn order to concurrently calculate the prefix sum over n data elements with p processing elements, the data is divided into p+1 blocks, each containing elements (for simplicity we assume that p+1 divides n).\nNote, that although the algorithm divides the data into p+1 blocks, only p processing elements run in parallel at a time.\nIn a first sweep, each PE calculates a local prefix sum for its block.\nThe last block does not need to be calculated, since these prefix sums are only calculated as offsets to the prefix sums of succeeding blocks and the last block is by definition not succeeded.\nThe p offsets which are stored in the last position of each block are accumulated in a prefix sum of their own and stored in their succeeding positions.\nFor p being a small number, it is faster to do this sequentially, for a large p, this step could be done in parallel as well.\nA second sweep is performed.\nThis time the first block does not have to be processed, since it does not need to account for the offset of a preceding block.\nHowever, in this sweep the last block is included instead and the prefix sums for each block are calculated taking the prefix sum block offsets calculated in the previous sweep into account.\n**Improvement:** In case that the number of blocks are too much that makes the serial step time-consuming by deploying a single processor, the [Hillis and Steele algorithm](https://bliptext.com/articles/) can be used to accelerate the second phase.\n\n### Distributed memory: Hypercube algorithm\nThe Hypercube Prefix Sum Algorithm is well adapted for [distributed memory](https://bliptext.com/articles/distributed-memory) platforms and works with the exchange of messages between the processing elements.\nIt assumes to have p=2^d processor elements (PEs) participating in the algorithm equal to the number of corners in a d-dimensional [hypercube](https://bliptext.com/articles/hypercube-internetwork-topology).\nThroughout the algorithm, each PE is seen as a corner in a hypothetical hyper cube with knowledge of the total prefix sum \\sigma as well as the prefix sum x of all elements up to itself (according to the ordered indices among the PEs), both in its own hypercube.\nIn a d-dimensional hyper cube with 2^d PEs at the corners, the algorithm has to be repeated d times to have the 2^dzero-dimensional hyper cubes be unified into one d-dimensional hyper cube.\nAssuming a [duplex communication](https://bliptext.com/articles/duplex-telecommunications) model where the \\sigma of two adjacent PEs in different hyper cubes can be exchanged in both directions in one communication step, this means d=\\log_2 p communication startups.\n# [Different hypercubes for varying number of nodes | upload.wikimedia.org/wikipedia/commons/3/34/Hypercube-construction-4d.png]\n\n### Large message sizes: pipelined binary tree\nThe Pipelined Binary Tree Algorithm is another algorithm for distributed memory platforms which is specifically well suited for large message sizes.\nLike the hypercube algorithm, it assumes a special communication structure.\nThe processing elements (PEs) are hypothetically arranged in a [binary tree](https://bliptext.com/articles/binary-tree) (e.g. a Fibonacci Tree) with [infix numeration](https://bliptext.com/articles/tree-traversal) according to their index within the PEs.\nCommunication on such a tree always occurs between parent and child nodes.\nThe [infix numeration](https://bliptext.com/articles/tree-traversal) ensures that for any given PEj, the indices of all nodes reachable by its left subtree are less than j and the indices of all nodes in the right subtree are greater than j. The parent's index is greater than any of the indices in PEj's subtree if PEj is a left child and smaller if PEj is a right child.\nThis allows for the following reasoning:\nNote the distinction between subtree-local and total prefix sums.\nThe points two, three and four can lead to believe they would form a circular dependency, but this is not the case.\nLower level PEs might require the total prefix sum of higher level PEs to calculate their total prefix sum, but higher level PEs only require subtree local prefix sums to calculate their total prefix sum.\nThe root node as highest level node only requires the local prefix sum of its left subtree to calculate its own prefix sum.\nEach PE on the path from PE0 to the root PE only requires the local prefix sum of its left subtree to calculate its own prefix sum, whereas every node on the path from PEp-1 (last PE) to the PEroot requires the total prefix sum of its parent to calculate its own total prefix sum.\nThis leads to a two-phase algorithm:\n**Upward Phase** Propagate the subtree local prefix sum to its parent for each PEj.\n**Downward phase** Propagate the exclusive (exclusive PEj as well as the PEs in its left subtree) total prefix sum of all lower index PEs which are not included in the addressed subtree of PEj to lower level PEs in the left child subtree of PEj.\nPropagate the inclusive prefix sum to the right child subtree of PEj.\nNote that the algorithm is run in parallel at each PE and the PEs will block upon receive until their children/parents provide them with packets.\n# [Information exchange between processing elements during upward (blue) and downward (red) phase in the Pipelined Binary Tree Prefix Sum algorithm. | upload.wikimedia.org/wikipedia/commons/2/2d/Pipelined///Binary///Tree///Prefix///Sum///Communication.png]\n\n#### Pipelining\nIf the message m of length n can be divided into k packets and the operator ⨁ can be used on each of the corresponding message packets separately, [pipelining](https://bliptext.com/articles/pipeline-computing) is possible.\nIf the algorithm is used without pipelining, there are always only two levels (the sending PEs and the receiving PEs) of the binary tree at work while all other PEs are waiting.\nIf there are p processing elements and a balanced binary tree is used, the tree has \\log _{2}p levels, the length of the path from PE_0 to is therefore which represents the maximum number of non parallel communication operations during the upward phase, likewise, the communication on the downward path is also limited to startups.\nAssuming a communication startup time of and a bytewise transmission time of, upward and downward phase are limited to in a non pipelined scenario.\nUpon division into k packets, each of size and sending them separately, the first packet still needs to be propagated to as part of a local prefix sum and this will occur again for the last packet if.\nHowever, in between, all the PEs along the path can work in parallel and each third communication operation (receive left, receive right, send to parent) sends a packet to the next level, so that one phase can be completed in communication operations and both phases together need which is favourable for large message sizes n.\nThe algorithm can further be optimised by making use of [full-duplex or telephone model](https://bliptext.com/articles/duplex-telecommunications) communication and overlapping the upward and the downward phase.\n\n# Data structures\nWhen a data set may be updated dynamically, it may be stored in a [Fenwick tree](https://bliptext.com/articles/fenwick-tree) data structure.\nThis structure allows both the lookup of any individual prefix sum value and the modification of any array value in logarithmic time per operation.\nHowever, an earlier 1982 paper presents a data structure called Partial Sums Tree (see Section 5.1) that appears to overlap Fenwick trees; in 1982 the term prefix-sum was not yet as common as it is today.\nFor higher-dimensional arrays, the [summed area table](https://bliptext.com/articles/summed-area-table) provides a data structure based on prefix sums for computing sums of arbitrary rectangular subarrays.\nThis can be a helpful primitive in [image convolution](https://bliptext.com/articles/kernel-image-processing) operations.\n\n# Applications\n[Counting sort](https://bliptext.com/articles/counting-sort) is an [integer sorting](https://bliptext.com/articles/integer-sorting) algorithm that uses the prefix sum of a [histogram](https://bliptext.com/articles/histogram) of key frequencies to calculate the position of each key in the sorted output array.\nIt runs in linear time for integer keys that are smaller than the number of items, and is frequently used as part of [radix sort](https://bliptext.com/articles/radix-sort), a fast algorithm for sorting integers that are less restricted in magnitude.\n[List ranking](https://bliptext.com/articles/list-ranking), the problem of transforming a [linked list](https://bliptext.com/articles/linked-list) into an [array](https://bliptext.com/articles/array-data-structure) 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](https://bliptext.com/articles/array-data-structure) position given by its prefix sum value; by combining list ranking, prefix sums, and [Euler tours](https://bliptext.com/articles/euler-tour), many important problems on [trees](https://bliptext.com/articles/tree-graph-theory) may be solved by efficient parallel algorithms.\nAn early application of parallel prefix sum algorithms was in the design of [binary adders](https://bliptext.com/articles/adder-electronics), Boolean circuits that can add two n-bit binary numbers.\nIn this application, the sequence of carry bits of the addition can be represented as a scan operation\non the sequence of pairs of input bits, using the [majority function](https://bliptext.com/articles/majority-function) to combine the previous carry with these two bits.\nEach bit of the output number can then be found as the [exclusive or](https://bliptext.com/articles/exclusive-or) of two input bits with the corresponding carry bit.\nBy using a circuit that performs the operations of the parallel prefix sum algorithm, it is possible to design an adder that uses\nO(n)\nlogic gates and\nO(log n)\ntime steps.\nIn the [parallel random access machine](https://bliptext.com/articles/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.\nBy means of a [sorting network](https://bliptext.com/articles/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.\nIn [Guy Blelloch](https://bliptext.com/articles/guy-e-blelloch)'s Ph.D. thesis, parallel prefix operations form part of the formalization of the [data parallelism](https://bliptext.com/articles/data-parallelism) model provided by machines such as the [Connection Machine](https://bliptext.com/articles/connection-machine).\nThe Connection Machine CM-1 and CM-2 provided a [hypercubic](https://bliptext.com/articles/hypercubic) network on which the Algorithm 1 above could be implemented, whereas the CM-5 provided a dedicated network to implement Algorithm 2.\nIn the construction of [Gray codes](https://bliptext.com/articles/gray-code), 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](https://bliptext.com/articles/exclusive-or) of n and n/2 (the number formed by shifting n right by a single bit position).\nThe 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.\nA prefix sum of this type may be performed efficiently using the bitwise Boolean operations available on modern computers, by computing the [exclusive or](https://bliptext.com/articles/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.\nParallel prefix (using multiplication as the underlying associative operation) can also be used to build fast algorithms for parallel [polynomial interpolation](https://bliptext.com/articles/polynomial-interpolation).\nIn particular, it can be used to compute the [divided difference](https://bliptext.com/articles/divided-difference) coefficients of the [Newton form](https://bliptext.com/articles/newton-form) of the interpolation polynomial.\nThis prefix based approach can also be used to obtain the generalized divided differences for (confluent) [Hermite interpolation](https://bliptext.com/articles/hermite-interpolation)\nas well as for parallel algorithms for [Vandermonde](https://bliptext.com/articles/vandermonde) systems.\nPrefix sum is used for [load balancing](https://bliptext.com/articles/load-balancing-computing) as a low-cost algorithm to distribute the work between multiple processors, where the overriding goal is achieving an equal amount of work on each processor.\nThe algorithms uses an array of weights representing the amount of work required for each item.\nAfter the prefix sum is calculated, the work item i is sent for processing to the processor unit with the number.\nGraphically this corresponds to an operation where the amount of work in each item is represented by the length of a linear segment, all segments are sequentially placed onto a line and the result cut into number of pieces, corresponding to the number of the processors.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T08:08:57.721Z","updated_at":"2025-01-26T08:08:57.721Z","search_vector":"'prefix':1 'sum':2","search_content":" \n \n\n# \nIn [computer science](https://bliptext.com/articles/computer-science), the **prefix sum**, **cumulative sum**, **inclusive **scan****, or simply **scan** of a sequence of numbers\nx0, x1, x2, ...\nis a second sequence of numbers\ny0, y1, y2, ...\n, the [sums](https://bliptext.com/articles/summation) of [prefixes](https://bliptext.com/articles/prefix-computer-science) ([running totals](https://bliptext.com/articles/running-total)) of the input sequence:\ny0 = x0\ny1 = x0 + x1\ny2 = x0 + x1+ x2\nFor instance, the prefix sums of the [natural numbers](https://bliptext.com/articles/natural-number) are the [triangular numbers](https://bliptext.com/articles/triangular-number):\n!input numbers\n!prefix sums\nPrefix sums are trivial to compute in sequential models of computation, by using the formula\nyi = yi − 1 + xi\nto compute each output value in sequence order.\nHowever, despite their ease of computation, prefix sums are a useful primitive in certain algorithms such as [counting sort](https://bliptext.com/articles/counting-sort),\nand they form the basis of the **scan** higher-order function in [functional programming](https://bliptext.com/articles/functional-programming) languages.\nPrefix sums have also been much studied in [parallel algorithms](https://bliptext.com/articles/parallel-algorithm), both as a test problem to be solved and as a useful primitive to be used as a subroutine in other [parallel algorithms](https://bliptext.com/articles/parallel-algorithm).\nAbstractly, a prefix sum requires only a [binary associative operator ⊕](https://bliptext.com/articles/semigroup), making it useful for many applications from calculating [well-separated pair decompositions](https://bliptext.com/articles/well-separated-pair-decomposition) of points to string processing.\nMathematically, 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](https://bliptext.com/articles/partial-sum) of a [series](https://bliptext.com/articles/series-mathematics).\nPrefix summation or partial summation form [linear operators](https://bliptext.com/articles/linear-operator) on the [vector spaces](https://bliptext.com/articles/vector-space) of finite or infinite sequences; their inverses are [finite difference](https://bliptext.com/articles/finite-difference) operators.\n\n# Scan higher order function\nIn [functional programming](https://bliptext.com/articles/functional-programming) terms, the prefix sum may be generalized to any binary operation (not just the [addition](https://bliptext.com/articles/addition) operation); the [higher order function](https://bliptext.com/articles/higher-order-function) resulting from this generalization is called a **scan**, and it is closely related to the [fold](https://bliptext.com/articles/fold-higher-order-function) operation.\nBoth 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.\nFor instance, the sequence of [factorial](https://bliptext.com/articles/factorial) numbers may be generated by a scan of the natural numbers using multiplication instead of addition:\n!input numbers\n!prefix products\n\n## Inclusive and exclusive scans\nProgramming language and library implementations of scan may be either inclusive or exclusive.\nAn inclusive scan includes input\nxi\nwhen computing output\nyi\n(i.e., ) while an exclusive scan does not (i.e., ).\nIn the latter case, implementations either leave\ny0\nundefined or accept a separate \"\nx−1\n\" 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.\nThe following table lists examples of the inclusive and exclusive scan functions provided by a few programming languages and libraries:\nThe directive-based [OpenMP](https://bliptext.com/articles/openmp) parallel programming model supports both inclusive and exclusive scan support beginning with Version 5.0.\n\n# Parallel algorithms\nThere are two key algorithms for computing a prefix sum in parallel.\nThe first offers a shorter [span](https://bliptext.com/articles/analysis-of-parallel-algorithms) and more [parallelism](https://bliptext.com/articles/analysis-of-parallel-algorithms) but is not work-efficient.\nThe second is work-efficient but requires double the span and offers less parallelism.\nThese are presented in turn below.\n\n## Algorithm 1: Shorter span, more parallel\n[Hillis](https://bliptext.com/articles/danny-hillis) and [Steele](https://bliptext.com/articles/guy-l-steele-jr) present the\nfollowing parallel prefix sum algorithm:\n**for** i <- 0 to floor(log2(n)) **do**\n**for** j <- 0 to n - 1 **do in parallel**\n**if** j < 2i **then**\nxi+1 j <- xi j **else**\nxi+1 j <- xi j + xi j - 2i\nIn the above, the notation x^i_j means the value of the\nj\nth element of array\nx\nin timestep\ni\n.\nWith a single processor this algorithm would run in\nO(n log n)\ntime.\nHowever if the machine has at least\nn\nprocessors to perform the inner loop in parallel, the algorithm as a whole runs in\nO(log n)\ntime, the number of iterations of the outer loop.\n# [Circuit representation of a highly parallel 16-input parallel prefix sum | upload.wikimedia.org/wikipedia/commons/e/ec/Hillis-Steele///Prefix///Sum.svg]\n\n## Algorithm 2: Work-efficient\nA work-efficient parallel prefix sum can be computed by the following steps.\nz0 = x0 + x1\n,\nz1 = x2 + x3\n, etc.\nw0, w1, w2, ...\nof the sequence\nz0, z1, z2, ...\ny0, y1, y2, ...\nas the sum of up to two terms of these intermediate sequences:\ny0 = x0\n,\ny1 = z0\n,\ny2 = z0 + x2\n,\ny3 = w1\n, etc. After the first value, each successive number\nyi\nis 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.\nIf the input sequence has n steps, then the recursion continues to a depth of\nO(log n)\n, which is also the bound on the parallel running time of this algorithm.\nThe number of steps of the algorithm is\nO(n)\n, and it can be implemented on a [parallel random access machine](https://bliptext.com/articles/parallel-random-access-machine) with\nO(n/log n)\nprocessors without any asymptotic slowdown by assigning multiple indices to each processor in rounds of the algorithm for which there are more elements than processors.\n# [Circuit representation of a work-efficient 16-input parallel prefix sum | upload.wikimedia.org/wikipedia/commons/8/81/Prefix///sum///16.svg]\n\n## Discussion\nEach of the preceding algorithms runs in\nO(log n)\ntime.\nHowever, the former takes exactly\nlog2 n\nsteps, while the latter requires\n2 log2 n − 2\nsteps.\nFor the 16-input examples illustrated, Algorithm 1 is 12-way parallel (49 units of work divided by a span of 4) while Algorithm 2 is only 4-way parallel (26 units of work divided by a span of 6).\nHowever, Algorithm 2 is work-efficient—it performs only a constant factor (2) of the amount of work required by the sequential algorithm—while Algorithm 1 is work-inefficient—it performs asymptotically more work (a logarithmic factor) than is required sequentially.\nConsequently, Algorithm 1 is likely to perform better when abundant parallelism is available, but Algorithm 2 is likely to perform better when parallelism is more limited.\nParallel algorithms for prefix sums can often be generalized to other scan operations on [associative binary operations](https://bliptext.com/articles/associative-property), and they can also be computed efficiently on modern parallel hardware such as a [GPU](https://bliptext.com/articles/gpu).\nThe idea of building in hardware a functional unit dedicated to computing multi-parameter prefix-sum was patented by [Uzi Vishkin](https://bliptext.com/articles/uzi-vishkin).\nMany 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.\nAsymptotically this method takes approximately two read operations and one write operation per item.\n\n## Concrete implementations of prefix sum algorithms\nAn implementation of a parallel prefix sum algorithm, like other parallel algorithms, has to take the [parallelization architecture](https://bliptext.com/articles/parallel-programming-model) of the platform into account.\nMore specifically, multiple algorithms exist which are adapted for platforms working on [shared memory](https://bliptext.com/articles/shared-memory) as well as algorithms which are well suited for platforms using [distributed memory](https://bliptext.com/articles/distributed-memory), relying on [message passing](https://bliptext.com/articles/message-passing) as the only form of interprocess communication.\n\n### Shared memory: Two-level algorithm\nThe following algorithm assumes a [shared memory](https://bliptext.com/articles/shared-memory) machine model; all processing elements (PEs) have access to the same memory.\nA version of this algorithm is implemented in the Multi-Core Standard Template Library (MCSTL), a parallel implementation of the [C++ standard template library](https://bliptext.com/articles/standard-template-library) which provides adapted versions for [parallel computing](https://bliptext.com/articles/parallel-computing) of various algorithms.\nIn order to concurrently calculate the prefix sum over n data elements with p processing elements, the data is divided into p+1 blocks, each containing elements (for simplicity we assume that p+1 divides n).\nNote, that although the algorithm divides the data into p+1 blocks, only p processing elements run in parallel at a time.\nIn a first sweep, each PE calculates a local prefix sum for its block.\nThe last block does not need to be calculated, since these prefix sums are only calculated as offsets to the prefix sums of succeeding blocks and the last block is by definition not succeeded.\nThe p offsets which are stored in the last position of each block are accumulated in a prefix sum of their own and stored in their succeeding positions.\nFor p being a small number, it is faster to do this sequentially, for a large p, this step could be done in parallel as well.\nA second sweep is performed.\nThis time the first block does not have to be processed, since it does not need to account for the offset of a preceding block.\nHowever, in this sweep the last block is included instead and the prefix sums for each block are calculated taking the prefix sum block offsets calculated in the previous sweep into account.\n**Improvement:** In case that the number of blocks are too much that makes the serial step time-consuming by deploying a single processor, the [Hillis and Steele algorithm](https://bliptext.com/articles/) can be used to accelerate the second phase.\n\n### Distributed memory: Hypercube algorithm\nThe Hypercube Prefix Sum Algorithm is well adapted for [distributed memory](https://bliptext.com/articles/distributed-memory) platforms and works with the exchange of messages between the processing elements.\nIt assumes to have p=2^d processor elements (PEs) participating in the algorithm equal to the number of corners in a d-dimensional [hypercube](https://bliptext.com/articles/hypercube-internetwork-topology).\nThroughout the algorithm, each PE is seen as a corner in a hypothetical hyper cube with knowledge of the total prefix sum \\sigma as well as the prefix sum x of all elements up to itself (according to the ordered indices among the PEs), both in its own hypercube.\nIn a d-dimensional hyper cube with 2^d PEs at the corners, the algorithm has to be repeated d times to have the 2^dzero-dimensional hyper cubes be unified into one d-dimensional hyper cube.\nAssuming a [duplex communication](https://bliptext.com/articles/duplex-telecommunications) model where the \\sigma of two adjacent PEs in different hyper cubes can be exchanged in both directions in one communication step, this means d=\\log_2 p communication startups.\n# [Different hypercubes for varying number of nodes | upload.wikimedia.org/wikipedia/commons/3/34/Hypercube-construction-4d.png]\n\n### Large message sizes: pipelined binary tree\nThe Pipelined Binary Tree Algorithm is another algorithm for distributed memory platforms which is specifically well suited for large message sizes.\nLike the hypercube algorithm, it assumes a special communication structure.\nThe processing elements (PEs) are hypothetically arranged in a [binary tree](https://bliptext.com/articles/binary-tree) (e.g. a Fibonacci Tree) with [infix numeration](https://bliptext.com/articles/tree-traversal) according to their index within the PEs.\nCommunication on such a tree always occurs between parent and child nodes.\nThe [infix numeration](https://bliptext.com/articles/tree-traversal) ensures that for any given PEj, the indices of all nodes reachable by its left subtree are less than j and the indices of all nodes in the right subtree are greater than j. The parent's index is greater than any of the indices in PEj's subtree if PEj is a left child and smaller if PEj is a right child.\nThis allows for the following reasoning:\nNote the distinction between subtree-local and total prefix sums.\nThe points two, three and four can lead to believe they would form a circular dependency, but this is not the case.\nLower level PEs might require the total prefix sum of higher level PEs to calculate their total prefix sum, but higher level PEs only require subtree local prefix sums to calculate their total prefix sum.\nThe root node as highest level node only requires the local prefix sum of its left subtree to calculate its own prefix sum.\nEach PE on the path from PE0 to the root PE only requires the local prefix sum of its left subtree to calculate its own prefix sum, whereas every node on the path from PEp-1 (last PE) to the PEroot requires the total prefix sum of its parent to calculate its own total prefix sum.\nThis leads to a two-phase algorithm:\n**Upward Phase** Propagate the subtree local prefix sum to its parent for each PEj.\n**Downward phase** Propagate the exclusive (exclusive PEj as well as the PEs in its left subtree) total prefix sum of all lower index PEs which are not included in the addressed subtree of PEj to lower level PEs in the left child subtree of PEj.\nPropagate the inclusive prefix sum to the right child subtree of PEj.\nNote that the algorithm is run in parallel at each PE and the PEs will block upon receive until their children/parents provide them with packets.\n# [Information exchange between processing elements during upward (blue) and downward (red) phase in the Pipelined Binary Tree Prefix Sum algorithm. | upload.wikimedia.org/wikipedia/commons/2/2d/Pipelined///Binary///Tree///Prefix///Sum///Communication.png]\n\n#### Pipelining\nIf the message m of length n can be divided into k packets and the operator ⨁ can be used on each of the corresponding message packets separately, [pipelining](https://bliptext.com/articles/pipeline-computing) is possible.\nIf the algorithm is used without pipelining, there are always only two levels (the sending PEs and the receiving PEs) of the binary tree at work while all other PEs are waiting.\nIf there are p processing elements and a balanced binary tree is used, the tree has \\log _{2}p levels, the length of the path from PE_0 to is therefore which represents the maximum number of non parallel communication operations during the upward phase, likewise, the communication on the downward path is also limited to startups.\nAssuming a communication startup time of and a bytewise transmission time of, upward and downward phase are limited to in a non pipelined scenario.\nUpon division into k packets, each of size and sending them separately, the first packet still needs to be propagated to as part of a local prefix sum and this will occur again for the last packet if.\nHowever, in between, all the PEs along the path can work in parallel and each third communication operation (receive left, receive right, send to parent) sends a packet to the next level, so that one phase can be completed in communication operations and both phases together need which is favourable for large message sizes n.\nThe algorithm can further be optimised by making use of [full-duplex or telephone model](https://bliptext.com/articles/duplex-telecommunications) communication and overlapping the upward and the downward phase.\n\n# Data structures\nWhen a data set may be updated dynamically, it may be stored in a [Fenwick tree](https://bliptext.com/articles/fenwick-tree) data structure.\nThis structure allows both the lookup of any individual prefix sum value and the modification of any array value in logarithmic time per operation.\nHowever, an earlier 1982 paper presents a data structure called Partial Sums Tree (see Section 5.1) that appears to overlap Fenwick trees; in 1982 the term prefix-sum was not yet as common as it is today.\nFor higher-dimensional arrays, the [summed area table](https://bliptext.com/articles/summed-area-table) provides a data structure based on prefix sums for computing sums of arbitrary rectangular subarrays.\nThis can be a helpful primitive in [image convolution](https://bliptext.com/articles/kernel-image-processing) operations.\n\n# Applications\n[Counting sort](https://bliptext.com/articles/counting-sort) is an [integer sorting](https://bliptext.com/articles/integer-sorting) algorithm that uses the prefix sum of a [histogram](https://bliptext.com/articles/histogram) of key frequencies to calculate the position of each key in the sorted output array.\nIt runs in linear time for integer keys that are smaller than the number of items, and is frequently used as part of [radix sort](https://bliptext.com/articles/radix-sort), a fast algorithm for sorting integers that are less restricted in magnitude.\n[List ranking](https://bliptext.com/articles/list-ranking), the problem of transforming a [linked list](https://bliptext.com/articles/linked-list) into an [array](https://bliptext.com/articles/array-data-structure) 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](https://bliptext.com/articles/array-data-structure) position given by its prefix sum value; by combining list ranking, prefix sums, and [Euler tours](https://bliptext.com/articles/euler-tour), many important problems on [trees](https://bliptext.com/articles/tree-graph-theory) may be solved by efficient parallel algorithms.\nAn early application of parallel prefix sum algorithms was in the design of [binary adders](https://bliptext.com/articles/adder-electronics), Boolean circuits that can add two n-bit binary numbers.\nIn this application, the sequence of carry bits of the addition can be represented as a scan operation\non the sequence of pairs of input bits, using the [majority function](https://bliptext.com/articles/majority-function) to combine the previous carry with these two bits.\nEach bit of the output number can then be found as the [exclusive or](https://bliptext.com/articles/exclusive-or) of two input bits with the corresponding carry bit.\nBy using a circuit that performs the operations of the parallel prefix sum algorithm, it is possible to design an adder that uses\nO(n)\nlogic gates and\nO(log n)\ntime steps.\nIn the [parallel random access machine](https://bliptext.com/articles/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.\nBy means of a [sorting network](https://bliptext.com/articles/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.\nIn [Guy Blelloch](https://bliptext.com/articles/guy-e-blelloch)'s Ph.D. thesis, parallel prefix operations form part of the formalization of the [data parallelism](https://bliptext.com/articles/data-parallelism) model provided by machines such as the [Connection Machine](https://bliptext.com/articles/connection-machine).\nThe Connection Machine CM-1 and CM-2 provided a [hypercubic](https://bliptext.com/articles/hypercubic) network on which the Algorithm 1 above could be implemented, whereas the CM-5 provided a dedicated network to implement Algorithm 2.\nIn the construction of [Gray codes](https://bliptext.com/articles/gray-code), 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](https://bliptext.com/articles/exclusive-or) of n and n/2 (the number formed by shifting n right by a single bit position).\nThe 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.\nA prefix sum of this type may be performed efficiently using the bitwise Boolean operations available on modern computers, by computing the [exclusive or](https://bliptext.com/articles/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.\nParallel prefix (using multiplication as the underlying associative operation) can also be used to build fast algorithms for parallel [polynomial interpolation](https://bliptext.com/articles/polynomial-interpolation).\nIn particular, it can be used to compute the [divided difference](https://bliptext.com/articles/divided-difference) coefficients of the [Newton form](https://bliptext.com/articles/newton-form) of the interpolation polynomial.\nThis prefix based approach can also be used to obtain the generalized divided differences for (confluent) [Hermite interpolation](https://bliptext.com/articles/hermite-interpolation)\nas well as for parallel algorithms for [Vandermonde](https://bliptext.com/articles/vandermonde) systems.\nPrefix sum is used for [load balancing](https://bliptext.com/articles/load-balancing-computing) as a low-cost algorithm to distribute the work between multiple processors, where the overriding goal is achieving an equal amount of work on each processor.\nThe algorithms uses an array of weights representing the amount of work required for each item.\nAfter the prefix sum is calculated, the work item i is sent for processing to the processor unit with the number.\nGraphically this corresponds to an operation where the amount of work in each item is represented by the length of a linear segment, all segments are sequentially placed onto a line and the result cut into number of pieces, corresponding to the number of the processors.","revisionCount":0},"hasMore":false,"nextCursor":null}

History