Time Bounds on the Parallel Evaluation of Arithmetic Expressions
David J. Kuck, Kiyoshi Maruyama · SIAM Journal on Computing · 1975
This paper presents a number of bounds on the parallel processor evaluation of arithmetic expressions. Several previous papers show that if the evaluation of an expression using a serial computer requires t operations, by using a number of processors in parallel, the expression may be evaluated in time proportional to $\log _2 t$. Since $\log _2 t$ is an obvious lower bound, it is of interest to attempt to approach this bound. The present paper shows that if more information than the number of operations (or operands) is known, sharper bounds may be given in certain cases. Thus if the number of parenthesis pairs is small or if the depth of parenthesis nesting is small, we may approach the lower bound. A new bound is also given for expressions which have few division operations. Similarly, if the expression’s form is restricted, sharper bounds may be found. Thus generalizations of polynomials and generalizations of continued fractions are shown to have improved bounds. We also give a new bound for expressions without division operations which have a limited number of parenthesis pairs. Finally, we give an upper bound on the time to evaluate expressions in which multiplication is not commutative.