On the Parallel Evaluation of Certain Arithmetic Expressions
Shmuel Winograd · Journal of the ACM · 1975
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).