A Bonus ...
Ladner
- Fischer can solve a larger problem in same time! [Works for other
algorithms]
Suppose
there are Plog2 P
values, stored log2 P per
processor
Ask each processor to add the log2 P items locally, and then solve
the problem as stated
On completion, compute the prefix for each of the log2 P elements
Though the problem is log2 P times larger, the execution time is roughly three times as long