cuda - CUDA 内核中的中值选择

Question

我需要计算 CUDA 内核中大小为 p 的数组的中位数（在我的情况下，p 很小，例如 p = 10）。为了简单起见，我使用了 O(p^2) 算法，但代价是时间性能。

是否有一个“函数”可以有效地找到我可以在 CUDA 内核中调用的中位数？

我知道我可以实现一个选择算法，但我正在寻找一个函数和/或测试代码。

谢谢！

Answer 1

这里有一些提示：

2. 使用更好的选择算法：QuickSelect是 QuickSort 的更快版本，用于选择数组中的第 k 个元素。对于编译时常量掩码大小，排序网络甚至更快，这要归功于高 TLP 和 O(log^2 n) 关键路径。如果您只有 8 位值，则可以使用基于直方图的方法。本文描述了一种实现，每个像素花费恒定的时间，与掩码大小无关，这使得它对于非常大的掩码大小非常快。您可以通过使用最小启动策略（仅运行尽可能多的线程以使所有 SM 保持最大容量）、平铺图像并让同一块的线程在每个内核直方图上协作来并行化它。
3. 在寄存器中排序。对于较小的掩码大小，您可以将整个数组保存在寄存器中，从而使排序网络的中值选择更快。对于较大的掩码大小，您可以使用共享内存。
4. 首先将块使用的所有像素复制到共享内存，然后复制到也在共享内存中的线程本地缓冲区。
5. 如果您只有几个需要非常快的掩码（例如 3x3 和 5x5），请使用模板使它们成为编译时间常量。这可以大大加快速度，因为编译器可以展开循环并重新排序更多指令，可能会改进负载批处理和其他好东西，从而大大提高速度。
6. 确保您的读取是合并和对齐的。

您还可以进行许多其他优化。确保您通读了CUDA 文档，尤其是编程指南和最佳实践指南。当您真的想追求高性能时，不要忘记仔细查看 CUDA 分析器，例如Visual Profiler。

Answer 2

即使在单个线程中，也可以对数组进行排序并在 O(p*log(p)) 中选择中间的值，这使得 O(p^2) 看起来过多。如果您有 p 个线程可供使用，也可以像 O(log(p)) 一样快地对数组进行排序，尽管这可能不是小 p 的最快解决方案。在此处查看最佳答案：

哪种并行排序算法具有最好的平均案例性能？