如何在多GPU上实现基数排序?

这种方法可行,但我认为这不是最快的方法。具体来说,合并每K位的直方图(K=4目前是最好的)需要在gpu32/K=8次之间交换密钥来对32位整数进行排序。由于GPU之间的内存带宽(~5GB/s)远低于GPU上的内存带宽(~150GB/s),这将降低性能。

一个更好的策略是将数据分成多个部分,在不同的GPU上对每个部分进行并行排序,然后在最后合并这些部分。这种方法只需要一个GPU间的传输(与上面的8个相比),因此速度会快得多。

不幸的是,这个问题没有充分提出。这取决于元素的大小、元素在内存中的起始位置以及希望排序的元素最终驻留的位置。

有时,可以通过将元素存储在共享相同公共前缀的组中来压缩已排序的列表,也可以动态地存储唯一的元素,将每个元素存储在已排序的列表中一次,并使用关联的计数。例如,您可以将一个32位整数的大列表排序为64K个16位值的不同列表,从而将内存需求减半。

一般原则是,您希望尽可能减少传递数据的次数,并且吞吐量几乎总是与存储策略相关的带宽限制相对应。

如果您的数据集超过了快速内存的大小,您可能希望完成合并过程,而不是像其他人已经回答的那样继续基数排序。

我刚进入GPU架构,我不明白上面的K=4注释。我从来没有见过这样一个架构,这么小的K可以证明是最佳的。

我怀疑合并直方图也是错误的方法。我可能会让这些元素在内存中碎片化,而不是合并直方图。在GPU结构中管理中尺度散射/聚集列表有那么困难吗?我当然希望不会。

最后,很难想象为什么您要让多个GPU参与此任务。假设您的卡有2GB的内存和60GB/s的写入带宽(这就是我的中档卡所显示的)。三通基数排序(11位直方图)需要6GB的写入带宽(可能是您的速率限制因子),或者大约100毫秒来排序一个由32位整数组成的2GB列表。太好了,他们被分类了,现在怎么办?如果您需要将它们发送到其他地方,而不需要进行某种预处理或压缩,那么排序时间将很短。

不管怎样,今天刚刚编译了我的第一个示例程序。还有很多东西要学。我的目标应用程序是排列密集型的,这与排序密切相关。我相信以后我会再讨论这个问题的。