The Parallel Evaluation of General Arithmetic Expressions

The Parallel Evaluation of General Arithmetic Expressions

April 1974 | RICHARD P. BRENT
This paper presents a parallel evaluation method for general arithmetic expressions with variables, constants, and operations of addition, multiplication, and division. It shows that such expressions can be evaluated in time $4 \log_{2} n + 10(n - 1)/p$ using $p \geq 1$ processors, each performing arithmetic operations in unit time. This bound is within a constant factor of the best possible. A sharper result is given for expressions without division, and the paper discusses numerical stability. The paper begins by introducing the problem of evaluating arithmetic expressions on a parallel computer. It then presents a theorem that provides a method for evaluating arithmetic expressions in parallel. The theorem is proven using induction and involves breaking down the expression into smaller subexpressions that can be evaluated simultaneously. The proof also considers the number of processors and operations required to evaluate the expression. The paper then presents two corollaries of the theorem. The first corollary shows that arithmetic expressions can be evaluated in time $4 \log_{2} n + 10(n - 1)/p$ with $p$ processors. The second corollary establishes the complexity of parallel evaluation of general arithmetic expressions to within a constant factor, showing that the maximum time required is at most 14 times the lower bound. The paper also discusses the numerical stability of the evaluation method. It shows that the method is numerically stable for expressions without division but not for those with division. Examples show that the algorithm implied by the proof of the theorem is not always numerically stable. The paper concludes by noting that the constant factor in the complexity bound can be reduced with more refined arguments, and that the lower bound for the time required to evaluate arithmetic expressions can be improved slightly. The paper also mentions that the results apply to expressions over commutative fields and that the proof simplifies when division is excluded.This paper presents a parallel evaluation method for general arithmetic expressions with variables, constants, and operations of addition, multiplication, and division. It shows that such expressions can be evaluated in time $4 \log_{2} n + 10(n - 1)/p$ using $p \geq 1$ processors, each performing arithmetic operations in unit time. This bound is within a constant factor of the best possible. A sharper result is given for expressions without division, and the paper discusses numerical stability. The paper begins by introducing the problem of evaluating arithmetic expressions on a parallel computer. It then presents a theorem that provides a method for evaluating arithmetic expressions in parallel. The theorem is proven using induction and involves breaking down the expression into smaller subexpressions that can be evaluated simultaneously. The proof also considers the number of processors and operations required to evaluate the expression. The paper then presents two corollaries of the theorem. The first corollary shows that arithmetic expressions can be evaluated in time $4 \log_{2} n + 10(n - 1)/p$ with $p$ processors. The second corollary establishes the complexity of parallel evaluation of general arithmetic expressions to within a constant factor, showing that the maximum time required is at most 14 times the lower bound. The paper also discusses the numerical stability of the evaluation method. It shows that the method is numerically stable for expressions without division but not for those with division. Examples show that the algorithm implied by the proof of the theorem is not always numerically stable. The paper concludes by noting that the constant factor in the complexity bound can be reduced with more refined arguments, and that the lower bound for the time required to evaluate arithmetic expressions can be improved slightly. The paper also mentions that the results apply to expressions over commutative fields and that the proof simplifies when division is excluded.
Reach us at info@study.space
[slides] The Parallel Evaluation of General Arithmetic Expressions | StudySpace