Efficient massively parallel quicksort
Solving Irregularly Structured Problems in Parallel, volume 1253 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, (1997)DOI: 10.1007/3-540-63138-0_2
Abstract
Parallel quicksort is known as a very scalable parallel sorting algorithm. However, most actual implementations have been limited to basic versions which suffer from irregular communication patterns and load imbalance. We have implemented a high performance variant of parallel quicksort which incorporates the following optimizations: Stop the recursion at the right time, sort locally first, use accurate yet efficient pivot selection strategies, streamline communication patterns, use locality preserving processor indexing schemes and work with multiple pivots at once. It turns out to be among the best practical sorting methods. It is about three times faster than the basic algorithm and achieves a speedup of 810 on a 1024 processor Parsytec GCel for the NAS parallel sorting benchmark of size 2
Description
Efficient massively parallel quicksort - Springer
