我有大量数据需要排序,数百万个数组,每个数组有数万个值。我想知道的是:
在 GPU 上实现并行排序算法并在所有数组中运行它会更好吗
或者
实现单线程算法,如快速排序,并为 GPU 的每个线程分配不同的数组。
显然速度是最重要的因素。对于单线程排序算法,内存是一个限制因素。我已经尝试实现递归快速排序,但它似乎不适用于大量数据,所以我假设存在内存问题。
要排序的数据类型很长,所以我不相信基数排序是可能的,因为数字的二进制表示会太长。
任何指针将不胜感激。
我有大量数据需要排序,数百万个数组,每个数组有数万个值。我想知道的是:
在 GPU 上实现并行排序算法并在所有数组中运行它会更好吗
或者
实现单线程算法,如快速排序,并为 GPU 的每个线程分配不同的数组。
显然速度是最重要的因素。对于单线程排序算法,内存是一个限制因素。我已经尝试实现递归快速排序,但它似乎不适用于大量数据,所以我假设存在内存问题。
要排序的数据类型很长,所以我不相信基数排序是可能的,因为数字的二进制表示会太长。
任何指针将不胜感激。
排序是一个受到很多关注的操作。如果您对高性能感兴趣,不建议编写自己的排序。我会考虑使用诸如推力、back40computing、moderngpu或CUB之类的东西在 GPU 上进行排序。
以上大部分内容将一次处理一个数组,使用完整的 GPU 对数组进行排序。推力中有一些技术可以进行矢量化排序,可以“一次”处理多个数组,而 CUB 也可能是进行“每线程”排序(比如“每线程块”)的一种选择。
一般来说,我会对 CPU 排序代码说同样的话。不要自己写。
编辑:我猜还有一条评论。我会非常倾向于您提到的第一种方法(即不对每个线程进行排序。)这有两个相关的原因: