c++ - CUDA 使用共享内存计算直方图

Question

我正在关注 a udacity problem set lesson从一长串 numElems 值中计算出 numBins 元素的直方图。在这个简单的例子中，每个元素的值也是他自己在直方图中的 bin，因此使用 CPU 代码生成直方图非常简单

for (i = 0; i < numElems; ++i)
  histo[val[i]]++;

我没有得到关于“快速直方图计算”的视频解释，根据该视频我应该按“粗略 bin id”对值进行排序，然后计算最终的直方图。

问题是:

• 为什么我应该按“粗略的 bin 索引”对值进行排序？

Answer 1

why should I sort the values by 'coarse bin indices'?

这是将工作分解为可由单个线程 block 处理的部分的尝试。这里有几个注意事项:

1. 在 GPU 上，最好有多个线程 block ，以便所有 SM 都可以参与解决问题。
2. 给定的线程 block 在单个 SM 上运行和运行，因此它受限于该 SM 上的可用资源，主要限制是线程数和可用共享内存的大小。
3. 由于共享内存特别有限，分工为每个线程 block 创建了一个更小的直方图操作，这可能适合 SM 共享内存，而整个直方图范围可能不适合。例如，如果我在 4 个十进制数字的范围内绘制直方图，则总共有 10,000 个分箱。每个 bin 可能需要一个 int 值，即 40Kbytes，这刚好适合共享内存(并且可能作为占用限制器对性能产生负面影响)。超过 5 个小数位的直方图可能不适合。另一方面，使用单个十进制数字的“粗分类”，我可以将每个 block 的共享内存需求从 40Kbytes 减少到 4Kbytes(大约)。

共享内存原子通常比全局内存原子快得多，因此以这种方式分解工作可以有效地使用共享内存原子，这可能是一种有用的优化。

so I will have to sort all the values first? Isn't that more expensive than reading and doing an atomicAdd into the right bin?

也许吧。但是粗分类的想法是它在计算上可能比完整分类要便宜得多。 radix sort是一种常用的、相对快速的排序操作，可以在 GPU 上并行完成。基数排序具有排序操作从最高有效“数字”开始并迭代进行到最低有效数字的特征。然而，粗分类意味着实际上只有最重要数字的某些子集需要“分类”。因此，使用基数排序技术的“粗分类”在计算上可能显着比完全排序更便宜。如 udacity 示例所示，如果您仅对 3 位数字中的最高有效位进行排序，则意味着您的排序成本仅为完整排序成本的大约 1/3。

我并不是说在任何情况下这都是提高性能的保证方法。具体情况很重要(例如直方图的大小、范围、最终的 bin 数量等)。您使用的特定 GPU 也可能影响权衡。例如，Kepler 和更新的设备将显着改进全局内存原子，因此比较将受到显着影响。 (OTOH，Pascal 大大改进了共享内存 原子，这将再次影响另一个方向的比较。)