Definition: Calculate an associative function, f, on all prefixes of an n-element array, that is, s, f(s, s), f(s, f(s, s)), ..., f(s, f(s, ... f(s[n-2], s[n-1])...)), using Θ(n) processors in Θ(log n) time. The algorithm is
for j := 0 to lg(n)-1 dowhere lg is the logarithm base 2, and parallel-do does the innermost computations in parallel.
for i := 2j to n-1 parallel-do
s[i] := f(s[i-2j], s[i])
In particular, this calculates any associative function, such as sum, maximum, or concatenate, over a list of values in logarithmic time. Note the write-after-read hazards in the parallel-do loop: old values of s[2j] to s[n-1-2j] must be read before being overwritten. Since this algorithm overwrites the initial values, the n processors can copy input values to a result array in parallel in one additional step.
From Yair Tuaff (firstname.lastname@example.org), 29 December 1999.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 25 January 2010.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "parallel prefix computation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 25 January 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/parallelPrefix.html