(algorithm)
Definition: Calculate an associative function, f, on all prefixes of an n-element array, that is, s[0], f(s[0], s[1]), f(s[0], f(s[1], s[2])), ..., f(s[0], f(s[1], ... 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])
Note:
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 (r56409@email.sps.mot.com), 29 December 1999.
Author: PEB
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