本節書摘來自華章社群《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函數維持相同的線程束分化。