## 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 log_{2}*n* + 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