Restructuring of Arithmetic Expressions For Parallel Evaluation

Publisher Website
Google Scholar
Abstract
Let E be an arithmetic expression involving 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 log 2 n + 1 and 2.08 log 2 n for general expressions and division-free expressions, respectively. The coefficients are precisely given by 2/log 2 α ≈ 2.88 and 1/log 2 β ≈ 2.08, where α and β are the positive real roots of the equations z 2 = z + 1 and z 4 = 2 z + 1, respectively. While these times were known to be of order log 2 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 E and to the number of processors required for its parallel evaluation. It is shown that at most O (n 1.44 ) and O (n 1.82 ) 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 n log n , the numbers of required processors exhibit the same rate of growth in n as the corresponding compiling times.

This publication has 4 references indexed in Scilit: