CUDA并行排序算法与单线程排序算法

Question

我有大量的数据需要排序，几百万个数组，每个数组都有数万个值。我想知道的是：

是否更好地在GPU上实现并行排序算法，并在所有数组上运行它？

或

实现了单线程算法，比如快速排序，并为GPU的每个线程分配了一个不同的数组.。

显然，速度是最重要的因素。对于单线程排序算法来说，内存是一个限制因素。我已经尝试过实现递归的快速排序，但是它似乎不适用于大量的数据，所以我假设存在内存问题。

要排序的数据类型很长，所以我不相信基数排序是可能的，因为它是数字的二进制表示形式太长了。

如有任何指示，将不胜感激。

Answer 1

排序是一种受到广泛关注的操作。如果你对高性能感兴趣，写你自己的分类是不可取的。我会考虑像推力、back40computing、现代派或幼崽这样的东西来对GPU进行排序。

上面的大部分内容都是一次处理一个数组，使用完整的GPU对数组进行排序。推力中有一些技术可以“同时”处理多个数组，而CUB也可能是执行“每个线程”排序的一个选项(比方说，“每个线程块”)。

通常，对于CPU排序代码，我会说同样的话。别写你自己的。

编辑：我想还有一条评论。我倾向于您提到的第一种方法(即不对每个线程进行排序)。这有两个相关的原因：

1. 大多数快速排序工作都是按照第一种方法完成的，而不是第二种方法。
2. 当工作适合SIMD或SIMT时，GPU通常更擅长快速工作。这意味着我们通常希望每个线程都做同样的事情，并将分支和翘曲发散最小化。在第二种情况下，这很难实现(我认为)，在第二种情况下，每个线程似乎遵循相同的顺序，但实际上数据依赖导致了“算法差异”。从表面上看，您可能想知道是否会对第一种方法提出同样的批评，但是由于我提到的这些库是由专家编写的，他们知道如何最好地利用SIMT体系结构。推力“向量化排序”和CUB方法将允许每个操作执行多个排序，同时仍然利用SIMT体系结构。