Parallel tree contraction and its application

Abstract : Trees play a fundamental role in many computations, both for sequential as well as parallel problems. The classic paradigm applied to generate parallel algorithms in the presence of trees has been divide-conquer; finding a 1/3 - 2/3 separator and recursively solving the two subproblems. A now classic example is Brent's work on parallel evaluation of arithmetic expressions. This top-down approach has several complications, one of which is finding the separators. We define dynamic expression evaluation as the task of evaluating the expression with no free preprocessing. If we apply Brent's method, finding the separators seems to add a factor of log n to the running time. We give a bottom-up algorithm to handle trees. That is, all modifications to the tree are done locally. This bottom-up approach which we call CONTRACT has two major advantages over the top-down approach: (1) the control structure is straight forward and easier to implement facilitating new algorithms using fewer processors and less time; and (2) problems for which it was too difficult or too complicated to find polylog parallel algorithms are now easy.