有没有为GPU排序字符串数组的算法？

Question

要排序的数组大约有一百万个字符串,其中每个字符串的长度最多可达一百万个字符.

我正在寻找GPU的排序算法的任何实现.

我有一个大小约1MB的数据块,我需要构造后缀数组.现在你可以看到如何在真正少量的内存中拥有一百万个字符串.

Answer 1

GPU 排序的最新技术水平并不特别令人鼓舞。

对于 32 位整数的排序，以下 2009 年的论文（两位作者都是 Nvidia 的研究人员）仅声称 GTX280 上的最佳 CUDA 排序与 4 核 Yorkfield 上的最佳 CPU 排序相比仅提高了 23%。

这在 GPU 上使用基数排序，在 CPU 上使用合并排序。您需要基于比较的排序才能构造后缀数组，因此论文中最好的方法不是 GPU 基数排序，而是 GPU 合并排序，它的速度大约是 GPU 基数排序的一半（100 万次排序）键） - 即比 CPU 合并排序慢约 40%。

添加可变长度密钥似乎可能会导致扭曲中的线程在 GPU 上不同步，因此与 CPU 相比，GPU 上的性能下降幅度更大。

总的来说，如果您的目的是构建一个高效的系统，我建议您使用 CPU 实现来解决这个问题，因为它会更快、更容易编写。

但是，如果您的目的是进行实验或只是了解 GPU，那么您可以从 CUDA SDK 中的论文中找到合并排序的 CUDA 实现：