在CUDA上有什么好的排序算法？

Question

我有一个struct数组,我需要根据struct(N)的属性对这个数组进行排序.该对象如下所示:

 struct OBJ
 { 
   int N; //sort array of OBJ with respect to N
   OB *c; //OB is another struct
 } 

数组大小很小,大约有512个元素,但每个元素的大小都很大,因此我无法将数组复制到共享内存中.

排序这个数组的最简单和"好"的方法是什么？我不需要一个需要大量时间来实现的复杂算法(因为数组中的元素数量很少)我只需要一个简单的算法.

注意:我已经阅读了一些关于使用GPU排序算法的论文,但这些论文的速度增益仅在阵列大小非常大时出现.因此我没有尝试实现他们的算法,因为我的数组的大小很小.我只需要一种简单的方法来并行排序我的数组.谢谢.

Answer 1

什么意思是"大"和"小"？

通过"大"我假设你的意思是> 1M元素,而小 - 小到足以实际适合共享内存(可能是<1K元素).如果我对"小"的理解与你的相符,我会尝试以下方法:

• 只使用一个块对数组进行排序(它可以是一些更大的CUDA内核的一部分)
• Bitonic排序是并行算法可以采用的优秀算法之一.

一些关于bitonic排序的页面:

• Bitonic排序(很好的解释,可视化的applet和不占用太多空间的java源码)
• 维基百科(对我的口味有点太简短的解释,但更多源代码 - 一些抽象语言和Java)
• NVIDIA代码示例(CUDA中的示例源代码.我认为它有点过于专注于杀死银行冲突.我相信更简单的代码可能实际上执行得更快)

我曾经为单个warp实现了一个冒泡排序(lol!)来对32个元素的数组进行排序.由于其简单性,它实际上并没有那么糟糕.尽管如此,精心调整的bitonic排序仍然会表现得更快.