投票和洗牌以优化原子操作

原文

几年前，我开始研究我的第一个CUDA实现的多粒子碰撞动力学(MPC)算法，一个粒子在 cell 内的代码，用来模拟溶剂和溶质之间的流体动力学相互作用。作为该算法的一部分，需要对若干粒子参数进行求和，计算出一定的 cell 参数。这是在 Tesla GPU 架构(比如 GT200 GPU，计算能力1.x)的时代，它的原子操作性能很差。我开发的一种链表方法在 Tesla 和 Fermi 上运行良好，作为原子加法的替代品，但在 Kepler GPU 上表现不佳。然而，在 Kepler 和 Maxwell 体系结构上，原子操作要快得多，所以使用原子加法是有意义的。

这些类型的求和不仅限于 MPC 或 cell 内的粒子代码，在某种程度上，只要按键聚合数据元素，就会发生这种求和。对于具有大量可能值的按键排序和组合的数据元素，在 warp 级别预先组合具有相同键的元素可以显著加快速度。在这篇文章中，我将描述一些算法，这些算法可以加速您对大量键的求和(或类似的聚合)，其中线程索引和键之间存在合理的相关性。这通常是适用于至少部分有序的元素的情况。不幸的是，这个参数在两个方向上都适用:如果键的数量很少或者键的分布是随机的，那么这些算法就不适合您。澄清一下:我说的“大量”键是指如果所有的 bin 都放在共享内存中，那么就无法处理这么多键。

文章来源: panda1234lee.blog.csdn.net，作者：panda1234lee，版权归原作者所有，如需转载，请联系作者。

原文链接：panda1234lee.blog.csdn.net/article/details/88916870