用共享内存计算直方图

Question

我跟着udacity习题集课从一个长系列的numBins值中计算numBins元素的直方图。在这种简单的情况下，每个元素的值在直方图中也是自己的bin，因此用CPU代码生成直方图就像

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

我没有得到关于“快速直方图计算”的视频解释，根据这种解释，我应该按照‘粗二进制id’对值进行排序，然后计算最后的直方图。

问题是：

• 为什么我要按“粗桶指数”对这些值进行排序？

Answer 1

为什么我要按“粗桶指数”对这些值进行排序？

这是试图将工作分解成可以由单个线程块处理的部分。这里有几个考虑因素：

1. 在GPU上，最好有多个线程块，这样所有SMs都可以参与解决这个问题。
2. 给定的线程块存在并在单个SM上运行，因此它仅限于该SM上可用的资源，主要限制是线程数量和可用共享内存的大小。
3. 由于共享内存是有限的，分工为每个线程块创建了一个较小的直方图操作，这可能适合于SM共享内存，而整体直方图范围可能不适用。例如，如果我在4位小数位的范围内进行直方图，那将是10,000个回收箱总数。每个bin可能需要一个int值，所以这是40K字节，这几乎不适合共享内存(并且作为占用率限制器可能会产生负面的性能影响)。超过5个小数位数的直方图可能不适合。另一方面，使用一位小数位的“粗桶排序”，我可以将每个块共享内存的需求从40千字节减少到4千字节(大约)。

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

所以我必须先对所有的值进行排序？这难道不比在正确的垃圾箱中阅读和执行atomicAdd更昂贵吗？

也许吧。但是，粗桶排序的想法是，从计算上看，它可能比一个完整的排序要便宜得多。基类是一种常用的、相对较快的排序操作，可以在GPU上并行执行。基排序的特点是排序操作从最重要的“数字”开始，然后迭代到最不重要的数字。然而，粗略的bin排序意味着实际上只需要对最重要数字的某些子集进行“排序”。因此，使用基排序技术的“粗桶排序”在计算上比完全排序要便宜得多。如果您只对3位中最重要的数字进行排序，如udacity示例所示，这意味着您的排序成本仅为完整排序的1/3。

我并不是说在每种情况下，这都是提高性能的保证。具体问题(如直方图的大小、范围、垃圾箱的最终数目等)您使用的特定GPU也可能影响权衡。例如，开普勒和更新的设备将大大改善全球内存原子，所以比较将受到很大的影响。(OTOH，Pascal大大改进了共享内存atomics，这将再次影响到另一个方向的比较。)