A Direct Approach to the Parallel Evaluation of Rational Expressions with a Small Number of Processors
- 1 October 1977
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-26 (10) , 933-937
- https://doi.org/10.1109/TC.1977.1674728
Abstract
In this paper we construct algorithms and investigate the time required for the parallel evaluation of rational expressions using small numbers of processors. We define algorithms which compute a polynomial with n operations in 3n/(2p + 1) + Q(p2) time units with p processors and a general rational expression with n operations in 5n/(2p + 3) + 0(p2) time units. These algorithms are suitable for implementation on computers with restricted data access.Keywords
This publication has 4 references indexed in Scilit:
- On the Parallel Evaluation of Certain Arithmetic ExpressionsJournal of the ACM, 1975
- Time Bounds on the Parallel Evaluation of Arithmetic ExpressionsSIAM Journal on Computing, 1975
- A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence EquationsIEEE Transactions on Computers, 1973
- An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of EquationsJournal of the ACM, 1973