Parallel Restructuring and Evaluation of Expressions
ILLINOIS UNIV AT URBANA COLL OF ENGINEERING
Pagination or Media Count:
This paper describes a boolean network of size ON squared log N which accepts a fully parenthesized N-variable expression over a given semiring and produces its value in Olog 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 Olog N for an N-variable expression, and are either optimal, ONlog N, or near-optimal, ON , 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.
- Computer Systems