本小节将会以并行规约求和算法为例，以Naïve Reduce为起点，针对5.4.2小节的三个基本步骤，逐步地探求并行规约算法的优化策略，以最大化地提升算法性能。

1.work-group内规约优化

（1）bank conflict

在AMDGCN架构的GPU上，每一个CU均包含一个64KB的本地数据共享（Local Data Share，LDS），LDS包含32个bank，每一个bank为4B宽，256B高，bank之间相邻。也可以简单地把LDS理解成一个256×32的二维数组，数组元素大小为4B。在同一个时钟周期内，每个bank都能够独立地工作.如果出现有多个线程同时访问处于同一个bank内的不同地址时，相关操作将无法并行地执行，将会串行化，这种情况叫作bank conflict。bank conflict的产生导致了线程访问LDS的串行化，严重影响着loca lmemory的访存效率。

根据图5-15的第一层规约可以看出，由于相邻的两个线程一个进行规约操作，而另一个则被屏蔽处于空转状态，连续的线程并没有访问连续的bank，如线程0与线程16将同时访问Bank0，线程1与线程17访问bank1等，此为2-way-bank-conflict。通过优化，如图5-16所示，通过连续的线程访问连续的数据，连续的32个线程将会访问连续的bank，有效地避免bank conflict，进一步提升算法性能。

（2）wavefront优化

wavefront是GPU调度和执行的基本单元，64个线程组成一个wavefront。图5-16规约过程与图5-15规约过程进行对比，当wavefront内部所有线程均执行相同操作以及减少活跃wavefront数目，将对性能带来提升。

1）减少wavefront内条件分支。由图5-15及Naïve Reduce可知，执行规约的线程ID并不连续，意味着同一个wavefront的线程存在着分支，一部分线程负责规约操作，一部分线程则空转。每一次的for循环内，都进行了条件判断，通过线程ID以屏蔽部分不需要进行规约操作的线程，此种逻辑判断中，令相邻的线程无法执行相同工作，导致了wavefront内部线程的分支执行，从而降低了程序的并行化，降低了算法性能。

2）减少活跃wavefront数目。由图5-15及Naïve Reduce可知，wavefront内只有一半线程处于工作状态，另一半线程处于空转状态。当一个wavefront内所有线程都参与至规约工作，如图5-16所示，一个wavefront所能处理的数据量将会翻倍，进而有效地减少活跃wavefront数目，优化后版本活跃wavefront数目约为Naïve Re-duce的一半。

（3）Divergence-Free Kernel算法

综合以上分析，提出Divergence-Free Kernel，针对Naïve Reduce所存在的不足进行改进，通过跨步寻址取数操作，避免了wavefront内部线程的条件分支。另一方面，由于一个wavefront所能处理的数据增加，以致所需活跃wavefront数目减少。因此，Divergence-Free Kernel可以提高并行规约算法的性能。

Divergence-Free Kernel算法与Naïve Reduce的不同之处在于步骤2的work-group内规约。

Divergence-Free Kernel的规约过程如图5-16所示。

根据图5-16可以清晰看出，从第一次循环开始，每一个线程以work-group所申请的local memory Size（即代码中的lSize）的一半，即lSize/2大小作为寻址跨度，读出两个数据进行累加（二分法）。规约过程中所使用的线程ID是连续的，所访问的数据也是连续的，即对bank进行连续访问，解决了local memory的bank conflict。此外，减少了wavefront内部线程的条件分支，使wavefront内部所有线程都执行相同操作。与此同时，因为wavefront内部线程的充分利用，因而减少了活跃wavefront的数目。其活跃wavefront数目约为Naïve Reduce算法的一半。因此性能得到较大的提升。从图5-15的Naïve版本和work-group内规约优化，可以看出，相对于Naïve Reduce，通过解决bank conflict和优化wavefront，work-group内规约优化算法Divergence-Free Kernel性能得到大幅的提升。

2.循环展开

（1）Last-Wavefront-Unroll Kernel

本算法针对最后一个wavefront-size的循环进行展开。对于Divergence-Free Kernel而言，首先从硬件资源组织上分析，每一个wavefront由64个线程组成，wavefront是GPU调度与执行的基本单位，wavefront内所有线程均执行相同的指令，4个cycle执行完一个wavefront，由此可知，对于Divergence-Free Kernel中的for循环，每一次迭代需要调用barrier（）进行本地同步，再进行下一层规约。

当运行线程数小于或等于64时，即运行线程都属于同一个wavefront时，可以省去显式的本地同步操作。因为wavefront是GPU调度与执行的基本单位，当work-group内活跃线程数少于或等于64时，即可免去本地同步操作，以提升算法性能。

因此，本小节的首个展开循环Kernel为Last-Wavefront-Unroll Kernel。Last-Wavefront-Unroll Kernel在Divergence-Free Kernel的基础上修改了步骤2中work-group内规约算法的循环结束条件，当所需线程数小于或等于一个wavefront所含线程数目4时结束循环，并进行显式的规约操作，从而减少本地同步函数的调用，实现更高的性能。

当for循环启用线程数小于或等于64时，终止循环，然后对剩余线程进行显式的规约操作。因此，if语句内的显式规约操作过程可以省去本地同步函数。正是由于所展开的部分循环不需要再使用barrier函数进行显式本地同步，因此算法性能得到提高.

此外，值得注意的是在显式规约过程中，需要使用volatile指示符，以强制地使规约操作是对内存直接进行读写，否则，规约过程会将运算结果暂存于寄存器，最终导致结果的不正确。

（2）Completely-Unroll Kernel(www.daowen.com)

考虑到在GCN架构的GPU中，OpenCL程序限制一个work-group在单一维度上最多开启256个线程。因此，在Last-Wavefront-Unroll Kernel的基础上，提出Completely-Unroll Kernel。Completely-Unroll Kernel展开所有for循环，涉及一个work-group内部多个活跃wavefront间的同步问题，因此仍需要显式的本地同步。

3.线程内规约优化

分析上文的并行规约算法，在步骤1的数据传输算法中，把global memory数据通过线程一一对应地读入local memory之后，从第一步规约开始，有一半的线程是处于空闲状态的，因此造成了极大的资源浪费。

为了更充分地利用资源，让所有线程均参与规约操作，对global memory数据加载至local memory的过程进行优化处理，此过程可以把每一个线程简单的读写操作改为规约操作，如把原本每次只读一个数据变成读两个数据再累加，把累加结果写入local memory相应位置。如此一来，在步骤2的work-group内规约算法之前，所有的线程均进行了一次规约操作，此处把该规约过程定义为线程内规约。

线程内规约算法有两种不同方式的实现，其实现的区别主要在于每个线程跨步寻址的步长。依据线程内规约算法中步长的不同，下面将分别列出Stride-Global-Size Kernel和Stride-Local-Size Kernel。

Stride-Global-Size Kernel：每一个线程以全局线程总数，即global-size大小为寻址跨度，读取相距global-size的两个或多个元素（取决于参数times），进行累加，然后把累加结果写入local memory的ISum数组，再执行work-group内规约算法。

Stride-Local-Size Kernel：每一个线程以work-group内线程数，即local-size大小为跨度，读取相距local-size的两个或多个元素（取决于参数times，下文将在两种情况下对times进行使用说明），进行累加，然后把累加结果写入local memory的ISum数组，再执行work-group内规约算法。

为了更好地观察对线程内规约算法对性能的影响，下面将对Stride-Global-Size Kernel和Stride-Local-Size Kernel在参数times进行两种不同场景的应用。

（1）Stride-Global-SizeKernel

Stride-Global-Size Kernel只需在Completely-Unroll Kernel步骤1的数据传输算法中加入线程内规约算法。

（2）Stride-Local-Size Kernel

同样，Stride-Local-Size Kernel只需在Completely-Unroll Kernel步骤1的数据传输算法中加入线程内规约算法，其与Stride-Global-Size Kernel的区别在于步骤1所包含的线程内规约算法的Stride不同。

（3）控制全局线程数

此场景将设置参数times=数据总量/全局线程数。work-group数目为NUM-Work-Group=全局线程数/局部线程数，由于局部线程数固定为256，因此work-group数量将会十分充足，能够有效地隐藏访存延迟。但是由于硬件CU（computer unit）数目是固定的，大量的work-group可能无法均衡地分配至所有的CU。

（4）控制work-group数目

此场景将设置参数times=数据总量/（局部线程数×NUM-work-group）。work-group的数目将会以硬件CU数目为基准，乘以倍数参数（即CU的倍数），观察在均衡使用CU情况下，适当地调整倍数以观察适量的work-group数目均衡使用CU情况下对性能的影响。

4.向量化

从上述内容可知，Stride-Global-Size Kernel和Stride-Local-Size Kernel两个算法的寻址跨度可以长达global size或者local size的距离，而本部分内容实现的Vector-Size Kernel算法中，向量化操作为相邻数据的规约操作，即跨度为1。因此，Vector-Size Kernel算法与Stride-Global-Size Kernel和Stride-Local-Size Kernel的区别在于并行规约步骤1所包含的线程内规约算法的不同。由于一些GPU硬件上对向量化操作进行了优化，为了观测向量化编程对并行规约算法的影响，独立于上述内容，以更好地独立分析GCN架构GPU对向量化操作的执行情况。

由于OpenCL平台向量类型的限制，Vector-Size Kernel算法的times只能取值为2、4、8、16。因此有四种不同的实现，本节给出其中一种，数据类型为uint4。

在Vector-Size Kernel算法中，每一个线程将读取一个向量，即将会读取相邻的多个数据，寻址跨度为1个数据单位。