Optimal parallel evaluation of tree-structured computations by raking (extended abstract)

We show that any arithmetic expression of size n can be evaluated on an EREW PRAM with O(n/log n) processors in O (log n) steps. A major contribution is the simplicity of the algorithm. In contrast with existing algorithms which require independent RAKE and COMPRESS operations, our algorithm combines the RAKE and COMPRESS into one simple operation. In fact, our algorithm can be viewed as avoiding COMPRESSes entirely and simply performing RAKEs. The algorithm can be modified easily to evaluate every subexpression of the original arithmetic expression. We also show how it can be applied to the following problem: Given a positive constant λ and a tree with weighted nodes, partition the tree into minimal components subject to the constraint that the sum of the node weights in each component is at least λ.