


























Quicksort is an instructive classroom approach to parallel sorting on distributed memory parallel computers with many opportunities for illustrating specific implementation alternatives and tradeoffs with common communication interfaces like MPI. The (two) standard distributed memory Quicksort implementations exchange partitioned data elements at each level of the Quicksort recursion. In this note, we show that this is not necessary: It suffices to distribute only the chosen pivots, and postpone element redistribution to the bottom of the recursion. This reduces the total volume of data exchanged from $O(n\log p)$ to $O(n)$, $n$ being the total number of elements to be sorted and $p$ a power-of-two number of processors, by trading off against a total of $O(p)$ additional pivot element distributions. Based on this observation, we describe new, \emph{exchange-free} implementation variants of parallel Quicksort and of Wagar's HyperQuicksort. We have implemented the discussed four different Quicksort variations in MPI, and show that with good pivot selection, Quicksort without pairwise element exchange can be significantly faster than standard implementations on moderately large problems.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。