The Parallel Evaluation of Arithmetic Expressions Without Division

15. 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.

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

Paper: pdf (536K).

Abstract

As computers become capable of executing more arithmetic operations simultaneously, the question of compiling for such machines becomes more important. In this correspondence we consider arbitrary arithmetic expressions of n distinct variables with operations restricted to addition, subtraction, and multiplication. We first construct a scheme whereby any such expression can be evaluated in at most 3 log2n + O(1) steps if sufficiently many processors are available. We then improve this result and reduce 3 log2n to 2.465 log2n. Finally, we deduce some results that apply when a fixed number of processors is available.

Comment

The result was improved (if the number of processors is limited) and generalised in [18], [22].

Go to next publication

Return to Richard Brent's index page