CUDA中并行规约（Parallel Reduction）的优化

川长思鸟来 2022-06-04 04:36 414阅读 0赞

Parallel Reduction是NVIDIA-CUDA自带的例子，也几乎是所有CUDA学习者的的必看算法。在这个算法的优化中，Mark Harris为我们实现了7种不同的优化版本，将Bandwidth几乎提高到了峰值。相信我们通过仔细研读这个过程，一定能对CUDA程序的优化有更加深刻的认识。

下面我们来一一细看这几种优化方案，数据和思想均摘录自官方SDK中Samples的算法说明。

### Parallel Reduction ###

Parallel Reduction可以理解为将一个数组中的所有数相加求和的过程并行化。一般来讲，我们并行化的思路是基于“树”的二元规约，如下图：

![Center][]

但是这样的算法会产生一个问题，就是我们怎样让不同blocks中的线程通信呢？CUDA本身并不支持全局同步（global synchronization）。但是，CUDA的kernel运行时有一个特性，即同一时间只能有一个kernel运行，这样我们便可以将每一层规约作为一个kernel来重复递归调用。如下图：

![17449943][]

我们的目标就是基于这个算法进行优化，达到“榨干CUDA性能”的目的。我们选取Bandwidth作为测量标准（因为Bandwidth侧重于测量memory-bound kernels，而GFLOP/s侧重于测量compute-bound kernels）。我们最终目标是实现最大的Data Bandwidth。测试环境为G80 GPU，384-bit memory interface, 900 MHz DDR，Bandwidth峰值384 \* 1800 / 8 = 86.4 GB/s。

对于基本概念，放上一张图供参考：

[![base][]][base]

### Reduction \#1: Interleaved Addressing ###

Interleaved Addressing的核心思想在于交错寻址，即典型的树状模型。示意图如下：

[![Interleaved\_Addressing][Interleaved_Addressing]][Interleaved_Addressing]

存在的问题：

上述代码中for循环内部，容易出现线程束的分化（Warp Divergence），即同一个Warp中的线程需要执行不同的逻辑分支（详见[这里][Link 1]），这是非常低效的，而且 `&` 运算也是非常慢的。测试结果如下(4M element)：

注意：Block Size = 128 threads for all tests.

### Reduction \#2: Interleaved Addressing ###

为了尽量减少1中的线程束的分化，我们这一步将分化的分支替换为跨步寻址（strided index）：

示意图如下（注意下图与上图中Thread ID的区别）：

[![Interleaved\_Addressing2][Interleaved_Addressing2]][Interleaved_Addressing2]

这里我们遇到一个新的问题，即Shared Memory Bank Conflicts。为了达到高带宽，Shared Memory被划分成许多大小相同的内存块，叫做Banks。Banks可以同步访问，即不同的地址对不同的Banks可以同时读写。但是，如果两个内存请求的地址落到同一个Bank上，将会导致Bank Conflicts，严重影响并行程序的性能。

运行结果如下(4M element)：

### Reduction \#3: Sequential Addressing ###

我们知道，CUDA中对数据的连续读取效率要比其它方式高。因此我们这一步优化主要是将取址方式变为连续的。我们只需要将2中跨步寻址（strided index）替换为基于threadID的逆向for循环即可。

示意图如下：

[![Sequential\_Addressing][Sequential_Addressing]][Sequential_Addressing]

但新的问题又出现了，我们发现在for循环中，因为 `if (tid < s)` 的缘故，在第一次循环的时候有一半的线程都处于闲置状态！如果我们能全部利用的话，相信性能还会提升很多。这也是我们以后要进行优化的地方，避免线程闲置。

本次运行结果如下(4M element)：

### Reduction \#4: First Add During Load ###

在以前的所有版本中，我们都是事先将global的数据读入共享内存 `sdata[tid] = (i < n) ? g_idata[i] : 0;` ，我们可不可以在这一步进行优化呢？当然，我们这一步优化的目的是在将数据读入到共享内存时同时进行第一次(第一层)规约。

本次运行结果如下(4M element)：

### Reduction \#5: Unroll The Loop ###

这时我们的数据带宽已经达到了17 GB/s，而我们清楚Reduction的算术强度（arithmetic intensity）很低，因此系统的瓶颈可能是由于Parallel Slowdown，即系统对于指令、调度的花费超过了实际数据处理的花费。在本例中即address arithmetic and loop overhead。

我们的解决办法是将for循环展开（Unroll the loop）。我们知道，在Reduce的过程中，活动的线程数是越来越少的，当活动的线程数少于32个时，我们将只有一个线程束（Warp）。在单个Warp中，指令的执行遵循SIMD（Single Instruction Multiple Data）模式，也就是说在活动线程数少于32个时，我么不需要进行同步控制，即我们不需要`if (tid < s)` 。

<table style="border-collapse:collapse; border-spacing:0px; max-width:100%; background-color:transparent"> 
 <tbody style=""> 
  <tr style=""> 
   <td style=""> 
    <div style="margin:0px; padding:0px"> 
     <div style="margin:0px; padding:0px">
       1 
     </div> 
     <div style="margin:0px; padding:0px">
       2 
     </div> 
     <div style="margin:0px; padding:0px">
       3 
     </div> 
     <div style="margin:0px; padding:0px">
       4 
     </div> 
     <div style="margin:0px; padding:0px">
       5 
     </div> 
     <div style="margin:0px; padding:0px">
       6 
     </div> 
     <div style="margin:0px; padding:0px">
       7 
     </div> 
     <div style="margin:0px; padding:0px">
       8 
     </div> 
     <div style="margin:0px; padding:0px">
       9 
     </div> 
     <div style="margin:0px; padding:0px">
       10 
     </div> 
     <div style="margin:0px; padding:0px">
       11 
     </div> 
     <div style="margin:0px; padding:0px">
       12 
     </div> 
     <div style="margin:0px; padding:0px">
       13 
     </div> 
     <div style="margin:0px; padding:0px">
       14 
     </div> 
     <div style="margin:0px; padding:0px">
       15 
     </div> 
     <div style="margin:0px; padding:0px">
       16 
     </div> 
     <div style="margin:0px; padding:0px">
       17 
     </div> 
     <div style="margin:0px; padding:0px">
       18 
     </div> 
     <div style="margin:0px; padding:0px">
       19 
     </div> 
     <div style="margin:0px; padding:0px">
       20 
     </div> 
     <div style="margin:0px; padding:0px">
       21 
     </div> 
     <div style="margin:0px; padding:0px">
       22 
     </div> 
     <div style="margin:0px; padding:0px">
       23 
     </div> 
     <div style="margin:0px; padding:0px">
       24 
     </div> 
     <div style="margin:0px; padding:0px">
       25 
     </div> 
     <div style="margin:0px; padding:0px">
       26 
     </div> 
     <div style="margin:0px; padding:0px">
       27 
     </div> 
     <div style="margin:0px; padding:0px">
       28 
     </div> 
     <div style="margin:0px; padding:0px">
       29 
     </div> 
     <div style="margin:0px; padding:0px">
       30 
     </div> 
     <div style="margin:0px; padding:0px">
       31 
     </div> 
     <div style="margin:0px; padding:0px">
       32 
     </div> 
     <div style="margin:0px; padding:0px">
       33 
     </div> 
     <div style="margin:0px; padding:0px">
       34 
     </div> 
     <div style="margin:0px; padding:0px">
       35 
     </div> 
     <div style="margin:0px; padding:0px">
       36 
     </div> 
     <div style="margin:0px; padding:0px">
       37 
     </div> 
     <div style="margin:0px; padding:0px">
       38 
     </div> 
     <div style="margin:0px; padding:0px">
       39 
     </div> 
     <div style="margin:0px; padding:0px">
       40 
     </div> 
     <div style="margin:0px; padding:0px">
       41 
     </div> 
     <div style="margin:0px; padding:0px">
       42 
     </div> 
     <div style="margin:0px; padding:0px">
       43 
     </div> 
     <div style="margin:0px; padding:0px">
       44 
     </div> 
     <div style="margin:0px; padding:0px">
       45 
     </div> 
     <div style="margin:0px; padding:0px">
       46 
     </div> 
     <div style="margin:0px; padding:0px">
       47 
     </div> 
     <div style="margin:0px; padding:0px">
       48 
     </div> 
     <div style="margin:0px; padding:0px">
       49 
     </div> 
     <div style="margin:0px; padding:0px">
       50 
     </div> 
     <div style="margin:0px; padding:0px">
       51 
     </div> 
     <div style="margin:0px; padding:0px">
       52 
     </div> 
     <div style="margin:0px; padding:0px">
       53 
     </div> 
     <div style="margin:0px; padding:0px">
       54 
     </div> 
     <div style="margin:0px; padding:0px">
       55 
     </div> 
     <div style="margin:0px; padding:0px">
       56 
     </div> 
     <div style="margin:0px; padding:0px">
       57 
     </div> 
     <div style="margin:0px; padding:0px">
       58 
     </div> 
     <div style="margin:0px; padding:0px">
       59 
     </div> 
     <div style="margin:0px; padding:0px">
       60 
     </div> 
     <div style="margin:0px; padding:0px">
       61 
     </div> 
     <div style="margin:0px; padding:0px">
       62 
     </div> 
     <div style="margin:0px; padding:0px">
       63 
     </div> 
     <div style="margin:0px; padding:0px">
       64 
     </div> 
     <div style="margin:0px; padding:0px">
       65 
     </div> 
     <div style="margin:0px; padding:0px">
       66 
     </div> 
     <div style="margin:0px; padding:0px">
       67 
     </div> 
     <div style="margin:0px; padding:0px">
       68 
     </div> 
     <div style="margin:0px; padding:0px">
       69 
     </div> 
     <div style="margin:0px; padding:0px">
       70 
     </div> 
     <div style="margin:0px; padding:0px">
       71 
     </div> 
     <div style="margin:0px; padding:0px">
       72 
     </div> 
     <div style="margin:0px; padding:0px">
       73 
     </div> 
     <div style="margin:0px; padding:0px">
       74 
     </div> 
     <div style="margin:0px; padding:0px">
       75 
     </div> 
     <div style="margin:0px; padding:0px">
       76 
     </div> 
     <div style="margin:0px; padding:0px">
       77 
     </div> 
     <div style="margin:0px; padding:0px">
       78 
     </div> 
     <div style="margin:0px; padding:0px">
       79 
     </div> 
    </div> </td> 
   <td style=""> 
    <div style="margin:0px; padding:0px"> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">/*</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;This version unrolls the last warp to avoid synchronization where it</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;isn't needed.</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;Note, this kernel needs a minimum of 64*sizeof(T) bytes of shared memory.</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;In other words if blockSize &lt;= 32, allocate 64*sizeof(T) bytes.</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;If blockSize &gt; 32, allocate blockSize*sizeof(T) bytes.</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">*/</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">template</span> 
      <span style="margin:0px; padding:0px">&lt;</span> 
      <span style="margin:0px; padding:0px">class</span> 
      <span style="margin:0px; padding:0px">T</span> 
      <span style="margin:0px; padding:0px">,</span> 
      <span style="margin:0px; padding:0px">unsigned</span> 
      <span style="margin:0px; padding:0px">int</span> 
      <span style="margin:0px; padding:0px">blockSize</span> 
      <span style="margin:0px; padding:0px">&gt;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">__global__&nbsp;</span> 
      <span style="margin:0px; padding:0px">void</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">reduce4</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">T</span> 
      <span style="margin:0px; padding:0px">*</span> 
      <span style="margin:0px; padding:0px">g_idata</span> 
      <span style="margin:0px; padding:0px">,</span> 
      <span style="margin:0px; padding:0px">T</span> 
      <span style="margin:0px; padding:0px">*</span> 
      <span style="margin:0px; padding:0px">g_odata</span> 
      <span style="margin:0px; padding:0px">,</span> 
      <span style="margin:0px; padding:0px">unsigned</span> 
      <span style="margin:0px; padding:0px">int</span> 
      <span style="margin:0px; padding:0px">n</span> 
      <span style="margin:0px; padding:0px">)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">{ </span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">T</span> 
      <span style="margin:0px; padding:0px">*</span> 
      <span style="margin:0px; padding:0px">sdata</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">SharedMemory</span> 
      <span style="margin:0px; padding:0px">&lt;</span> 
      <span style="margin:0px; padding:0px">T</span> 
      <span style="margin:0px; padding:0px">&gt;</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">)</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">// perform first level of reduction,</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">// reading from global memory, writing to shared memory</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">unsigned</span> 
      <span style="margin:0px; padding:0px">int</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">threadIdx</span> 
      <span style="margin:0px; padding:0px">.</span> 
      <span style="margin:0px; padding:0px">x</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">unsigned</span> 
      <span style="margin:0px; padding:0px">int</span> 
      <span style="margin:0px; padding:0px">i</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">blockIdx</span> 
      <span style="margin:0px; padding:0px">.</span> 
      <span style="margin:0px; padding:0px">x</span> 
      <span style="margin:0px; padding:0px">*</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">blockDim</span> 
      <span style="margin:0px; padding:0px">.</span> 
      <span style="margin:0px; padding:0px">x</span> 
      <span style="margin:0px; padding:0px">*</span> 
      <span style="margin:0px; padding:0px">2</span> 
      <span style="margin:0px; padding:0px">)</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">threadIdx</span> 
      <span style="margin:0px; padding:0px">.</span> 
      <span style="margin:0px; padding:0px">x</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">T</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">i</span> 
      <span style="margin:0px; padding:0px">&lt;</span> 
      <span style="margin:0px; padding:0px">n</span> 
      <span style="margin:0px; padding:0px">)</span> 
      <span style="margin:0px; padding:0px">?</span> 
      <span style="margin:0px; padding:0px">g_idata</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">i</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">:</span> 
      <span style="margin:0px; padding:0px">0</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">if</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">i</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">blockSize</span> 
      <span style="margin:0px; padding:0px">&lt;</span> 
      <span style="margin:0px; padding:0px">n</span> 
      <span style="margin:0px; padding:0px">)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">g_idata</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">i</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">blockSize</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">sdata</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">__syncthreads</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">)</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">// do reduction in shared mem</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">for</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">unsigned</span> 
      <span style="margin:0px; padding:0px">int</span> 
      <span style="margin:0px; padding:0px">s</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">blockDim</span> 
      <span style="margin:0px; padding:0px">.</span> 
      <span style="margin:0px; padding:0px">x</span> 
      <span style="margin:0px; padding:0px">/</span> 
      <span style="margin:0px; padding:0px">2</span> 
      <span style="margin:0px; padding:0px">;</span> 
      <span style="margin:0px; padding:0px">s</span> 
      <span style="margin:0px; padding:0px">&gt;</span> 
      <span style="margin:0px; padding:0px">32</span> 
      <span style="margin:0px; padding:0px">;</span> 
      <span style="margin:0px; padding:0px">s</span> 
      <span style="margin:0px; padding:0px">&gt;&gt;</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">1</span> 
      <span style="margin:0px; padding:0px">)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">{ </span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">if</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">&lt;</span> 
      <span style="margin:0px; padding:0px">s</span> 
      <span style="margin:0px; padding:0px">)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">{ </span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">sdata</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">sdata</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">s</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">}</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">__syncthreads</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">)</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">}</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">if</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">&lt;</span> 
      <span style="margin:0px; padding:0px">32</span> 
      <span style="margin:0px; padding:0px">)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">{ </span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">// now that we are using warp-synchronous programming (below)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">// we need to declare our shared memory volatile so that the compiler</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">// doesn't reorder stores to it and induce incorrect behavior.</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">volatile</span> 
      <span style="margin:0px; padding:0px">T</span> 
      <span style="margin:0px; padding:0px">*</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">sdata</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">if</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">blockSize</span> 
      <span style="margin:0px; padding:0px">&gt;=</span> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">64</span> 
      <span style="margin:0px; padding:0px">)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">{ </span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">32</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">}</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">if</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">blockSize</span> 
      <span style="margin:0px; padding:0px">&gt;=</span> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">32</span> 
      <span style="margin:0px; padding:0px">)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">{ </span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">16</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">}</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">if</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">blockSize</span> 
      <span style="margin:0px; padding:0px">&gt;=</span> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">16</span> 
      <span style="margin:0px; padding:0px">)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">{ </span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">8</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">}</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">if</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">blockSize</span> 
      <span style="margin:0px; padding:0px">&gt;=</span> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">8</span> 
      <span style="margin:0px; padding:0px">)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">{ </span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">4</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">}</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">if</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">blockSize</span> 
      <span style="margin:0px; padding:0px">&gt;=</span> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">4</span> 
      <span style="margin:0px; padding:0px">)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">{ </span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">2</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">}</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">if</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">blockSize</span> 
      <span style="margin:0px; padding:0px">&gt;=</span> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">2</span> 
      <span style="margin:0px; padding:0px">)</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">{ </span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">mySum</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">smem</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">+</span> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">1</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">}</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">}</span> 
     </div> 
     <div style="margin:0px; padding:0px">
       &nbsp; 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">// write result for this block to global mem</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">&nbsp;&nbsp;&nbsp;&nbsp;</span> 
      <span style="margin:0px; padding:0px">if</span> 
      <span style="margin:0px; padding:0px">(</span> 
      <span style="margin:0px; padding:0px">tid</span> 
      <span style="margin:0px; padding:0px">==</span> 
      <span style="margin:0px; padding:0px">0</span> 
      <span style="margin:0px; padding:0px">)</span> 
      <span style="margin:0px; padding:0px">g_odata</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">blockIdx</span> 
      <span style="margin:0px; padding:0px">.</span> 
      <span style="margin:0px; padding:0px">x</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">=</span> 
      <span style="margin:0px; padding:0px">sdata</span> 
      <span style="margin:0px; padding:0px">[</span> 
      <span style="margin:0px; padding:0px">0</span> 
      <span style="margin:0px; padding:0px">]</span> 
      <span style="margin:0px; padding:0px">;</span> 
     </div> 
     <div style="margin:0px; padding:0px"> 
      <span style="margin:0px; padding:0px">}</span> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

注意，这在所有的warps中都省去了无用过的过程，不只是最后一个warp。如果不进行循环展开，则所有的warps都会执行for中的每一次循环和每一次if判断。

本次运行结果如下(4M element)：

今天我们暂时先分析到这里，SDK的示例中还有第六种和第七种优化方案，分别是Completely Unrolled和Multiple Adds / Thread，最后性能提升达30+x，我们以后有机会再仔细进行分析

[Center]: /images/20220604/2bc8c6e50cba4337a9cc9857cb96618b.png
[17449943]: /images/20220604/c120490f3f8d42839b2ab21f097fcce6.png
[base]: http://hackecho.com/wp-content/uploads/2013/10/base.png
[Interleaved_Addressing]: http://hackecho.com/wp-content/uploads/2013/10/Interleaved_Addressing.png
[Link 1]: http://people.maths.ox.ac.uk/gilesm/cuda/lecs/lec3-2x2.pdf
[Interleaved_Addressing2]: http://hackecho.com/wp-content/uploads/2013/10/Interleaved_Addressing2.png
[Sequential_Addressing]: http://hackecho.com/wp-content/uploads/2013/10/Sequential_Addressing.png