分支分歧,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子句中的代码,但是随着我添加越来越多的线程,这将如何扩展？

关于如何估计性能损失/收益的任何参考也将受到欢迎.

谢谢!

Answer 1

GPU以32个线程为一组运行线程,称为warps.分歧只能在扭曲中发生.因此,如果您能够以这样的方式排列线程,使得if条件在整个warp中以相同的方式进行评估,那么就没有分歧.

当if概念上存在分歧时,GPU只是忽略if条件为假的线程的结果和内存请求.

所以,比如if评估true特定warp中的10个线程.在内部,if经线的潜在计算性能从100%降低到10/32*100 = 31%,因为被禁用的22个线程if可能已经正在工作但现在只占用了经线的空间.

退出后if,再次启用禁用的线程,并且warp继续以100%的潜在计算性能.

一个if-else在大致相同的方式表现.当warp到达时else,已if禁用的线程将被禁用,而已禁用的线程将被启用.

在for为warp中的每个线程循环不同次数的循环中,线程被禁用,因为它们的迭代计数达到它们的设置数,但整个warp必须保持循环,直到完成具有最高迭代计数的线程.

在考虑潜在的内存吞吐量时,事情会有点复杂.如果算法是存储器绑定的,则由于经线发散可能没有太多或任何性能损失,因为可以减少存储器事务的数量.如果warp中的每个线程都从全局内存中的完全不同的位置读取(GPU的情况很糟糕),则会为每个禁用的线程保存时间,因为不必执行它们的内存事务.另一方面,如果线程正在从已经针对GPU访问进行优化的阵列中读取,则多个线程将共享来自单个事务的结果.在这种情况下,从内存中读取用于禁用线程的值,然后与禁用线程可能完成的计算一起丢弃.

所以,现在你可能已经有了足够的概述,能够做出相当好的判断调用,以了解经线偏差会对你的表现产生多大影响.最糟糕的情况是当warp中只有一个线程处于活动状态时.然后得到1/32 = 3.125%的计算绑定性能潜力.最佳案例是31/32 = 96.875%.对于if完全随机的,您获得50%.如上所述,内存绑定性能取决于所需内存事务数量的变化.