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

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

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

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

一，分支分歧對(duì)性能的影響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于SIMT棧的Reconvergence方案并不完美，其中一個(gè)很大的問題是Warp內(nèi)線程細(xì)粒度同步的時(shí)候很容易引發(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.”。

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

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

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

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

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

主要參考資料：

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