The parallel evaluation of general arithmetic expressions
22. R. P. Brent,
The parallel evaluation of general arithmetic expressions,
J. ACM 21 (1974), 201-206.
CR 15#27055,
MR 58#31996.
Abstract:
dvi (2K),
pdf (80K).
Paper:
pdf (387K).
Abstract
It is shown that arithmetic expressions with n
variables and constants; operations of addition, multiplication, and division;
and any depth of parenthesis nesting can be evaluated in time
4 log2n + 10(n-1)/p
using p 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
The main result is the best possible,
up to small constant factors.
For related results see
[15,
18,
38].
Lemma 2 of the paper is a simple but useful simulation result,
sometimes called ``Brent's lemma'', which allows us to deduce time
bounds for parallel computations with a limited number of processors
by counting the operations performed on a parallel machine with an
unlimited number of processors.
Lemma 2 (Brent's Lemma)
If a computation can be performed in t steps with
q operations on a parallel computer (formally, a PRAM)
with an unbounded number of processors,
then the computation can be performed in
t + (q-t)/p steps with p processors.
Go to next publication
Return to Richard Brent's index page