The Parallel Evaluation of General Arithmetic Expressions

The Parallel Evaluation of General Arithmetic Expressions

April 1974 | RICHARD P. BRENT
The paper by Richard P. Brent discusses the parallel evaluation of arithmetic expressions with $n \geq 1$ variables and constants, involving addition, multiplication, and division, and any depth of parenthesis nesting. Brent shows that such expressions can be evaluated in time $4 \log n + 10(n - 1)/p$ using $p \geq 1$ processors, where each processor can perform arithmetic operations in unit time. This bound is within a constant factor of the best possible. The paper also provides a sharper result for expressions without division and discusses numerical stability. The proofs are constructive, and efficient algorithms for compiling expressions for parallel execution are derived. The results are compared favorably with those in previous studies, and the practical implications for optimizing compilers on parallel machines are highlighted. The paper concludes with a discussion on the complexity of parallel evaluation and the numerical stability of the algorithms.The paper by Richard P. Brent discusses the parallel evaluation of arithmetic expressions with $n \geq 1$ variables and constants, involving addition, multiplication, and division, and any depth of parenthesis nesting. Brent shows that such expressions can be evaluated in time $4 \log n + 10(n - 1)/p$ using $p \geq 1$ processors, where each processor can perform arithmetic operations in unit time. This bound is within a constant factor of the best possible. The paper also provides a sharper result for expressions without division and discusses numerical stability. The proofs are constructive, and efficient algorithms for compiling expressions for parallel execution are derived. The results are compared favorably with those in previous studies, and the practical implications for optimizing compilers on parallel machines are highlighted. The paper concludes with a discussion on the complexity of parallel evaluation and the numerical stability of the algorithms.
Reach us at info@study.space