是否有用于 GPU 的字符串数组排序算法？
要排序的数组大约有一百万个字符串，其中每个字符串的长度最多可达一百万个字符。
我正在寻找 GPU 排序算法的任何实现。
我有一个大小约为 1MB 的数据块，我需要构造 后缀数组。现在您可以看到如何在非常小的内存中容纳一百万个字符串。
Array to sort has approximately one million strings, where every string can have length up to one million characters.
I am looking for any implementation of sorting algorithm for GPU.
I have a block of data with size approximately 1MB and I need to construct suffix array. Now you can see how it is possible to have one million strings inside really small amount of memory.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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%。
添加可变长度密钥似乎可能会导致 warp 中的线程在 GPU 上不同步，因此与 CPU 相比，GPU 上的性能下降幅度更大。
总的来说，如果您的目的是构建一个高效的系统，我建议您使用 CPU 实现来解决这个问题，因为它会更快、更容易编写。
但是，如果您的目的是进行实验或只是了解 GPU，那么您可以从 CUDA SDK 中的论文中找到合并排序的 CUDA 实现：
http://developer.download.nvidia.com/compute/cuda/sdk/website/Data-Parallel_Algorithms.html
The state of the art in GPU sorting isn't particularly encouraging.
For sorting 32-bit integers the following paper from 2009 (with 2 authors who are researchers at Nvidia) only claims 23% increase for the best CUDA sort on GTX280 compared to the best CPU sort on a 4 core Yorkfield.
http://www.mgarland.org/files/papers/gpusort-ipdps09.pdf
This used a radix sort on the GPU, and merge sort on CPU. You'd need a comparison-based sort in order to construct a suffix array, so instead of GPU radix sort the best of those in the paper would be GPU merge sort, which achieved about half the speed of GPU radix sort (with 1 million keys) - ie about 40% slower than the CPU merge sort.
Adding variable length keys seems likely to cause threads in a warp will get out of sync on a GPU, so would reduce the performance on GPU more than CPU.
Overall if your purpose is to build an efficient system, I'd recommend that you use a CPU implementation for this problem because it will be faster and easier to write.
But, if your purpose is to experiment or just to learn about GPU, then you can find the CUDA implementation of merge sort from the paper in the CUDA SDK:
http://developer.download.nvidia.com/compute/cuda/sdk/website/Data-Parallel_Algorithms.html