Parallel Restructuring and Evaluation of Expressions
Abstract
This paper describes a boolean network of size O(N squared log N) which accepts a fully parenthesized N-variable expression over a given semiring and produces its value in O(log N) time. The network consists of two components: a preprocessor and a universal evaluator. The preprocessor computes the destinations of the expression terms and routes them to the correct input terminals of the universal evaluator. The evaluation of tree-structured expressions is a fundamental computation encountered in several problems. The feasibility of parallel computing has attracted considerable research interest to the restructuring of expressions - typically arithmetic expressions - to speed up their evaluation. While restructuring for parallel evaluation has been the main objective for some time, more recently attention has focussed on the parallelization of the actual evaluation starting from the original expression itself. Several algorithms have been recently proposed for implementation on the P-RAM model, the most efficient of these algorithms achieve time O(log N) for an N-variable expression, and are either optimal, O(N/log N), or near-optimal, O(N) , in the number of processors used. The evaluations of an expression in parallel could be carried out as the combined execution of the restructuring and evaluation tasks.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1988
- Accession Number
- ADA200521
Entities
People
- D. E. Muller
- Franco P. Preparata
Organizations
- University of Illinois Urbana–Champaign