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