performance - 分支分歧、CUDA 和动力学蒙特卡洛

Question

所以，我有一个代码，它在格子上使用 Kinetic Monte Carlo 来模拟某些东西。我正在使用 CUDA 在我的 GPU 上运行此代码(尽管我相信同样的问题也适用于 OpenCl)。

这意味着我将我的格子分成小的子格子，每个线程都在其中一个上运行。由于我在做 KMC，每个线程都有这个代码:

   While(condition == true){
     *Grab a sample u from U[0,1]*
      for(i = 0; i < 100;i++){
         *Do some stuff here to generate A*
          if(A > u){
              *Do more stuff here, which could include updates to global memory*
               break();
           }
      }
   }

A 对于不同的线程是不同的，u 也是不同的，100 只是一个随机数。在代码中，这可能是 1000 甚至 10000。

那么，当一个线程通过 if 的时候，我们不会有分支分歧吗？这会对性能造成多大的影响？我知道答案取决于 if 子句中的代码，但是随着我添加越来越多的线程，这将如何扩展？

任何关于我如何估计性能损失/ yield 的引用也将受到欢迎。

谢谢!

Answer 1

GPU 以 32 个线程为一组运行线程，称为 warp。分歧只能发生在经线内。因此，如果您能够以 if 的方式排列线程，条件在整个扭曲中以相同的方式评估，没有分歧。

当 if 中存在分歧时，从概念上讲，GPU 只是忽略了来自线程的结果和内存请求，其中 if条件为假。

所以，假设 if计算结果为 true用于特定经纱中的 10 根线。在里面if ，warp 的潜在计算性能从 100% 降低到 10/32 * 100 = 31%，因为 if 禁用了 22 个线程本来可以工作的，但现在只是在经线中占据空间。

一旦退出 if ，禁用的线程再次启用，扭曲以 100% 的潜在计算性能继续进行。

一个 if-else行为方式大致相同。当经线到达 else ，在 if 中启用的线程变为禁用，而那些被禁用的变为启用。

在 for对于 warp 中的每个线程循环不同次数的循环，线程在其迭代计数达到其设定数时被禁用，但整个 warp 必须保持循环，直到具有最高迭代计数的线程完成。

在查看潜在的内存吞吐量时，事情有点复杂。如果算法是内存受限的，那么由于扭曲发散可能不会有太多或任何性能损失，因为内存事务的数量可能会减少。如果 warp 中的每个线程都从全局内存中完全不同的位置读取数据(对于 GPU 来说是一种糟糕的情况)，那么每个禁用线程的时间都将被节省下来，因为它们的内存事务不必执行。另一方面，如果线程正在从已针对 GPU 访问优化的数组中读取数据，则多个线程将共享单个事务的结果。在这种情况下，用于禁用线程的值是从内存中读取的，然后与禁用线程可能完成的计算一起丢弃。

所以，现在你可能已经有了足够的了解，可以做出很好的判断，判断扭曲散度会影响你的表现。最坏的情况是warp中只有一个线程处于事件状态。然后您将获得 1/32 = 3.125% 的计算绑定(bind)性能潜力。最好的情况是 31/32 = 96.875%。对于 if那是完全随机的，你得到 50%。如前所述，内存绑定(bind)性能取决于所需内存事务数量的变化。