Tree-structured parallel algorithms

This paper presents a study of tree-structured parallel algorithms. Concepts such as flow, synchronous and asynchronous tree algorithms, and speed-up for this class of algorithms are defined. It is shown that under certain reasonable assumptions the speed-up, in going from a sequential to a parallel execution, is given by the ratio of the number of nodes in the tree to the number of levels in the tree. These concepts are then used in the study of algorithms for the following four problems: finding a maximal common subsequence of two given strings, locating the zeros of a complex polynomial in a given rectangle in the complex plane, allocating resources to some n activities maximizing the returns using a dynamic programming approach, and evaluating a multivariate polynomial. The polynomial zeros algorithm is shown to be an asynchronous tree algorithm whose speed-up is given by 0(n). The other algorithms are shown to be synchronous tree algorithms and their speed-up is O(n/log₂n). These serve as examples of algorithms with an inherent limitation preventing them from achieving a speed-up factor of 0(n).