哪种并行排序算法的平均事例性能最好?

下面的文章(pdf下载)是对各种架构上并行排序算法的比较研究:

Parallel sorting algorithms on various architectures

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

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

以下是最近的一些文章,介绍了一些更新颖的东西(从2007年开始,顺便说一句,与样本排序相比仍然是如此):

Improvements on sample sort
AA-Sort

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

Parallel sorting pattern
Many-core GPU based parallel sorting
Hybrid CPU/GPU parallel sort
Randomized Parallel Sorting Algorithm with an Experimental Study
Highly scalable parallel sorting
Sorting N-Elements Using Natural Order: A New Adaptive Sorting Approach

2013年更新: 这是2013年1月左右的出血边缘。(注:其中一些链接指向Citeseer的论文,需要免费注册):

大学讲座:
Parallel Partitioning for Selection and Sorting
Parallel Sorting Algorithms Lecture
Parallel Sorting Algorithms Lecture 2
Parallel Sorting Algorithms Lecture 3

其他来源和论文:
A novel sorting algorithm for many-core architectures based on adaptive bitonic sort
Highly Scalable Parallel Sorting 2
Parallel Merging
Parallel Merging 2
Parallel Self-Sorting System for Objects
Performance Comparison of Sequential Quick Sort and Parallel Quick Sort Algorithms
Shared Memory, Message Passing, and Hybrid Merge Sorts for Standalone and Clustered SMPs
Various parallel algorithms (sorting et al) including implementations

GPU和CPU/GPU混合源和论文:
An OpenCL Method of Parallel Sorting Algorithms for GPU Architecture
Data Sorting Using Graphics Processing Units
Efficient Algorithms for Sorting on GPUs
Designing efficient sorting algorithms for manycore GPUs
Deterministic Sample Sort For GPUs
Fast in-place sorting with CUDA based on bitonic sort
Fast parallel GPU-sorting using a hybrid algorithm
Fast Parallel Sorting Algorithms on GPUs
Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort
GPU sample sort
GPU-ABiSort: Optimal Parallel Sorting on Stream Architectures
GPUTeraSort: high performance graphics co-processor sorting for large database management
High performance comparison-based sorting algorithm on many-core GPUs
Parallel external sorting for CUDA-enabled GPUs with load balancing and low transfer overhead
Sorting on GPUs for large scale datasets: A thorough comparison

我已经使用了并行快速排序算法和PSRS算法,它们基本上是将快速排序与合并结合在一起的。

使用并行快速排序算法,我演示了近线性加速,最多4个核心(双核心,超线程),考虑到算法的局限性,这是预期的。纯并行快速排序依赖于共享的堆栈资源,这将导致线程之间的争用,从而降低性能的任何增益。这种算法的优点是它可以“就地”排序,从而减少了所需的内存量。在按照您的说明对100米以上的元素进行排序时,您可能需要考虑这一点。

我看到你正在寻找一个8-32核的系统。PSRS算法避免了在共享资源上的争用,允许在更多进程上加速。我已经演示了上面提到的最多4个核心的算法,但是其他人的实验结果显示,核心数量更大,超过32个,几乎是线性加速。PSRS算法的缺点是它没有就位,需要相当多的内存。

如果您感兴趣,您可以使用或使用这些算法中的每一个Java代码。你可以在Github上找到它: https://github.com/broadbear/sort . 代码的目的是作为Java集合的替代。如果您正在寻找在上面所述的JVM中执行并行排序的能力,那么我的repo中的代码可能会帮助您解决问题。对于实现可比较或实现自己的比较器的元素,API是完全通用的。

我可以问一下你要为这些元素排序的目的是什么吗?我有兴趣了解我的分类包的潜在应用程序。

看看这篇论文: A Scalable Parallel Sorting Algorithm Using Exact Splitting . 它涉及32多个核心。然而,它详细描述了一种运行时间复杂度为o(n/p*log(n)+p*log(n)**2)的算法,适用于任意比较器。

论文 "Comparison of Parallel Sorting Algorithms on Different Architectures" 可能是你开始的好地方。