string - 是否有用于 GPU 的字符串数组排序算法？

Question

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

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

我有一个大小约为 1MB 的数据 block ，我需要构造 suffix array 。现在您可以看到如何在非常小的内存中容纳一百万个字符串。

Answer 1

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

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

http://www.mgarland.org/files/papers/gpusort-ipdps09.pdf

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

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

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

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

http://developer.download.nvidia.com/compute/cuda/sdk/website/Data-Parallel_Algorithms.html