opengl - GLSL 中的快速排序？

Question

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

Answer 1

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

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

我只能笼统地说:

对于小型数据集，排序算法实际上并不重要。虽然人们一生都在担心对于非常大的数据库来说哪种排序算法是最好的，但对于小 N 来说，是否使用快速排序、堆排序、基数排序、希尔排序、优化冒泡排序、未优化冒泡排序实际上并不重要，等等。至少对于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]);
  }
}