Accession Number:

ADA171219

Title:

Parallel Tree Contraction and Its Application.

Descriptive Note:

Technical rept.,

Corporate Author:

HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB

Personal Author(s):

• Miller,Gary L.
• Reif,John H.

Report Date:

1985-12-01

Pagination or Media Count:

55.0

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 13 - 23 separator and recursively solving the two subproblems. A now classic example is Brents 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 Brents 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.

Descriptors:

• *ALGORITHMS
• *PARALLEL PROCESSING
• COMPUTATIONS
• PARALLEL PROCESSORS
• THEOREMS
• SEPARATORS

Subject Categories:

• Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE