A benchmark parallel sort for shared memory multiprocessors
- 1 January 1988
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 37 (12) , 1619-1626
- https://doi.org/10.1109/12.9738
Abstract
The first parallel sort algorithm for shared memory MIMD (multiple-instruction-multiple-data-stream) multiprocessors that has a theoretical and measured speedup near linear is exhibited. It is based on a novel asynchronous parallel merge that evenly partitions data to be merged among any number of processors. A benchmark sorting algorithm is proposed that uses this merge to remove the linear time bottleneck inherent in previous multiprocessors sorts. This sort, when applied to data set on p processors, has a time complexity of O((n log n)/p)+O((n log p)/p) and a space complexity of 2n, where n is the number of keys being sorted. Evaluations of the merge and benchmark sort algorithms on a 12-processor Sequent Balance 21000 System demonstrate near-linear speedup when compared to sequential Quicksort.Keywords
This publication has 15 references indexed in Scilit:
- Problem-heap: A paradigm for multiprocesor algorithmsParallel Computing, 1987
- Timing results of some internal sorting algorithms on vector computersParallel Computing, 1987
- The parallel neighbour sort and 2-way merge algorithmParallel Computing, 1986
- Analysis of the performance of the parallel quicksort methodBIT Numerical Mathematics, 1985
- A taxonomy of parallel sortingACM Computing Surveys, 1984
- Parallel Sorting AlgorithmsPublished by Elsevier ,1984
- Implementing Quicksort programsCommunications of the ACM, 1978
- Merging with parallel processorsCommunications of the ACM, 1975
- Parallelism in Comparison ProblemsSIAM Journal on Computing, 1975
- Bounds to Complexities of Networks for Sorting and for SwitchingJournal of the ACM, 1975