On the Parallel Evaluation of Certain Arithmetic Expressions

Abstract

The time required to evaluate arithmetic expressions using parallel processing is investigated It is shown that for the evaluation of an arithmetic expression of n variables without division, in which every variable appears only once, at most 3n/2p + o(n) time umts are required if p processors are used In case the expression includes the division operation, the bound is raised to 5n/2p + o(n). © 1975, ACM. All rights reserved.