Tree-Based Parallel Algorithm Design |
| |
Authors: | G L Miller S -H Teng |
| |
Affiliation: | (1) School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA. glmiller@cs.cmu.edu. , US;(2) Department of Computer Science, University of Minnesota, Minneapolis, MN 55455, USA. steng@cs.umn.edu. , US |
| |
Abstract: | In this paper a systematic method for the design of efficient parallel algorithms for the dynamic evaluation of computation
trees and/or expressions is presented. This method involves the use of uniform closure properties of certain classes of unary
functions. Using this method, optimal parallel algorithms are given for many computation tree problems which are important
in parallel algebraic and numerical computation, and parallel code generation on exclusive read and exclusive write parallel
random access machines. Our algorithmic result is complemented by a P-complete tree problem.
Received February 13, 1995; revised March 25, 1996. |
| |
Keywords: | , Parallel tree contraction, Parallel algorithms, Algebraic computing, Code optimization, List ranking, Parallel,,,,,prefix sum, |
本文献已被 SpringerLink 等数据库收录! |
|