哪种并行排序算法具有最佳的平均案例性能？

Question

排序在串行情况下需要O(n log n).如果我们有O(n)处理器,我们希望线性加速.存在O(log n)并行算法,但它们具有非常高的常数.它们也不适用于没有O(n)处理器附近的商品硬件.对于p个处理器,合理的算法应该花费O(n/p log n)时间.

在串行的情况下,快速排序平均具有最佳的运行时复杂性.并行快速排序算法易于实现(请参见此处和此处).但是它表现不佳,因为第一步是将整个集合划分到单个核心上.我已经找到了许多并行排序算法的信息,但到目前为止我还没有看到任何指向明显赢家的信息.

我希望在运行8到32个内核的JVM语言中对100万到1亿个元素的列表进行排序.

Answer 1

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

各种体系结构上的并行排序算法

根据这篇文章,样本排序在许多并行体系结构类型上似乎是最好的.

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

这里有更新的文章介绍更新颖的东西(从2007年开始,顺便说一句,仍然可以与样本排序进行比较):

样品分类 AA-Sort的改进

最前沿(大约在2010年,有些只有几个月):

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

2013年更新: 这是大约在2013年1月的最前沿.(注意:一些链接是Citeseer的论文,需要注册免费):

大学讲座:
并行分区选择和排序
并行排序算法讲座
并行排序算法第2讲
并行排序算法第3讲

其他资料和论文:
基于自适应比特排序的多核架构的新型排序算法
高度可扩展的并行排序2
并行合并
并行合并
用于对象的2个并行自排序系统
顺序快速排序和并行快速排序算法的性能比较
独立和群集SMP的共享内存,消息传递和混合合并排序
各种并行算法(排序等)包括实现

GPU和CPU/GPU混合源和论文:
用于GPU体系结构的并行排序算法的OpenCL方法
使用图形处理单元
进行数据排序在GPU上进行排序的
高效算法为多核GPU设计有效的排序算法
确定性样本排序用于GPU
快速就地排序基于bitonic排序的CUDA
使用混合算法进行快速并行GPU排序使用GPU上的
快速并行排序算法
快速排序CPU和GPU:带宽无用的SIMD排序
GPU样本排序
GPU-ABiSort:流体系结构上的最佳并行排序
GPUTeraSort:高性能图形协处理器排序,用于大型数据库管理
基于高性能比较的多核GPU排序算法
支持CUDA的GPU的并行外部排序,具有负载平衡和低传输开销,可
在大型数据集的GPU上进行排序:全面比较

Answer 2

我使用了Parallel Quicksort算法和PSRS算法,它基本上将quicksort与并行相结合.

使用Parallel Quicksort算法,我已经证明了具有多达4个内核(具有超线程的双核)的近线性加速,考虑到算法的局限性,这是预期的.纯并行Quicksort依赖于共享堆栈资源,这将导致线程之间的争用,从而减少任何性能增益.该算法的优点在于它"就地"排序,这减少了所需的内存量.如上所述,在排序超过100M的元素时,您可能需要考虑这一点.

我看到你正在寻找一个8-32核心的系统.PSRS算法避免了共享资源上的争用,从而允许在更多数量的进程中加速.我已经演示了如上所述的最多4个核心的算法,但其他人的实验结果报告接近线性加速,核心数量大得多,32个以上.PSRS算法的缺点是它不是就地并且需要相当多的存储器.

如果您感兴趣,可以对每种算法使用或仔细阅读我的Java代码.你可以在github上找到它:https://github.com/broadbear/sort.该代码旨在作为Java Collections.sort()的替代品.如果您正在寻找能够在JVM中执行并行排序的功能,那么我的仓库中的代码可能会帮助您解决问题.对于实现Comparable或实现自己的Comparator的元素,API是完全通用的.

请问您要将那些元素分类为什么？我很想知道我的分拣包的潜在应用.