什么是CUDA上好的排序算法？

Question

我有一个结构体数组，需要根据结构体的某个属性（N）对该数组进行排序。对象的结构如下：

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

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

对于这个数组，最简单且“好”的排序方法是什么？ 我不需要复杂算法来实现（由于数组中的元素数量很少），我只需要一个简单的算法。

注意：我已经阅读了一些使用GPU进行排序算法的论文，但仅当数组大小非常大时才会显示出这些论文的速度提升。 因此，我没有尝试实现它们的算法，因为我的数组很小。 我只需要一个简单的并行排序方法。 谢谢。

- liz

---

对于只排序一个小数组，无论如何都无法使GPU饱和。如果同时还有其他内核需要运行，可能更容易在CPU端进行排序。然而，如果您有许多小列表（像您的列表一样最多有~500个项目），那么类似的问题是无序透明性。请参见此处。您需要提取键和索引列表，对其进行排序，然后使用索引重新排序或按排序顺序读取。 - jozxyqk

Answer 1

我需要翻译的内容如下：

“大”和“小”的意思是什么？

如果您所说的“大”是指超过1M个元素，而“小”则是指足够小以适合共享内存（可能少于1K个元素）。 如果我的“小”的理解与您的相匹配，我建议尝试以下操作：

• 仅使用单个块对数组进行排序（它可以成为某个更大的CUDA内核的一部分）
• 双调排序是可以采用的良好并行算法之一。

有关双调排序的一些页面：

• 比特位排序（清晰的解释，可视化应用和不占用太多空间的Java源代码）
• 维基百科（对我来说有点太简短的解释，但有更多的源代码-一些抽象语言和Java）
• NVIDIA代码示例（CUDA中的示例源代码。我认为它过于专注于消除银行冲突。我相信较简单的代码实际上可能会执行得更快）

我曾经为一个单独的warp实现了一个冒泡排序（哈哈！），用于对32个元素的数组进行排序。由于其简单性，它实际上表现得并不差。但是，经过良好调整的比特位排序仍然会更快。

- CygnusX1

---

我曾经也实现过冒泡排序——你肯定要去开发者地狱了！ - Mitch Wheat

插入排序和冒泡排序在GPU上的表现很好，即使是100个项目。低SIMD分歧。双调排序算法不错，但必须有2^n个项目或少于此数（例如513），否则速度会相对较慢。 - jozxyqk

Answer 2

使用CUDPP或Thrust库中提供的排序函数。

如果使用cudppSort，请注意它只适用于整数或浮点数。要对结构数组进行排序，可以先对键和索引数组进行排序。然后，可以使用已排序的索引数组将结构移动到其最终排序位置。我在博客文章这里中描述了如何在cudppCompact压缩算法中执行此操作。对于使用cudppSort对结构数组进行排序，步骤类似。

- Ashwin Nanjappa

---

Cudpp具有归并排序和基数排序，顺带一提。 - einpoklum

Answer 3

你为什么要使用CUDA呢？我的意思是，你的问题似乎不是CUDA擅长解决的问题。你只需要对512个元素的数组进行排序，并让一些指针引用另一个位置。这并不是什么高级操作，可以使用简单的串行算法来完成，例如快速排序、堆排序或归并排序。

此外，考虑从堆栈复制数据到CUDA设备所需的开销。只有当计算强度足够大，使得在CUDA上的计算时间+从堆栈复制数据到CUDA设备的时间+从CUDA设备复制数据到堆栈的时间 < 在主机CPU上的计算时间时，使用CUDA才有意义。

此外，CUDA在处理大向量和矩阵以及相对简单的数据类型（数字）的数学计算方面非常强大，因为这是GPU经常遇到的问题之一：计算图形。

- crusoe

Answer 4

是的，我完全同意，对于小数组（＜5k元素）进行排序的开销会抵消您在CUDA中实现“精细调整”的并行排序算法可能获得的加速效果。 对于这样一个小尺寸，我更喜欢基于CPU的排序...

- Salman Ul Haq

---

有时，您需要在CUDA上解决一个更大的问题，而需要排序的这些（有时是多个）小数组可能只是您代码的“副产品”。在这种情况下，完全可以在CUDA上进行排序，而不是将这些数据发送到主机，使用CPU并再次发送回GPU。 - CygnusX1