我有大量数据需要排序，数百万个数组，每个数组有数万个值。我想知道的是：
在 GPU 上实现并行排序算法并在所有数组中运行它会更好吗
或者
实现单线程算法，如快速排序，并为 GPU 的每个线程分配不同的数组。
显然速度是最重要的因素。对于单线程排序算法，内存是一个限制因素。我已经尝试实现递归快速排序，但它似乎不适用于大量数据，所以我假设存在内存问题。
要排序的数据类型很长，所以我不相信基数排序是可能的，因为数字的二进制表示会太长。
任何指针将不胜感激。
问问题
3291 次
1 回答
5
排序是一个受到很多关注的操作。如果您对高性能感兴趣，不建议编写自己的排序。我会考虑使用诸如推力、back40computing、moderngpu或CUB之类的东西在 GPU 上进行排序。
以上大部分内容将一次处理一个数组，使用完整的 GPU 对数组进行排序。推力中有一些技术可以进行矢量化排序，可以“一次”处理多个数组，而 CUB 也可能是进行“每线程”排序（比如“每线程块”）的一种选择。
一般来说，我会对 CPU 排序代码说同样的话。不要自己写。
编辑：我猜还有一条评论。我会非常倾向于您提到的第一种方法（即不对每个线程进行排序。）这有两个相关的原因：
- 大多数快速排序工作都是按照您的第一种方法完成的，而不是第二种方法。
- 当工作非常适合 SIMD 或 SIMT 时，GPU 通常更快。这意味着我们通常希望每个线程都做同样的事情并最小化分支和扭曲发散。在第二种情况下（我认为）这更难实现，其中每个线程似乎都遵循相同的顺序，但实际上数据依赖性正在导致“算法分歧”。从表面上看，您可能想知道第一种方法是否会受到同样的批评，但由于我提到的这些库是由专家编写的，他们知道如何最好地利用 SIMT 架构。主旨“矢量化排序”和 CUB 方法将允许每个操作完成多个排序，同时仍然利用 SIMT 架构。
于 2013-07-13T19:26:33.363 回答