6

我正在考虑使用 GLSL 着色器将大量处理移植到 GPU。我偶然发现的一个直接问题是，在其中一个步骤中，算法需要维护一个元素列表，对它们进行排序并取几个最大的元素（哪个数字取决于数据）。在 CPU 上，这只是使用 STL 向量和 qsort() 来完成，但在 GLSL 中我没有这样的设施。有没有办法解决这个缺陷？

4

3 回答 3

15

披露：我真的不知道 GLSL——我一直在使用具有不同编程语言的 AMD Stream SDK 进行 GPGPU 编程。

从您对 Bjorn 回答的评论中，我了解到您对使用 GPU 对庞大的数据库进行排序不感兴趣——比如创建反向电话簿或其他任何东西，但是相反，您有一个小数据集，每个片段都有自己的数据集种类。更像是尝试进行中值像素过滤？

我只能笼统地说：

对于小型数据集，排序算法真的无关紧要。虽然人们一直在担心哪种算法对于超大型数据库来说是最好的排序算法，但对于小 N 来说，使用快速排序、堆排序、基数排序、Shell 排序、优化冒泡排序、未优化冒泡排序、等等。至少它在 CPU 上并不重要。

GPU 是 SIMD 设备，因此它们希望每个内核都以锁步执行相同的操作。计算很便宜，但分支很昂贵，并且每个内核以不同方式分支的数据相关分支非常、非常、非常、昂贵。

因此，如果每个内核都有自己的小数据集进行排序，并且要排序的数据数量取决于数据，并且每个内核可能是不同的数字，那么您最好选择最大大小（如果可以的话），填充具有无穷大或一些大数的数组，并让每个内核执行完全相同的排序，这将是未优化的无分支冒泡排序，如下所示：

伪代码（因为我不知道 GLSL），9 分

#define TwoSort(a,b) { tmp = min (a, b); b = a + b - tmp; a = tmp; }
for (size_t n = 8; n ; --n) {
  for (size_t i = 0; i < n; ++i) {
    TwoSort (A[i], A[i+1]);
  }
}
于 2009-04-14T20:21:18.570 回答
5

你看过这篇文章吗？ https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html

我不确定您是在寻找快速排序算法还是快速排序算法。文章中的算法使用归并排序...

于 2009-04-05T12:13:51.823 回答
2

我对GPU编程一无所知。

我会使用堆排序而不是快速排序，因为您说您只需要查看前几个值。堆可以及时构建O(n)，但是获取top值是log(n). 因此，如果您需要的值的数量明显小于元素的总数，您可以获得一些性能。

于 2009-04-26T08:49:57.573 回答