哪种并行排序算法具有最佳的平均情况性能? [英] Which parallel sorting algorithm has the best average case performance?
问题描述
在串行情况下排序需要 O(n log n).如果我们有 O(n) 个处理器，我们希望线性加速.存在 O(log n) 并行算法，但它们具有非常高的常数.它们也不适用于没有接近 O(n) 处理器的商品硬件.对于 p 个处理器，合理的算法应该花费 O(n/p log n) 时间.
Sorting takes O(n log n) in the serial case. If we have O(n) processors we would hope for a linear speedup. O(log n) parallel algorithms exist but they have a very high constant. They also aren't applicable on commodity hardware which doesn't have anywhere near O(n) processors. With p processors, reasonable algorithms should take O(n/p log n) time.
在串行情况下，平均而言，快速排序具有最佳的运行时复杂度.并行快速排序算法很容易实现(参见这里和此处).然而，它的性能并不好，因为第一步是在单个核心上对整个集合进行分区.我已经找到了许多并行排序算法的信息，但到目前为止我还没有看到任何指向明显赢家的信息.
In the serial case, quick sort has the best runtime complexity on average. A parallel quick sort algorithm is easy to implement (see here and here). However it doesn't perform well since the very first step is to partition the whole collection on a single core. I have found information on many parallel sort algorithms but so far I have not seen anything pointing to a clear winner.
我希望在 8 到 32 个内核上运行的 JVM 语言中对包含 100 万到 1 亿个元素的列表进行排序.
I'm looking to sort lists of 1 million to 100 million elements in a JVM language running on 8 to 32 cores.
推荐答案
以下文章(PDF下载)是对各种架构上的并行排序算法的对比研究:
The following article (PDF download) is a comparative study of parallel sorting algorithms on various architectures:
根据文章，sample sort 似乎在许多并行架构类型上是最好的.
According to the article, sample sort seems to be best on many parallel architecture types.
更新以解决 Mark 对年龄的担忧:
Update to address Mark's concern of age:
这里有更多最近的文章介绍了一些更新颖的东西(从 2007 年开始，顺便说一句，仍然可以与样本排序进行比较):
Here are more recent articles introducing something more novel (from 2007, which, btw, still get compared with sample sort):
最前沿(大约 2010 年，有些只有几个月大):
The bleeding edge (circa 2010, some only a couple months old):
并行排序模式
基于多核 GPU 的并行排序
混合 CPU/GPU 并行排序
随机并行排序算法与实验研究
高度可扩展的并行排序
使用自然顺序对 N 元素进行排序:一种新的自适应排序方法
2013 年更新:这是大约 2013 年 1 月的最新消息.(注意:一些链接指向 Citeseer 上的论文，需要免费注册):
Update for 2013:
Here is the bleeding edge circa January, 2013. (Note: A few of the links are to papers at Citeseer and require registration which is free):
大学讲座:
用于选择和排序的并行分区
并行排序算法讲座
并行排序算法第 2 课
并行排序算法第三讲
其他来源和论文:
一种新的基于自适应双音排序的多核架构排序算法
高度可扩展的并行排序 2
并行合并
并行合并 2
对象的并行自排序系统
顺序快速排序和并行快速排序算法的性能比较
独立和集群的共享内存、消息传递和混合合并排序中小事务所
各种并行算法(排序等)，包括实现
GPU 和 CPU/GPU 混合来源和论文:
一种用于 GPU 架构的并行排序算法的 OpenCL 方法
使用图形处理单元进行数据排序
在 GPU 上进行排序的高效算法
为众核 GPU 设计高效的排序算法
GPU 的确定性样本排序
使用基于双音排序的 CUDA 进行快速就地排序
使用混合算法的快速并行 GPU 排序
GPU 上的快速并行排序算法
CPU 和 GPU 上的快速排序:不考虑带宽的 SIMD 排序的案例
GPU 样本排序
GPU-ABiSort:流架构上的最佳并行排序
GPUTeraSort:用于大型数据库管理的高性能图形协处理器排序
众核GPU上基于比较的高性能排序算法
具有负载平衡和低传输开销的支持 CUDA 的 GPU 的并行外部排序
在 GPU 上为大规模数据集排序:彻底比较
2021 年更新:我没有忘记这个答案，就像所有与计算机相关的东西一样，它没有老化.我将尽最大努力在今年年底(2021 年)之前的某个时间点针对当前趋势和最新技术更新和刷新它.
Update for 2021: I have not forgotten this answer and like all things computer related, it has not aged well. I will do my best to update and refresh it for current trends as well as the state of the art, at some point prior to the end of this year (2021).
这篇关于哪种并行排序算法具有最佳的平均情况性能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
