cuda - CUDA 内核中的中值选择

Question

我需要计算 CUDA 内核中大小为 p 的数组的中值(在我的例子中，p 很小，例如 p = 10)。我使用 O(p^2) 算法是为了它的简单性，但以牺牲时间性能为代价。

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

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

谢谢!

Answer 1

这里有一些提示:

1. 使用更好的选择算法:QuickSelect是快速排序的更快版本，用于选择数组中的第 k 个元素。对于编译时常量掩码大小，sorting networks由于高 TLP 和 O(log^2 n) 关键路径，甚至更快。如果您只有 8 位值，则可以使用基于直方图的方法。 This paper描述了一个每个像素花费恒定时间的实现，与掩码大小无关，这使得非常大的掩码大小非常快。您可以通过使用最小的启动策略(只运行您需要的线程数，以使所有 SM 保持最大容量)、平铺图像并让同一 block 的线程在每个内核直方图上协作来对其进行并行化。
2. Sort in registers.对于较小的掩码大小，您可以将整个数组保存在寄存器中，使用 sorting network 进行中值选择。快多了。对于更大的 mask 尺寸，您可以使用 shared memory .
3. 将 block 使用的所有像素复制到shared memory首先，然后复制到也在共享内存中的线程本地缓冲区。
4. 如果您只有几个需要非常快的掩码(例如 3x3 和 5x5)，use templates使它们成为编译时间常数。这可以大大加快速度，因为编译器可以展开循环并重新排序更多的指令，可能会改进加载批处理和其他好处，从而实现大幅加速。
5. 确保你的读数是coalesced and aligned .

您还可以进行许多其他优化。确保您通读了 CUDA documents ，尤其是 Programming Guide和 Best Practices Guide .当你真的想追求高性能时，不要忘记好好看看 CUDA 分析器，比如 Visual Profiler .