Loading...
Please wait, while we are loading the content...
Similar Documents
New algorithms and lower bounds for the parallel evaluation of certain rational expressions (1974)
| Content Provider | CiteSeerX |
|---|---|
| Author | Kung, H. T. |
| Abstract | This paper presents new algorithms for the parallel evaluation of certain polynomial expres-sions. In particular, for the parallel evaluation n of x, we introduce an algorithm which takes two steps of parallel division and [log2n] steps of parallel addition, while the usual algorithm takes [log2n] steps of parallel multiplication. Hence our 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 algor-ithms presented in the paper are shown to be asymp-totically optimal. Moreover, we prove that by using parallelism the evaluation of any first order ra-= ~(x.~--), and any tional recurrence, e.g., xi+] z i x. i non-linear polynomial recurrence can be sped up at most by a constant factor, no matter how many pro-cessors are used. |
| File Format | |
| Language | English |
| Publisher Date | 1974-01-01 |
| Access Restriction | Open |
| Subject Keyword | Parallel Evaluation New Algorithm Certain Rational Expression Usual Algorithm Many Pro-cessors Polynomial Expression Similar Algorithm Non-linear Polynomial Recurrence Log2n Step Certain Polynomial Expres-sions First Order Ra Tional Recurrence Parallel Multiplication Rational Expression Parallel Addition Parallel Division Constant Factor |
| Content Type | Text |
| Resource Type | Technical Report |
