本節書摘來自華章計算機《CUDA C編程權威指南》一書中的第3章，第3.4節，作者 [美] 馬克斯·格羅斯曼（Max Grossman），譯 顏成鋼 殷建 李亮，更多章節內容可以訪問云棲社區“華章計算機”公眾號查看。

3.4　避免分支分化

有時，控制流依賴于線程索引。線程束中的條件執行可能引起線程束分化，這會導致內核性能變差。通過重新組織數據的獲取模式，可以減少或避免線程束分化。在本節里，將會以并行歸約為例，介紹避免分支分化的基本技術。

3.4.1　并行歸約問題

假設要對一個有N個元素的整數數組求和。使用如下的串行代碼很容易實現算法：

如果有大量的數據元素會怎么樣呢？如何通過并行計算快速求和呢？鑒于加法的結合律和交換律，數組元素可以以任何順序求和。所以可以用以下的方法執行并行加法運算：

將輸入向量劃分到更小的數據塊中。

用一個線程計算一個數據塊的部分和。

對每個數據塊的部分和再求和得出最終結果。

并行加法的一個常用方法是使用迭代成對實現。一個數據塊只包含一對元素，并且一個線程對這兩個元素求和產生一個局部結果。然后，這些局部結果在最初的輸入向量中就地保存。這些新值被作為下一次迭代求和的輸入值。因為輸入值的數量在每一次迭代后會減半，當輸出向量的長度達到1時，最終的和就已經被計算出來了。

根據每次迭代后輸出元素就地存儲的位置，成對的并行求和實現可以被進一步分為以下兩種類型：

• 相鄰配對：元素與它們直接相鄰的元素配對
• 交錯配對：根據給定的跨度配對元素

圖3-19所示為相鄰配對的實現。在每一步實現中，一個線程對兩個相鄰元素進行操作，產生部分和。對于有N個元素的數組，這種實現方式需要N―1次求和，進行log2 N步。

圖3-20所示為交錯配對的實現。值得注意的是，在這種實現方法的每一步中，一個線程的輸入是輸入數組長度的一半。

下列的C語言函數是一個交錯配對方法的遞歸實現：

盡管以上代碼實現的是加法，但任何滿足交換律和結合律的運算都可以代替加法。例如，通過調用max代替求和運算，就可以計算輸入向量中的最大值。其他有效運算的例子有最小值、平均值和乘積。

在向量中執行滿足交換律和結合律的運算，被稱為歸約問題。并行歸約問題是這種運算的并行執行。并行歸約是一種最常見的并行模式，并且是許多并行算法中的一個關鍵運算。

在本節里，會實現多個不同的并行歸約核函數，并且將測試不同的實現是如何影響內核性能的。

3.4.2　并行歸約中的分化

圖3-21所示的是相鄰配對方法的內核實現流程。每個線程將相鄰的兩個元素相加產生部分和。

在這個內核里，有兩個全局內存數組：一個大數組用來存放整個數組，進行歸約；另一個小數組用來存放每個線程塊的部分和。每個線程塊在數組的一部分上獨立地執行操作。循環中迭代一次執行一個歸約步驟。歸約是在就地完成的，這意味著在每一步，全局內存里的值都被部分和替代。__syncthreads語句可以保證，線程塊中的任一線程在進入下一次迭代之前，在當前迭代里每個線程的所有部分和都被保存在了全局內存中。進入下一次迭代的所有線程都使用上一步產生的數值。在最后一個循環以后，整個線程塊的和被保存進全局內存中。

兩個相鄰元素間的距離被稱為跨度，初始化均為1。在每一次歸約循環結束后，這個間隔就被乘以2。在第一次循環結束后，idata（全局數據指針）的偶數元素將會被部分和替代。在第二次循環結束后，idata的每四個元素將會被新產生的部分和替代。因為線程塊間無法同步，所以每個線程塊產生的部分和被復制回了主機，并且在那兒進行串行求和，如圖3-22所示。

從Wrox.com上可以找到reduceInteger.cu完整的源代碼。代碼清單3-3只列出了主函數。

初始化輸入數組，使其包含16M元素：

然后，內核被配置為一維網格和一維塊：

用以下的命令編譯文件：

運行可執行文件，以下是運行結果。

在接下來的一節中，這些結果將會被作為性能調節的基準。

3.4.3　改善并行歸約的分化

注意內核中的下述語句，它為每個線程設置數組訪問索引：

因為跨度乘以了2，所以下面的語句使用線程塊的前半部分來執行求和操作：

對于一個有512個線程的塊來說，前8個線程束執行第一輪歸約，剩下8個線程束什么也不做。在第二輪里，前4個線程束執行歸約，剩下12個線程束什么也不做。因此，這樣就徹底不存在分化了。在最后五輪中，當每一輪的線程總數小于線程束的大小時，分化就會出現。在下一節將會介紹如何處理這一問題。

在主函數里調用基準內核之后，通過以下代碼段可以調用這個新內核。

用reduceNeighboredLess函數測試，較早的核函數將產生如下報告：

新的實現比原來的快了1.26倍。

可以通過測試不同的指標來解釋這兩個內核之間的不同行為。用inst_per_warp指標來查看每個線程束上執行指令數量的平均值。

結果總結如下，原來的內核在每個線程束里執行的指令數是新內核的兩倍多，它是原來實現高分化的一個指示器：

用gld_throughput指標來查看內存加載吞吐量：

結果總結如下，新的實現擁有更高的加載吞吐量，因為雖然I/O操作數量相同，但是其耗時更短：

3.4.4　交錯配對的歸約

與相鄰配對方法相比，交錯配對方法顛倒了元素的跨度。初始跨度是線程塊大小的一半，然后在每次迭代中減少一半（如圖3-24所示）。在每次循環中，每個線程對兩個被當前跨度隔開的元素進行求和，以產生一個部分和。與圖3-23相比，交錯歸約的工作線程沒有變化。但是，每個線程在全局內存中的加載/存儲位置是不同的。

交錯歸約的內核代碼如下所示：

注意核函數中的下述語句，兩個元素間的跨度被初始化為線程塊大小的一半，然后在每次循環中減少一半：

下面的語句在第一次迭代時強制線程塊中的前半部分線程執行求和操作，第二次迭代時是線程塊的前四分之一，以此類推：

下面的代碼增加到主函數中，執行交錯歸約的代碼：

用reduceInterleaved函數進行測試，較早的內核函數將產生如下報告：

交錯實現比第一個實現快了1.69倍，比第二個實現快了1.34倍。這種性能的提升主要是由reduceInterleaved函數里的全局內存加載/存儲模式導致的。在第4章里會介紹更多有關于全局內存加載/存儲模式對內核性能的影響。reduceInterleaved函數和reduceNeigh-boredLess函數維持相同的線程束分化。

總結

以上是生活随笔為你收集整理的《CUDA C编程权威指南》——3.4　避免分支分化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。