Bounds on the Speed-Up of Parallel Evaluation of Recurrences,
Abstract
To understand the performance of parallel computers such as ILLIAC IV and C.mmp, the largest speed-up that can be obtained for a given task must be known. If there are k processors, the largest speed-up that can be achieved is k and the authors call this optimal speed-up. The speed-ups in general depend on the parallel decompositon of a particular computing task and the various aspects of the multiprocessing system, including memory contention, process communication, operating system overhead, etc. In this paper, the authors concentrate on the issue of decomposing tasks, and assume that the multiprocessing system is idealized so that it causes no delays at all. It is shown that even under this idealized assumption, there are problems for which, because the parallel decompositions are inherently difficult, the optimal speed-up cannot be achieved.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1975
- Accession Number
- ADA016227
Entities
People
- H. T. Kung
- L. Hyafil
Organizations
- Carnegie Mellon University