Accession Number:

AD0779055

Title:

New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions,

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Kung,H. T.

Report Date:

1974-02-01

Pagination or Media Count:

14.0

Abstract:

The paper presents new algorithms for the parallel evaluation of certain polynomial expressions. In particular, for the parallel evaluation of x sup n the author introduces an algorithm which takes two steps of parallel division and logbase 2 n steps of parallel addition, while the usual algorithm takes logbase 2n steps of parallel multiplication. Hence the algorithm is faster than the usual algorithm when multiplication takes more time than addition. Similar algorithms for the evaluation of other polynomial expressions are also introduced. Lower bounds on the time needed for the parallel evaluation of rational expressions are given. All the algorithms presented in the paper are shown to be asymptotically optimal. Moreover, the author proves that by using parallelism the evaluation of any first order rational recurrence, e.g., y subi1 12 y sub i ay, and any non-linear polynomial recurrence can be sped up at most by a constant factor, no matter how many processors are used. Author

Descriptors:

• *Parallel processors
• *Arithmetic
• *Computations
• Polynomials
• Algorithms

Subject Categories:

• Theoretical Mathematics
• Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE