在GLSL中快速排序？

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

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

从你评论Bjorn的答案,我得知你对使用GPU排序庞大的数据库不感兴趣 - 比如创建一个反向电话簿或者其他什么,但是你有一个小数据集,每个片段都有它自己的数据集到分类.更像是尝试进行中值像素滤波？

我只能说:

对于小型数据集,排序算法确实无关紧要.虽然人们已经花了很多职业担心哪个是非常大的数据库的最佳排序算法,但对于小N来说,无论你使用快速排序,堆排序,基数排序,Shell排序,优化冒泡排序,未优化冒泡排序,至少在CPU上并不重要.

GPU是SIMD设备,因此他们希望每个内核在锁定步骤中执行相同的操作.计算很便宜,但分支很昂贵,并且每个内核以不同方式分支的数据依赖分支非常非常非常昂贵.

因此,如果每个内核都有自己的小数据集进行排序,并且要排序的数据数量依赖于数据,并且每个内核的数量可能不同,那么最好选择最大大小(如果可以的话),填充具有Infinity或一些大数字的数组,并且每个内核执行完全相同的排序,这将是一个未经优化的无分支冒泡排序,如下所示:

伪代码(因为我不知道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]);
  }
}

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

我不确定您是在寻找Quicksort算法还是快速排序算法.本文中的算法使用合并排序...