是否有算法来排序GPU的字符串数组？

要排序的数组大约有一百万个字符串，其中每个字符串的长度可以高达一百万个字符。是否有算法来排序GPU的字符串数组？

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

我有一块大小约为1MB的数据，我需要构建suffix array。现在你可以看到如何在真正少量的内存中有一百万个字符串。

2010-07-15 Kentzo

'1M'字符字符串（avg'.5M'？），'1M'字符串，2字节/字符（最常见）产生：'.5 * 1 * 2 = 1TB'内存。你需要一些特别的东西（可能是数据库？），因为很少有机器存在这种内存，更不用说GPU内存了。 http://blogs.technet.com/b/markrussinovich/archive/2008/07/21/3092070.aspx – Abel 2010-07-15 12:52:35

最大的字符串长度没有说什么关于平均。我假设字符串已经在内存中并正在排序，但是海报对任务中的CPU性能不满意。 – 2010-07-15 12:54:05

了解数据的结构可能是相关/有用的。它是由'\ 0'分隔的一堆连续字符串吗？字符串前面是一个保存字节数的头文件吗？或者有一堆指向堆的指针？我们在谈论ASCII字符串还是Unicode？ – 2010-07-15 12:56:13

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

对于排序32位整数，2009年的以下论文（有2位作者是Nvidia的研究人员）只比GTX280上的最佳CUDA排序增加23％，而4核心Yorkfield排名最好。

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

这用在GPU基数排序和归并排序的CPU。您需要基于比较的排序才能构建后缀数组，因此，不是GPU基数排序，本文中最好的排序是GPU合并排序，它实现了GPU基数排序的一半速度（有100万键） - 比CPU合并类型慢大约40％。

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

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

但是，如果你的目的是试验，或只是为了了解GPU，那么你可以找到在CUDA SDK纸上的CUDA实现合并排序的：每

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

来源

2010-07-17 05:37:21 RD1

CUDA的重点不在于使用闲置的处理器吗？即使GPU在GPU上的速度没有提高，但如果能够有效利用额外的并行性，与仅使用CPU相比，仍然可以提高2倍的性能。 – 2010-07-17 05:40:03

@罗伯特哈维 - CUDA的大部分用途不会使CPU同时处于繁忙状态。然而最近这种情况已经变得越来越普遍，通常被称为混合GPU/CPU。需要在CPU和GPU之间复制内存往往会使得获得良好的性能变得非常棘手。在这种情况下，我希望最多可以达到CPU速度的150％，而且最好还是投资于带有两个CPU的系统。 – RD1 2010-07-17 07:17:45

感谢您的回答。我同意所有关于在GPU上对字符串进行排序的笔记，我以同样的方式思考，但我曾希望有一种我错过的算法。 – Kentzo 2010-07-17 14:42:41

是否有算法来排序GPU的字符串数组？

回答

相关问题