The parallel evaluation of arithmetic expressions in logarithmic time
18. R. P. Brent,
The parallel evaluation of arithmetic expressions in
logarithmic time,
in Complexity of Sequential and Parallel Numerical Algorithms
(edited by J. F. Traub), Academic Press, New York, 1973, 83-102.
CR 15#26540, 15#27335;
MR 50#15432.
Abstract:
dvi (2K),
pdf (73K).
Paper:
pdf (1297K).
Abstract
This paper gives a survey of results on the time required to evaluate
arithmetic expressions with several parallel processors, and also includes
several new results.
It is shown that an arithmetic expression with
n distinct atoms, and operations of addition and multiplication
over a ring can be evaluated in time
4 log2n + 2(n-1)/p
using p processors. If division is allowed, the time is
4 log2n + 10(n-1)/p,
as shown in [22].
These results are within small constant factors of the best possible.
It is also shown that the algorithm for parallel evaluation of expressions
without division is numerically stable in the sense of backward error
analysis.
Comments
This paper improves a result of Brent,
Kuck and Maruyama
[15] by reducing the number of processors
required. The numerical stability result is new.
The result on expressions including division appears in
Brent [22]. However, the error analysis
does not carry over to expressions with division.
Go to next publication
Return to Richard Brent's index page