在先前文章中，我們談到現(xiàn)代GPU發(fā)展出SIMT（Single Instruction Multiple Thread）的執(zhí)行結(jié)構(gòu)，硬件線程池的線程們有相對獨立的運行上下文，以Warp為單位分發(fā)到一組處理單元按SIMD的模式運行。

這些Warp內(nèi)的線程共享同樣的PC，以鎖步的方式執(zhí)行指令，但是每個線程又可以有自己的執(zhí)行分支。很自然衍生的一個問題就是現(xiàn)代GPU如何有效的處理Branch Divergence（分支分歧）？

一方面為適應(yīng)復(fù)雜圖形渲染以及通用計算的要求，GPU編程語言像其它高級語言一樣需要支持各種各樣的流控制（Flow Control）指令，比如ifswitchdoforwhile等等，這些指令都會導(dǎo)致分支分歧。

另一方面GPU并行計算的特點要求所有處理單元整齊劃一地執(zhí)行相同指令，才能夠取得性能最大化。如何較好地解決這兩種不同要求導(dǎo)致的沖突，一直是GPU研究中的熱點難點問題。在這里筆者沒有能力深入探討，只是淺嘗輒止做一般介紹，主要求這個系列內(nèi)容完整，不足甚至謬誤之處，請各位看官不吝指正。

一，分支分歧對性能的影響

這一節(jié)我們首先來討論下分支分歧對GPU性能的影響。以如下ifelse代碼為例，我們看下GPU一般是如何來處理分支分歧的？

if （cond） {。。。} else {。。。}

假設(shè)一個Warp中有16個線程判斷條件為真，另外16個線程條件為假，所以一半線程會執(zhí)行if中的語句，另一半線程執(zhí)行else中的語句。這看起來像個悖論，我們知道Warp中的線程同一時刻只能執(zhí)行相同的指令。

實際上遇到分支分歧時GPU會順序執(zhí)行每個分支路徑，而禁用不在此路徑上的線程，直到所有有線程使能的分支路徑都走完，線程再重新匯合到同一執(zhí)行路徑。每個分支都有些線程不干活或者干無用功，Warp實際上需要執(zhí)行的指令數(shù)目大增。

假設(shè)每個分支任務(wù)量大致相同，分支分歧造成的性能損失少則原先的一半，最壞的情況如果每個線程執(zhí)行分支都不一致，性能下降為最高時候的1/32。

所以無論在設(shè)計算法還是分配處理數(shù)據(jù)的時候，我們都要小心盡量避免同一個Warp內(nèi)線程出現(xiàn)分支分歧的狀況，在遇到流控制指令的時候，最好能夠選擇同樣的路徑。

二，如何實現(xiàn)Reconvergence

上一節(jié)我們講了Warp的線程產(chǎn)生了分支分歧之后，為求性能最佳，不可能讓它們一直放任自流，最終還是要盡可能在合適時機把它們重新匯合（Reconverge）起來。但這一切是如何實現(xiàn)的呢？

按照參考1的說法，“The SM uses a branch synchronization stack to manage independent threads that diverge and converge” 。下面根據(jù)可接觸到的文獻(xiàn)我們看看大概是如何實現(xiàn)的，不一定跟GPU產(chǎn)商的實際做法一致。

我們稱這個Warp運行時棧為SIMT Stack，每個Warp擁有一個SIMT棧用于處理SIMT執(zhí)行模式中的分支分歧。

首先我們需要先確定分支分歧的最近重匯合點（Reconvergence Point），一般可以選用造成分支分歧節(jié)點的直接后序支配節(jié)點（Immediate post-dominator，若控制流圖的節(jié)點n 到終結(jié)節(jié)點的每一條路徑均要經(jīng)過節(jié)點d，則稱節(jié)點d后序支配節(jié)點n，如d與n之間沒有任何其他節(jié)點后序支配n，則稱節(jié)點d直接后序支配節(jié)點n）。

這可以通過編譯時的控制流分析得到。左邊是我們假想的一段GPU偽代碼，右邊是對應(yīng)的控制流圖，我們假設(shè)SIMD通道的數(shù)目是4，每個節(jié)點邊上的掩碼數(shù)字代表通道上線程在該節(jié)點基本塊有沒有使能。

SIMT棧結(jié)構(gòu)每個條目由執(zhí)行指令PC、分支重匯合PC（RPC）和使能線程掩碼三部分組成。執(zhí)行流從節(jié)點B分支分歧到節(jié)點E重新匯合時SIMT棧的更新過程。執(zhí)行的時候，遇到流控制指令，我們將各個分支依次入棧，棧頂條目的PC會被送到取指單元開始相應(yīng)分支路徑的處理。

只有條目掩碼中使能的線程會處于活躍狀態(tài)，當(dāng)下一條PC等于棧頂條目RPC的時候，說明該分支已經(jīng)到了匯合點，棧頂條目會被彈出，開始下一分支的處理以至所有執(zhí)行線程匯合并共同執(zhí)行接下來的指令。值得注意的是真實環(huán)境下GPU都設(shè)計有一些特殊指令來維護(hù)SIMT棧。

下圖表示上面代碼在時間軸上的執(zhí)行過程，實心箭頭表示對應(yīng)線程在該執(zhí)行節(jié)點處于活躍狀態(tài)，反之空心箭頭代表不活躍狀態(tài)。

基于SIMT棧的Reconvergence方案并不完美，其中一個很大的問題是Warp內(nèi)線程細(xì)粒度同步的時候很容易引發(fā)死鎖。按照Nvidia的說法，“algorithms requiring fine-grainedsharing of data guarded by locks or mutexes can easily lead to deadlock，depending on which warp the contending threads come from.”。

以下面代碼為例，某幸運線程拿到鎖之后，在最近重匯合點C等著與大部隊接頭，不幸的是它無法執(zhí)行下面的Exch指令以釋放鎖，導(dǎo)致其它線程只能在B處空轉(zhuǎn)，形成死鎖。

從更高的層次上理解，分支分歧導(dǎo)致的順序執(zhí)行只發(fā)生在Warp內(nèi)的線程，Warp之間卻相互不受干擾，這種不一致的處理方式對算法移植的適應(yīng)性還是可預(yù)測性都會帶來影響。Nvidia從Volta GPU開始做出了改進(jìn)。

提出了“Independent Thread Scheduling”的方法，使得所有線程無關(guān)所在Warp可以具有同樣并發(fā)執(zhí)行能力，為此相比之前的GPU其Warp內(nèi)所有線程共享PC以及運行棧，Volta GPU的線程都分別有各自的PC和運行棧，如下圖所示。

如此針對同樣的GPU程序以及分支分歧，Volta與之前的GPU相比有截然不同的調(diào)度行為。我們注意到在Volta中所有的Warp線程并沒有一起強制匯合執(zhí)行Z基本塊，主要考慮到Z可能作為生產(chǎn)者需要提供其它執(zhí)行分支依賴的的數(shù)據(jù)。

回到我們先前死鎖的例子，在Volta中這個死鎖便可迎刃而解。如果我們明顯了解相關(guān)分支不存在同步行為，為優(yōu)化性能計，CUDA提供了 __syncwarp（） 函數(shù)以便強制匯合。

主要參考資料：

NVIDIA Tesla： A Unified Graphics and Computing Architecture

Dynamic Warp Formation and Scheduling for Efficient GPU Control Flow

https://developer.nvidia.com/blog/inside-volta/

General-Purpose Graphics Processor Architectures

編輯：jq