哪种并行sortingalgorithm具有最好的平均情况下的性能?

在序列情况下sorting需要O(n log n)。 如果我们有O(n)处理器,我们希望线性加速。 O(log n)并行algorithm存在,但它们具有很高的常数。 它们也不适用于在O(n)处理器附近没有任何地方的商品硬件。 对于p处理器,合理的algorithm应该花费O(n / p log n)时间。

在序列情况下,快速sorting平均具有最佳的运行时复杂性。 并行快速sortingalgorithm很容易实现(见这里和这里 )。 然而,由于第一步是将整个集合分割到单个内核上,因此性能不佳。 我已经find许多并行sortingalgorithm的信息,但到目前为止我还没有看到任何指向明确的赢家。

我正在寻找以8到32个核心运行的JVM语言sorting100万到1亿个元素的列表。

以下文章(PDF下载)是各种体系结构上并行sortingalgorithm的比较研究:

在各种体系结构上的并行sortingalgorithm

根据文章, 样本sorting似乎是许多并行架构types中最好的。

更新以解决Mark对年龄的关注:

这里有更近期的文章介绍更新颖的东西(从2007年,顺便说一句,仍然得到比较样本sorting):

样品分类改进
AA-sorting

出血的边缘(大约在2010年,一些只有几个月大):

并行sorting模式
基于GPU的多核并行sorting
混合CPU / GPU并行sorting
随机并行sortingalgorithm的实验研究
高度可扩展的并行sorting
使用自然顺序sortingN元素:一种新的自适应sorting方法

2013年更新:大约在2013年1月份,这里是出血点。(注:一些链接是在Citeseer的文件,需要注册是免费的):

大学讲座:
并行分区select和sorting
并行sortingalgorithm讲座
并行sortingalgorithm讲座2
并行sortingalgorithm讲座3

其他来源和论文:
基于自适应比特sorting的多核体系结构分类algorithm
高度可扩展的并行sorting2
并行合并
并行合并2
并行对象自动sorting系统
序列快速sorting与并行快速sortingalgorithm的性能比较
共享内存,消息传递和混合合并sorting用于独立和群集SMP
各种并行algorithm(sorting等)包括实现

GPU和CPU / GPU混合来源和论文:
一种用于GPU架构的并行sortingalgorithm的OpenCL方法
数据分类使用graphics处理单元
在GPU上进行sorting的高效algorithm
为许多GPUdevise高效的sortingalgorithm
针对GPU的确定性样本分类
基于双向sorting的CUDA快速就地分拣
使用混合algorithm的快速并行GPU分类
GPU上的快速并行sortingalgorithm
在CPU和GPU上快速sorting:带宽不经意SIMDsorting的情况
GPU样本sorting
GPU-ABiSort:stream体系结构上的最佳并行sorting
GPUTeraSort:用于大型数据库pipe理的高性能graphics协处理器分类
基于高性能比较的多核GPUsortingalgorithm
对支持CUDA的GPU进行并行外部sorting,具有负载平衡和低传输开销
在GPU上进行大规模数据集sorting:彻底比较

我已经使用了并行快速sortingalgorithm和PSRSalgorithm,它们基本上将QuickSort与合并并行。

使用并行快速sortingalgorithm,我已经演示了多达4个内核(具有超线程的双核)的接近线性加速,由于该algorithm的局限性,我们预计这是预期的。 纯粹的并行快速sorting依赖共享堆栈资源,这将导致线程之间的争用,从而降低性能的增益。 这个algorithm的优点是它能够“就地”sorting,从而减less了所需的内存量。 如您所述,您可能需要考虑这个问题时,将100M元素sorting。

我看到你正在寻找一个8-32核心的系统sorting。 PSRSalgorithm避免了在共享资源上的争用,允许在更多的进程中加速。 我已经演示了多达4个核心的algorithm,但是其他的实验结果报道了线性加速,32核心以及更多的核心。 PSRSalgorithm的缺点是它不在位,并且需要相当多的内存。

如果你有兴趣,你可以使用或仔细阅读我的Java代码中的每一种algorithm。 你可以在github上find它: https : //github.com/broadbear/sort 。 该代码旨在作为Java Collections.sort()的简单replace。 如果您正在寻找能够在JVM中执行并行sorting的function,则可以使用我的回购代码中的代码。 该API是完全通用的元素实现Comparable或实现自己的比较器。

请问您在寻找什么样的元素来分类? 我很想知道我的分类软件包的潜在应用程序。

看看这篇文章: 一种使用精确分割的可伸缩并行sortingalgorithm 。 它涉及到多于32个内核。 然而,它详细描述了一个algorithm,其运算时间复杂度为O(n / p * log(n)+ p * log(n)** 2),适用于任意的比较器。

论文“不同架构上的并行sortingalgorithm的比较”可能是一个很好的开始。