The parallel evaluation of arithmetic expressions in logarithmic time

18. R. P. Brent, The parallel evaluation of arithmetic expressions in logarithmic time, in Complexity of Sequential and Parallel Numerical Algorithms (edited by J. F. Traub), Academic Press, New York, 1973, 83-102. CR 15#26540, 15#27335; MR 50#15432.

Abstract: dvi (2K), pdf (73K).

Paper: pdf (1297K).

Abstract

This paper gives a survey of results on the time required to evaluate arithmetic expressions with several parallel processors, and also includes several new results.

It is shown that an arithmetic expression with n distinct atoms, and operations of addition and multiplication over a ring can be evaluated in time 4 log2n + 2(n-1)/p using p processors. If division is allowed, the time is 4 log2n + 10(n-1)/p, as shown in [22]. These results are within small constant factors of the best possible.

It is also shown that the algorithm for parallel evaluation of expressions without division is numerically stable in the sense of backward error analysis.

Comments

This paper improves a result of Brent, Kuck and Maruyama [15] by reducing the number of processors required. The numerical stability result is new.

The result on expressions including division appears in Brent [22]. However, the error analysis does not carry over to expressions with division.

Go to next publication

Return to Richard Brent's index page