Optimal Sorting Algorithms for Parallel Computers.
Abstract
The problem of sorting a sequence of n elements on a parallel computer with k processors is considered. The algorithms the authors present can all be run on a single instruction stream multiple data stream computer. For large n, each achieves an asymptotic speed-up ratio of k with respect to the best sequential algorithm. This linear (in k) speed-up is optimal in the number of processors used.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1975
- Accession Number
- ADA012492
Entities
People
- David Stevenson
- Gerard Baudet
Organizations
- Carnegie Mellon University