THE PARALLEL EVALUATION OF ARITHMETIC EXPRESSIONS WITHOUT DIVISION

RICHARD BRENT, DAVID KUCK, AND KIYOSHI MARUYAMA

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 log_{2} n + O(1) steps if sufficiently many processors are available. We then improve this result and reduce 3 log_{2} n to 2.465 log_{2} n. Finally, we deduce some results that apply when a fixed number of processors is available.

Comments

Only the Abstract is given here. The full paper appeared as [1] and was reprinted in [3, pages 30–35]. For a more general result which allows division, and requires less processors, see [2].

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.

(R. P. Brent) Computer Centre, Australian National University, Canberra, Australia

(D. J. Kuck and K. Maruyama) Department of Computer Science, University of Illinois, Urbana, Illinois 61801

1991 Mathematics Subject Classification. Primary 68Q22; Secondary 65Y05, 65Y20, 68M07, 68Q25. Key words and phrases. Arithmetic expression evaluation, number of processors, parallel computation, pro-

cessing time upper bound, simultaneous operations, tree-height reduction.

Manuscript received July 13, 1972; revised October 30, 1972. This work was supported in part by NSF Grant GJ-27446, AT(11-1)-2118 and in part by the IBM T. J. Watson

Research Center.

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

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