Parallel tree contraction and its application

TLDR

Trees are fundamental to many computations, and parallel algorithms have traditionally used a divide‑conquer, 1/3‑2/3 separator strategy exemplified by Brent’s parallel evaluation of arithmetic expressions, but this top‑down approach is complicated by the need to find separators. The authors define dynamic expression evaluation—evaluating expressions without preprocessing—and propose a bottom‑up algorithm to handle trees. Their bottom‑up method performs local tree modifications, avoiding the log n overhead of separator discovery inherent in Brent’s approach. The resulting CONTRACT algorithm simplifies control, reduces processor count and runtime, and enables efficient parallel solutions to problems that were previously too difficult for polylogarithmic algorithms.

Abstract

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.