### Restructuring of Arithmetic Expressions For Parallel EvaluationRestructuring of Arithmetic Expressions For Parallel Evaluation

Access Restriction
Subscribed

 Author Muller, David E. ♦ Preparata, Franco P. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1976 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract Let $\textit{E}$ be an arithmetic expression involving $\textit{n}$ variables, each of which appears just once, and the possible operations of addition, multiplication, and division. Although other cases are considered, when these three operations take unit time the restructuring algorithms presented in this paper yield evaluation times no greater than 2.88 $log2\textit{n}$ + 1 and 2.08 $log2\textit{n}$ for general expressions and division-free expressions, respectively. The coefficients are precisely given by 2/log2α ≈ 2.88 and $1/log2\textit{β}$ ≈ 2.08, where $\textit{α}$ and $\textit{β}$ are the positive real roots of the equations $\textit{z}2$ = $\textit{z}$ + 1 and $\textit{z}4$ = $2\textit{z}$ + 1, respectively. While these times were known to be of order $log2\textit{n},$ the best previously known coefficients were 4 and 2.15 for the two cases.The authors conjecture that the present coefficients are the best possible, since they have exhibited expressions which seem to require these times within an additive constant.The paper also gives upper bounds to the restructuring time of a given expression $\textit{E}$ and to the number of processors required for its parallel evaluation. It is shown that at most $\textit{O}\textit{(n}1.44\textit{)}$ and $\textit{O}(n1.82\textit{)}$ operations are needed for restructuring general expressions and division-free expression, respectively. It is pointed out that, since the order of the compiling time is greater than $\textit{n}$ log $\textit{n},$ the numbers of required processors exhibit the same rate of growth in $\textit{n}$ as the corresponding compiling times. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1976-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 23 Issue Number 3 Page Count 10 Starting Page 534 Ending Page 543

#### Open content in new tab

Source: ACM Digital Library