Sorting with near linear speed-up on tightly coupled multiprocessors
✍ Scribed by Wheat, Mitchell
- Publisher
- John Wiley and Sons
- Year
- 1991
- Tongue
- English
- Weight
- 582 KB
- Volume
- 3
- Category
- Article
- ISSN
- 1040-3108
No coin nor oath required. For personal study only.
✦ Synopsis
A new parallel sorting algorithm, called parsort, suitable for implementation on tightly coupled multiprocessors is presented. The algorithm is based upon quicksort and two-way merging. An asynchronous parallel partitioning algorithm is used to distribute work evenly during merging to ensure a good load balance amongst processors, which is crucial if we are to achieve high eficiency. The implementation d this parallel sorting algorithm exhibits theoretical and measured near linear speed-up when compared to sequential quicksort. This is illustrated by the results of experiments carried out on the Sequent Balance 8OOO multiprocessor.