近距離看GPU計算（3）
[導(dǎo)讀]在先前文章《近距離看GPU計算（2）》中，我們談到現(xiàn)代GPU發(fā)展出SIMT(SingleInstructionMultipleThread)的執(zhí)行結(jié)構(gòu)，硬件線程池的線程們有相對獨立的運行上下文，以Warp為單位分發(fā)到一組處理單元按SIMD的模式運行。這些Warp內(nèi)的線程共享同樣的...
在先前文章《近距離看GPU計算（2）》中，我們談到現(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)指令，比如if\switch\do\for\while等等，這些指令都會導(dǎo)致分支分歧。另一方面GPU并行計算的特點要求所有處理單元整齊劃一地執(zhí)行相同指令，才能夠取得性能最大化。如何較好地解決這兩種不同要求導(dǎo)致的沖突，一直是GPU研究中的熱點難點問題。在這里筆者沒有能力深入探討，只是淺嘗輒止做一般介紹，主要求這個系列內(nèi)容完整，不足甚至謬誤之處，請各位看官不吝指正。一，分支分歧對性能的影響這一節(jié)我們首先來討論下分支分歧對GPU性能的影響。以如下if\else代碼為例，我們看下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)的，不一定跟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)，當下一條PC等于棧頂條目RPC的時候，說明該分支已經(jīng)到了匯合點，棧頂條目會被彈出，開始下一分支的處理以至所有執(zhí)行線程匯合并共同執(zhí)行接下來的指令。值得注意的是真實環(huán)境下GPU都設(shè)計有一些特殊指令來維護SIMT棧。下圖表示上面代碼在時間軸上的執(zhí)行過程，實心箭頭表示對應(yīng)線程在該執(zhí)行節(jié)點處于活躍狀態(tài)，反之空心箭頭代表不活躍狀態(tài)。
基于SIMT棧的Reconvergence方案并不完美，其中一個很大的問題是Warp內(nèi)線程細粒度同步的時候很容易引發(fā)死鎖。按照Nvidia的說法，"algorithms requiring fine-grained sharing 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開始做出了改進，提出了"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提供了?
主要參考資料:
上一節(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)的，不一定跟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棧的Reconvergence方案并不完美，其中一個很大的問題是Warp內(nèi)線程細粒度同步的時候很容易引發(fā)死鎖。按照Nvidia的說法，"algorithms requiring fine-grained sharing 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開始做出了改進，提出了"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
下載文檔
