THE PARALLEL EVALUATION OF ARITHMETIC EXPRESSIONS IN LOGARITHMIC TIME

RICHARD P. BRENT

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 log_{2} n + 2(n − 1)/p using p processors. If division is allowed, the time is 4 log_{2} n+10(n−1)/p (as shown in [3]). 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

Only the Abstract is given here. The full paper appeared as [2]. The paper improves a result of Brent, Kuck and Maruyama [1] by reducing the number of

processors required. The numerical stability result is new.

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

References

[1] R. P. Brent, D. J. Kuck and K. Maruyama, “The parallel evaluation of arithmetic expressions without division”, IEEE Transactions on Computers C-22 (1973), 532–534. MR 50#11843. rpb015.

[2] 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; Zbl 273.68037. rpb018.

[3] R. P. Brent, “The parallel evaluation of general arithmetic expressions”, Journal of the ACM 21 (1974), 201–206. CR 15#27055, MR 58#31996, Zbl 276.68010. rpb022.

Computer Centre, Australian National University, Canberra, Australia

1991 Mathematics Subject Classification. Primary 68Q22; Secondary 65M15, 65Y05, 68Q25. Key words and phrases. Arithmetic expressions, Boolean expressions, compilation of arithmetic expressions,

computational complexity, general arithmetic expressions, numerical stability, parallel computation. CR Categories. 4.12, 5.11, 5.25. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1973, Academic Press, Inc. Comments \begin{matrix}c \\ ◯ \end{matrix} 2000, R. P. Brent.

rpb018a typeset using AMS-L^{A}TEX.