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

Question

我有大量的数据需要排序,数百万个数组,每个数组有数万个值.我想知道以下内容:

最好是在GPU上实现并行排序算法,并在所有阵列上运行它

要么

实现单线程算法,如quicksort,并为GPU的每个线程分配一个不同的数组.

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

要排序的数据类型很长,所以我不相信基数排序是可能的,因为它的数字的二进制表示将太长.

任何指针将不胜感激.

Answer 1

排序是一项受到很多关注的操作.如果您对高性能感兴趣,则不建议编写自己的排序.我认为是这样的推力,back40computing,moderngpu,或CUB在GPU上进行排序.

以上大多数将使用完整的GPU对数组进行排序,一次处理一个数组.有一些技术可以进行矢量化排序,可以"同时"处理多个数组,而CUB也可以选择进行"每线程"排序(比方说,"每个线程块").

一般来说,我会对CPU排序代码说同样的话.不要自己写.

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

1. 大多数快速分拣工作都是按照第一种方法进行的,而不是第二种方法.
2. 当工作适应SIMD或SIMT时,GPU通常更快速.这意味着我们通常希望每个线程都做同样的事情并最小化分支和扭曲发散.在第二种情况下,这很难实现(我认为),其中每个线程看起来遵循相同的序列,但实际上数据依赖性导致"算法分歧".从表面上看,你可能想知道第一种方法是否可能会受到同样的批评,但是由于我提到的这些库是专家写的,他们知道如何最好地利用SIMT架构.推力"矢量化排序"和CUB方法将允许每次操作完成多种排序,同时仍然利用SIMT架构.