The Complexity of Parallel Evaluation of Linear Recurrences.
Abstract
The concept of computers such as C.mmp and ILLIAC 4 is to achieve computational speed-up by performing several operations simultaneously with parallel processors. This type of computer organization is referred to as a parallel computer. In this paper, the authors prove upper bounds on speed-ups achievable by parallel computers for a particular problem, the solution of first order linear recurrences. The authors consider this problem because it is important in practice and also because it is simply stated so that one might obtain some insight into the nature of parallel computation by studying it.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1974
- Accession Number
- ADA001376
Entities
People
- H. T. Kung
- L. Hyafil
Organizations
- Carnegie Mellon University