我正在学习udacity问题集的课程，从一长串numElems值中计算numBins元素的直方图。在这种简单的情况下，每个元素的值也是直方图中他自己的bin，因此用CPU代码生成直方图就像一样简单
for (i = 0; i < numElems; ++i)
histo[val[i]]++;
我没有得到"快速直方图计算"的视频解释，根据该解释，我应该按照"粗略bin id"对值进行排序，然后计算最终直方图。
问题是：
- 为什么要按"粗略bin索引"对值进行排序
为什么要按"粗略bin索引"对值进行排序？
这是一种将工作分解为可以由单个线程块处理的部分的尝试。这里有几个考虑因素：
- 在GPU上，最好有多个线程块，这样所有SM都可以参与解决问题
- 给定的线程块在单个SM上生存和操作，因此它被限制在该SM上可用的资源内，主要限制是线程数量和可用共享内存的大小
- 由于共享内存特别有限，因此工作划分为每个线程块创建较小大小的直方图操作，该直方图操作可能适合SM共享内存，而整个直方图范围可能不适合。例如，如果我在4位十进制数字的范围内进行直方图，那么总共将有10000个bin。每个bin可能需要一个
int值，即40K字节，这几乎不适合共享内存（作为占用限制器，可能会对性能产生负面影响）。超过5位小数的直方图可能不合适。另一方面，使用一个十进制数字的"粗略bin排序"，我可以将每个块的共享内存需求从40K字节减少到4K字节（大约）
共享内存原子通常比全局内存原子快得多，因此以这种方式分解工作可以有效地使用共享内存原子，这可能是一种有用的优化。
所以我必须先对所有值进行排序？这不是比阅读并将原子添加到正确的垃圾桶更贵吗？
也许吧。但粗bin排序的想法是，它在计算上可能比全排序便宜得多。基数排序是一种常用的、相对快速的排序操作，可以在GPU上并行完成。基数排序的特点是，排序操作从最高有效的"数字"开始，并迭代进行到最低有效的数字。然而，粗bin排序意味着实际上只需要对最高有效数字的某个子集进行"排序"。因此，使用基数排序技术的"粗略bin排序"在计算上可能比完全排序便宜。如果如udcity示例所示，只对3位数字中的最高有效数字进行排序，则意味着您的排序成本仅为完全排序的约1/3。
我并不是说这在任何情况下都能保证更快的性能。细节很重要（例如直方图的大小、范围、仓的最终数量等）您使用的特定GPU也可能影响权衡。例如，开普勒和更新的设备将大大改进全局内存原子论，因此比较将受到这一点的实质性影响。（OTOH，Pascal大大改进了共享内存原子，这将再次影响另一个方向的比较。）