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

Question

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

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

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

score 4 · Accepted Answer

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

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

这在 GPU 上使用基数排序，在 CPU 上使用合并排序。您需要基于比较的排序来构建后缀数组，因此本文中最好的方法不是 GPU 基数排序，而是 GPU 合并排序，它实现了 GPU 基数排序的一半左右的速度（100 万键） - 即比 CPU 合并排序慢 40%。

添加可变长度键似乎可能会导致扭曲中的线程在 GPU 上不同步，因此会降低 GPU 上的性能而不是 CPU。

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

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

1 回答 1