Ladner Fischer [1980] Better Solution
•Parallel
Prefix algorithm uses idea like “carry propagation” to reduce work
•In
first half of algorithm, each processor adds as in “global sum” technique, but
it also passes to its parent the sum of its left subtree
•In
second half of algorithm, each processor
–receives
sum of items to its left
–forwards
that to its left subtree
–adds
in the sum of its left subtree
–sends
result to its right subtree
•Every
processor i gets data to produce yi