THE PARALLEL EVALUATION OF GENERAL ARITHMETIC EXPRESSIONS

RICHARD P. BRENT

Abstract

It is shown that arithmetic expressions with n ≥ 1 variables and constants; operations of addition, multiplication, and division; and any depth of parenthesis nesting can be evaluated in time 4 log_{2} n + 10(n − 1)/p using p ≥ 1 processors which can independently perform arithmetic operations in unit time. This bound is within a constant factor of the best possible. A sharper result is given for expressions without the division operation, and the question of numerical stability is discussed.

Comments

Only the Abstract is given here. The full paper appeared as [2] and was reprinted in [3, pages 39–44]. For earlier work see [1].

The result of [2] is the best possible, up to small constant factors. It should be compared with the well-known result of Valiant et al [4] that any multivariate polynomial of degree d which can be evaluated sequentially in n steps can be evaluated in O(log d)(log n+log d) parallel steps using O(n^{3}d^{6}) processors. The latter result is more general, but weaker, because of the log d terms in the time bound and the much larger number of processors. Both results apply to Boolean expressions, so they have implications for the design of circuits with small depth, i.e. small delay.

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 general arithmetic expressions”, Journal of the ACM 21 (1974), 201–206. CR 15#27055, MR 58#31996, Zbl 276.68010. rpb022.

3. R. P. Brent, Topics in computational complexity and the analysis of algorithms, Report TR-CS-80-14, DCS, ANU, October 1980, 375 pp. (D. Sc. thesis). rpb062.

4. L. G. Valiant, S. Skyum, S. Berkowitz and C. Rackoff, “Fast parallel computation of polynomials using few processors”, SIAM J. Computing 12, 1983, 641–644.

Computer Centre, Australian National University, Canberra, Australia

1991 Mathematics Subject Classification. Primary 68Q22; Secondary 65M15, 65Y05, 68Q25.

Key words and phrases. Arithmetic expressions, compilation of arithmetic expressions, computational complexity, general arithmetic expressions, numerical stability, parallel computation, code optimization.

CR Categories. 4.12, 5.11, 5.25.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1974, Association for Computing Machinery, Inc. General permission to republish, but not for profit, all or part of this material is granted provided that ACM’s copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb022a typeset using AMS-L^{A}TEX