本节书摘来自华章社区《CUDA C编程权威指南》一书中的第3章，第3.4节避免分支分化，作者[美] 马克斯·格罗斯曼（Max Grossman） ，更多章节内容可以访问云栖社区“华章社区”公众号查看
3.4 避免分支分化
有时，控制流依赖于线程索引。线程束中的条件执行可能引起线程束分化，这会导致内核性能变差。通过重新组织数据的获取模式，可以减少或避免线程束分化。在本节里，将会以并行归约为例，介绍避免分支分化的基本技术。
3.4.1 并行归约问题
假设要对一个有N个元素的整数数组求和。使用如下的串行代码很容易实现算法：
如果有大量的数据元素会怎么样呢？如何通过并行计算快速求和呢？鉴于加法的结合律和交换律，数组元素可以以任何顺序求和。所以可以用以下的方法执行并行加法运算：
1.将输入向量划分到更小的数据块中。
2.用一个线程计算一个数据块的部分和。
3.对每个数据块的部分和再求和得出最终结果。
并行加法的一个常用方法是使用迭代成对实现。一个数据块只包含一对元素，并且一个线程对这两个元素求和产生一个局部结果。然后，这些局部结果在最初的输入向量中就地保存。这些新值被作为下一次迭代求和的输入值。因为输入值的数量在每一次迭代后会减半，当输出向量的长度达到1时，最终的和就已经被计算出来了。
根据每次迭代后输出元素就地存储的位置，成对的并行求和实现可以被进一步分为以下两种类型：
相邻配对：元素与它们直接相邻的元素配对
交错配对：根据给定的跨度配对元素
尽管以上代码实现的是加法，但任何满足交换律和结合律的运算都可以代替加法。例如，通过调用max代替求和运算，就可以计算输入向量中的最大值。其他有效运算的例子有最小值、平均值和乘积。
在向量中执行满足交换律和结合律的运算，被称为归约问题。并行归约问题是这种运算的并行执行。并行归约是一种最常见的并行模式，并且是许多并行算法中的一个关键运算。
在本节里，会实现多个不同的并行归约核函数，并且将测试不同的实现是如何影响内核性能的。
3.4.2 并行归约中的分化
图3-21所示的是相邻配对方法的内核实现流程。每个线程将相邻的两个元素相加产生部分和。
在这个内核里，有两个全局内存数组：一个大数组用来存放整个数组，进行归约；另一个小数组用来存放每个线程块的部分和。每个线程块在数组的一部分上独立地执行操作。循环中迭代一次执行一个归约步骤。归约是在就地完成的，这意味着在每一步，全局内存里的值都被部分和替代。__syncthreads语句可以保证，线程块中的任一线程在进入下一次迭代之前，在当前迭代里每个线程的所有部分和都被保存在了全局内存中。进入下一次迭代的所有线程都使用上一步产生的数值。在最后一个循环以后，整个线程块的和被保存进全局内存中。
两个相邻元素间的距离被称为跨度，初始化均为1。在每一次归约循环结束后，这个间隔就被乘以2。在第一次循环结束后，idata（全局数据指针）的偶数元素将会被部分和替代。在第二次循环结束后，idata的每四个元素将会被新产生的部分和替代。因为线程块间无法同步，所以每个线程块产生的部分和被复制回了主机，并且在那儿进行串行求和，如图3-22所示。
从Wrox.com上可以找到reduceInteger.cu完整的源代码。代码清单3-3只列出了主函数。
初始化输入数组，使其包含16M元素：
在接下来的一节中，这些结果将会被作为性能调节的基准。
3.4.3 改善并行归约的分化
测试核函数reduceNeighbored，并注意以下条件表达式：
if ((tid % (2 * stride)) == 0)
因为上述语句只对偶数ID的线程为true，所以这会导致很高的线程束分化。在并行归约的第一次迭代中，只有ID为偶数的线程执行这个条件语句的主体，但是所有的线程都必须被调度。在第二次迭代中，只有四分之一的线程是活跃的，但是所有的线程仍然都必须被调度。通过重新组织每个线程的数组索引来强制ID相邻的线程执行求和操作，线程束分化就能被归约了。图3-23展示了这种实现。和图3-21相比，部分和的存储位置并没有改变，但是工作线程已经更新了。
修改之后的内核代码如下：
3.4.4 交错配对的归约
与相邻配对方法相比，交错配对方法颠倒了元素的跨度。初始跨度是线程块大小的一半，然后在每次迭代中减少一半（如图3-24所示）。在每次循环中，每个线程对两个被当前跨度隔开的元素进行求和，以产生一个部分和。与图3-23相比，交错归约的工作线程没有变化。但是，每个线程在全局内存中的加载/存储位置是不同的。
交错归约的内核代码如下所示：
交错实现比第一个实现快了1.69倍，比第二个实现快了1.34倍。这种性能的提升主要是由reduceInterleaved函数里的全局内存加载/存储模式导致的。在第4章里会介绍更多有关于全局内存加载/存储模式对内核性能的影响。reduceInterleaved函数和reduceNeigh-boredLess函数维持相同的线程束分化。
