劉素芹，王 鑫，安仲奇，楊娜利，王俊爽

(中國(guó)石油大學(xué)計(jì)算機(jī)與通信工程學(xué)院，山東青島 266580)

近年來(lái)由GPU作為加速部件的異構(gòu)計(jì)算系統(tǒng)和技術(shù)，如CUDA［1］產(chǎn)生并得到發(fā)展。GPU擅長(zhǎng)的SIMD(single instruction multiple data)執(zhí)行方式提高了系統(tǒng)的計(jì)算效率，但當(dāng)程序出現(xiàn)條件分支分歧時(shí)，會(huì)部分或完全退化成串行執(zhí)行，性能損失嚴(yán)重。條件分支是控制程序執(zhí)行流的基本方式，易大量出現(xiàn)，并且算法越復(fù)雜，對(duì)分支的利用就會(huì)越頻繁。因此，需要優(yōu)化GPU對(duì)條件分支的處理以更充分地發(fā)揮其并行計(jì)算的潛力。目前的研究主要集中在硬件層面設(shè)計(jì)線程調(diào)度器方面［2-5］，對(duì)普通用戶而言實(shí)現(xiàn)難度較大，而利用現(xiàn)有體系結(jié)構(gòu)從軟件層面優(yōu)化條件分支處理流程方面的研究還較少，因此筆者探索實(shí)現(xiàn)難度較低、可操作性較強(qiáng)的優(yōu)化方法。

1 GPU條件分支處理機(jī)制分析

1.1 基于CUDA的GPU處理?xiàng)l件分支的機(jī)制

基于CUDA的GPU執(zhí)行沒有分支的語(yǔ)句時(shí)，線程束(warp［6］)中的線程按照SIMD的方式步調(diào)一致地執(zhí)行，而遇到條件分支分歧時(shí)，處理過程則有所不同。對(duì)于較簡(jiǎn)單的IF-ELSE語(yǔ)句，PTX［7］匯編器將PTX語(yǔ)句只編譯為GPU斷言指令。此時(shí)GPU的斷言設(shè)置指令處理IF語(yǔ)句的條件部分，并根據(jù)判斷結(jié)果設(shè)置斷言寄存器的各位，從而啟用或禁用對(duì)應(yīng)的SIMD道。當(dāng)執(zhí)行IF內(nèi)部的語(yǔ)句時(shí)，操作被廣播至所有SIMD道，但只有斷言寄存器設(shè)為啟用的道執(zhí)行操作并流出結(jié)果，設(shè)為禁用的道并不執(zhí)行操作也不保存結(jié)果。ELSE部分處理方式與之類似。分支語(yǔ)句執(zhí)行結(jié)束后，SIMD道不再受斷言影響，繼續(xù)一致地執(zhí)行后續(xù)指令。當(dāng)SIMD線程中的所有道都選擇了相同的路徑時(shí)，不被執(zhí)行的另一路徑的指令將被直接跳過。

對(duì)于復(fù)雜控制流如嵌套條件語(yǔ)句，則需要混合使用斷言指令、GPU分支指令和同步指令。此時(shí)，當(dāng)分支分歧時(shí)，棧條目被壓入分支同步棧，SIMD道轉(zhuǎn)到目標(biāo)指令執(zhí)行。當(dāng)分支收斂時(shí)，棧條目彈出，SIMD道轉(zhuǎn)回棧條目地址且斷言寄存器還原為上一層嵌套的掩碼。

1.2 條件分支對(duì)計(jì)算性能的影響

SIMD執(zhí)行方式處理?xiàng)l件分支時(shí)性能損失往往是顯著的。如果條件分支嵌套較深，可能導(dǎo)致多數(shù)SIMD道空閑，比如假設(shè)每條分支路徑的長(zhǎng)度相同，兩層嵌套將使效率降低至25%，三層嵌套進(jìn)一步降低至12.5%。在最壞情況下，所有SIMD元素將串行執(zhí)行，以 Fermi［8］架構(gòu)為例，每?jī)蓚€(gè)時(shí)鐘周期(SIMD線程寬度為32，執(zhí)行單元寬度為16)只能有一條SIMD道流出有效結(jié)果，其他道都被阻塞［9］。下列IF語(yǔ)句和IF-ELSE語(yǔ)句是造成SIMD執(zhí)行性能損失的兩種基本條件分支語(yǔ)句結(jié)構(gòu)。

(a)IF語(yǔ)句:

(a)只有一條分支路徑，如果某一SIMD線程中的任意SIMD道需要執(zhí)行IF內(nèi)部的語(yǔ)句，則同一SIMD線程中所有的SIMD道都會(huì)經(jīng)過這個(gè)分支路徑，只是斷言寄存器設(shè)為禁用的道不執(zhí)行實(shí)際操作，因此部分計(jì)算資源閑置，性能有顯著損失。(b)相當(dāng)于兩個(gè)(a)情況的疊加，同一SIMD線程中只有當(dāng)所有SIMD道都選擇相同的路徑時(shí)才會(huì)少走一路分支路徑，其他情況下所有SIMD道都會(huì)經(jīng)過兩個(gè)分支路徑，程序性能損失為(a)的兩倍。

1.3 GPU條件分支優(yōu)化的研究現(xiàn)狀

條件分支分歧對(duì)計(jì)算性能的影響主要是由GPU底層的處理方式造成的，因此現(xiàn)有優(yōu)化方法多傾向于設(shè)計(jì)某種新硬件機(jī)制來(lái)重新調(diào)度SIMD道，避免在SIMD線程內(nèi)發(fā)生分支分歧，使其在每步計(jì)算中更充分地利用計(jì)算資源。DWF(dynamic warp formation)［10］和 DWS(dynamic warp subdivision)［11］即為兩種硬件機(jī)制:DWF的硬件調(diào)度器在每個(gè)時(shí)鐘周期分析SIMD線程，將執(zhí)行相同分支路徑的SIMD道整合生成新的SIMD線程;DWS則是將SIMD線程分解為子線程，子線程被獨(dú)立調(diào)度并交替執(zhí)行。Zhang等［12］提出了一種在運(yùn)行時(shí)重新映射SIMD線程數(shù)據(jù)的方法，由于需要昂貴的CPU-GPU數(shù)據(jù)通信，整體優(yōu)化效果有限。

以上優(yōu)化方案都是硬件層面的優(yōu)化，雖然較為有效，但對(duì)于一般的GPU計(jì)算用戶實(shí)現(xiàn)難度較大。因此，有必要探討實(shí)現(xiàn)難度更低，可操作性更強(qiáng)的優(yōu)化方法。本文中針對(duì)這一問題利用現(xiàn)有體系結(jié)構(gòu)在軟件層面進(jìn)行優(yōu)化，以期能在一定程度上優(yōu)化條件分支分歧。

2 聚合優(yōu)化策略的設(shè)計(jì)方案

從軟件層級(jí)入手，探索提升每步SIMD執(zhí)行的有效處理比重的方法，提出了利用“聚合”思想的SIMD分支優(yōu)化策略，該策略針對(duì)的具體情形如下列代碼所示。

由于分支條件不能在編譯時(shí)確定，所以只有程序運(yùn)行時(shí)才能決定線程的走向。此種情形由于GPU的執(zhí)行方式使得執(zhí)行某條路徑時(shí)只有選擇該路徑的SIMD道進(jìn)行實(shí)際計(jì)算，其他道被阻塞，而分支處于循環(huán)體內(nèi)部導(dǎo)致任意時(shí)刻都有大量資源閑置。

鑒于此，聚合策略的主體思想是:在每步循環(huán)中，采用某種機(jī)制將不同SIMD道中選擇相同路徑的條件分支“聚合”到同一步循環(huán)中，力求提高每次循環(huán)的有效處理比重。為此，在具體實(shí)施過程中可以用不同的實(shí)現(xiàn)策略，本文著重對(duì)循環(huán)推遲和循環(huán)提前兩種實(shí)現(xiàn)策略進(jìn)行討論。

2.1 基于循環(huán)推遲的聚合優(yōu)化策略

循環(huán)推遲的做法是在每一步循環(huán)中，SIMD線程中的所有SIMD道只執(zhí)行一條分支路徑，另一條分支路徑則被“掛起”，并被推遲到后續(xù)的循環(huán)中，與下一步循環(huán)合并后再擇機(jī)執(zhí)行。此前未執(zhí)行的SIMD道與即將執(zhí)行的SIMD道就“聚合”到了同一步SIMD執(zhí)行中。這樣做使得每次循環(huán)只執(zhí)行了一條路徑，另一條路徑直接跳過，因此所用時(shí)間是串行執(zhí)行兩條分支路徑的一半，從而使SIMD執(zhí)行的總數(shù)少于未優(yōu)化之前。

圖1給出了一個(gè)SIMD線程常規(guī)分支執(zhí)行與采用循環(huán)推遲策略后分支執(zhí)行的兩種不同情況的對(duì)比示例。其中假設(shè)SIMD線程寬度為4，循環(huán)次數(shù)為3，帶下標(biāo)的T和F分別代表?xiàng)l件判斷為真(True)和為假(False)的不同路徑，下標(biāo)的左起第一位數(shù)代表的是在未優(yōu)化的情況下第幾次循環(huán)的編號(hào)，第二位數(shù)代表的是SIMD道的編號(hào)。

圖1 使用基于循環(huán)推遲的聚合優(yōu)化策略的示例Fig.1 A branch execution example using converging optimization strategy based on loop postpone

常規(guī)執(zhí)行時(shí)，如圖1(a)，每次循環(huán)內(nèi)要依次將所有分支路徑都執(zhí)行一次，從本例來(lái)說，共有6步SIMD執(zhí)行(每個(gè)循環(huán)包含兩次SIMD執(zhí)行)。采用了循環(huán)推遲的策略后，如(b)和(c)所示，雖然循環(huán)次數(shù)都有所增加，但是整體的SIMD執(zhí)行步數(shù)卻都有所減少(空路徑被直接跳過，執(zhí)行時(shí)間忽略不計(jì))，最多也與未優(yōu)化時(shí)相等。假設(shè)兩條分支路徑中的指令數(shù)目相同，則聚合后(b)情況執(zhí)行的指令數(shù)降低了16.7%，(c)情況則降低了33.3%。

從上圖的例子中不難看出，當(dāng)遇到分支分歧時(shí)“掛起”的分支路徑選擇的不同，會(huì)導(dǎo)致最終的聚合效果不同，因此循環(huán)推遲策略的關(guān)鍵是在每次循環(huán)中如何選擇要執(zhí)行的路徑。此處采用了兩種較為簡(jiǎn)單的路徑選擇策略:多數(shù)優(yōu)先策略和輪轉(zhuǎn)策略。

多數(shù)優(yōu)先策略是在每次分支分歧時(shí)選擇包含最多SIMD道的分支路徑執(zhí)行，即選擇執(zhí)行計(jì)算單元使用率最高的路徑。由于本文討論的條件分支有兩條路徑，所以這樣使得多數(shù)循環(huán)中SIMD執(zhí)行的有效道數(shù)必然大于等于SIMD總道數(shù)的一半，如圖1(b)中第0～3次循環(huán)，從而提高SIMD計(jì)算單元的使用率，減少SIMD執(zhí)行的總次數(shù)，達(dá)到縮短計(jì)算時(shí)間的目的，并且整個(gè)執(zhí)行過程不會(huì)破壞每個(gè)SIMD道原有的循環(huán)執(zhí)行順序。但本策略可能導(dǎo)致處于冷門路徑的SIMD道遲遲得不到執(zhí)行，如圖1(b)中第2號(hào)道的第4次循環(huán)，本文中稱這種現(xiàn)象為道饑餓。道饑餓現(xiàn)象的存在可能會(huì)造成最后幾步循環(huán)中只有少數(shù)SIMD道執(zhí)行實(shí)際操作，一定程度上限制了循環(huán)推遲的聚合效果，實(shí)際實(shí)現(xiàn)中可以采用周期性暫停本聚合策略來(lái)觸發(fā)冷門路徑的執(zhí)行以緩解道饑餓現(xiàn)象。

輪轉(zhuǎn)策略是在每次循環(huán)中遇到分支分歧時(shí)，交替的選擇條件判斷為真或?yàn)榧俚穆窂綀?zhí)行，并將另一條路徑掛起和推遲到下一步循環(huán)中，從而達(dá)到聚合的效果，提高計(jì)算效率，如圖1(c)所示(采用先假后真交替循環(huán))。這樣雖然在最初幾次循環(huán)中聚合效果不如多數(shù)優(yōu)先策略，但是每次循環(huán)中有效執(zhí)行的SIMD道數(shù)卻較為均等，且多數(shù)情況下超過SIMD總道數(shù)的一半，同時(shí)還避免了道饑餓現(xiàn)象。不足之處是如果SIMD線程的所有SIMD道在某次循環(huán)中都選擇相同路徑，而此時(shí)根據(jù)輪轉(zhuǎn)策略恰好輪轉(zhuǎn)到了另一條路徑(此處稱這種現(xiàn)象為“空載”)，會(huì)導(dǎo)致無(wú)用執(zhí)行，實(shí)際實(shí)現(xiàn)中遇到上述情況要切換分支走向。

這兩種策略實(shí)現(xiàn)起來(lái)都非常方便，可以利用CUDA本身提供的統(tǒng)計(jì)各SIMD道狀態(tài)的函數(shù)來(lái)實(shí)現(xiàn)，并且所引入的開銷也可忽略不計(jì)。

影響循環(huán)推遲優(yōu)化效果的因素有以下4點(diǎn):

(1)如果分支指令規(guī)模小于實(shí)現(xiàn)循環(huán)推遲的指令規(guī)模，那么其帶來(lái)的收益可能不足以抵消本身的開銷，甚至?xí)?dǎo)致性能損失。

(2)暫時(shí)阻塞分支同樣會(huì)阻塞相關(guān)SIMD元素對(duì)循環(huán)體中后續(xù)非分支代碼的執(zhí)行，如若分支指令數(shù)量相比后續(xù)非分支指令較少，循環(huán)推遲可能無(wú)法帶來(lái)理想的改進(jìn)。

(3)分支被執(zhí)行的頻率、SIMD元素分支變向的頻率等因素會(huì)影響循環(huán)推遲的效果。本文所采用的多數(shù)優(yōu)先策略和輪轉(zhuǎn)策略相對(duì)簡(jiǎn)單，其改進(jìn)效果依賴具體的分支模式。

(4)循環(huán)推遲可能破壞原有的優(yōu)化的內(nèi)存訪問模式，導(dǎo)致性能的下降。

2.2 基于循環(huán)提前的聚合優(yōu)化策略

循環(huán)提前的做法是將原本由兩次循環(huán)完成的任務(wù)“聚合”到一次循環(huán)中完成。這種策略適用于同一SIMD道執(zhí)行流中第N次循環(huán)與第N+1次循環(huán)所選擇的分支路徑不同的情況，假設(shè)程序只有兩個(gè)不同的分支路徑T路徑和F路徑，如圖2(a)和圖2(c)所示，當(dāng)遇到這兩種情形時(shí)，可以考慮將第N+1次循環(huán)提前到第N次循環(huán)中執(zhí)行，如圖2(b)和圖2(d)所示，從而充分利用每一次循環(huán)。

圖2 基于循環(huán)提前的聚合優(yōu)化策略的適用情況Fig.2 Circumstances converging optimization strategy based on loop advance targets

循環(huán)提前策略的效果依賴于原有程序路徑選擇的情況，圖3給出了兩個(gè)使用基于循環(huán)提前的聚合優(yōu)化的兩個(gè)示例，每個(gè)示例中SIMD線程寬度為4，循環(huán)次數(shù)為4。

示例1在使用了本策略后聚合效果達(dá)到了理想狀態(tài)，如果兩條分支路徑中的指令數(shù)大致相當(dāng)，則優(yōu)化后的指令數(shù)降為原來(lái)的50%。示例2在使用了本策略后聚合效果較為一般，并非所有的相鄰的循環(huán)都能使用循環(huán)提前策略，但總體性能仍然有一定提升，優(yōu)化后的指令數(shù)降為原來(lái)的75%。最壞情況下SIMD線程中的某些道在整個(gè)循環(huán)過程中都只選擇走同一條分支路徑，本策略則在這些道上不起作用，程序受這些道拖累性能沒有任何提升，還有可能下降。

圖3 使用基于循環(huán)提前的聚合優(yōu)化策略的兩個(gè)示例Fig.3 Two branch execution examples using converging optimization strategy based on loop advance

策略的實(shí)現(xiàn)可以通過改造原有條件分支的執(zhí)行模式，判斷相鄰兩次循環(huán)中條件分支的路徑走向，然后調(diào)整分支的執(zhí)行來(lái)實(shí)現(xiàn)，引入的開銷也不大。由于循環(huán)提前可能會(huì)調(diào)換相鄰兩步循環(huán)的次序，因此需要滿足如下條件才能保證執(zhí)行結(jié)果的正確:

(1)每步循環(huán)中各分支語(yǔ)句不依賴上一步循環(huán)的結(jié)果，即循環(huán)的先后次序可交換。

(2)條件分支語(yǔ)句內(nèi)的兩個(gè)不同分支之間不能出現(xiàn)相互依賴。

(3)循環(huán)中條件分支以后不能直接出現(xiàn)非分支代碼。

條件(3)的原因主要是，循環(huán)提前策略合并了相鄰的兩步循環(huán)，從而減少了循環(huán)的次數(shù)，導(dǎo)致分支代碼之后的非分支代碼執(zhí)行的次數(shù)也相應(yīng)減少，無(wú)法與之前未優(yōu)化的程序保持一致。如一定要有非分支代碼，則可以將非分支代碼整體拷貝或封裝成函數(shù)后分別移入到條件分支的不同路徑中。影響循環(huán)提前優(yōu)化效果的因素有循環(huán)推遲中的(1)、(3)、(4)條。此外，從圖3的分析也可看出，實(shí)際優(yōu)化效果依賴于程序中的分支出現(xiàn)圖2中兩種情況的比例。

3 聚合優(yōu)化策略的實(shí)現(xiàn)

從策略的設(shè)計(jì)來(lái)看，要實(shí)現(xiàn)聚合優(yōu)化策略勢(shì)必會(huì)引入新的條件分支判斷，這雖然會(huì)在局部影響到程序運(yùn)行的效率，但其影響十分有限。因?yàn)檫@些額外的條件分支當(dāng)中只包含很少的代碼，且多為復(fù)制和比較等簡(jiǎn)單運(yùn)算，計(jì)算時(shí)間十分短暫。本文將其歸結(jié)為“實(shí)現(xiàn)優(yōu)化策略所需的指令規(guī)?！?。只有當(dāng)原有的分支指令規(guī)模接近或小于“實(shí)現(xiàn)優(yōu)化策略所需的指令規(guī)模”時(shí)才可能導(dǎo)致性能的損失。在需要采用聚合優(yōu)化策略的情況下，主要分支路徑中的指令規(guī)模要遠(yuǎn)大于“實(shí)現(xiàn)優(yōu)化策略所需的指令規(guī)?！?，所以優(yōu)化主要分支所帶來(lái)的程序效率的提升要大于策略的開銷。

3.1 基于循環(huán)推遲的聚合優(yōu)化策略的實(shí)現(xiàn)

實(shí)現(xiàn)基于循環(huán)推遲的聚合策略的關(guān)鍵是實(shí)現(xiàn)兩種選擇路徑的策略，然后根據(jù)路徑選擇策略的結(jié)果掛起或執(zhí)行某些線程，其主體的示意性代碼如下:

多數(shù)優(yōu)先策略的實(shí)現(xiàn)可以使用線程束投票函數(shù)__ballot()和整數(shù)處理函數(shù)__popc()。__ballot()函數(shù)可以檢查線程束中所有線程的斷言狀態(tài)并搜集至一個(gè)32位整數(shù)中，如果第n個(gè)線程的斷言值與參數(shù)值相同，那么返回的整數(shù)的第n位為1。__popc()能夠返回32位整數(shù)中位1的數(shù)目。使用這兩個(gè)函數(shù)可以找出被多數(shù)SIMD線程執(zhí)行的分支路徑，進(jìn)而實(shí)施多數(shù)優(yōu)先策略。

輪轉(zhuǎn)策略的實(shí)現(xiàn)方法比較直接，只需在循環(huán)中周期性地調(diào)轉(zhuǎn)分支走向即可。為避免“空載”分支路徑被執(zhí)行的情況，可以利用線程束投票函數(shù)__all()和__any()來(lái)進(jìn)行判斷。如果所有SIMD線程的斷言狀態(tài)與參數(shù)相符，那么__all()返回非零值。如果SIMD線程中存在斷言狀態(tài)與參數(shù)相符的元素，那么__any()將返回非零值。利用這兩個(gè)函數(shù)可以在循環(huán)出現(xiàn)“空載”路徑時(shí)切換分支走向。

3.2 基于循環(huán)提前的聚合優(yōu)化策略的實(shí)現(xiàn)

由于循環(huán)提前策略需要考慮相鄰兩步循環(huán)所選的分支路徑才能決定循環(huán)是否需要提前，因此在循環(huán)體中分支語(yǔ)句之前需要計(jì)算出相鄰兩步循環(huán)中的分支條件。然后據(jù)此判明是圖2中的哪種具體情況，再對(duì)不同的情況分別采用不同的提前模式，處理過程的示意性代碼如下:

代碼中將每次循環(huán)中條件分支中所要用到的不同的變量統(tǒng)稱為環(huán)境變量，可以是從某處讀取的數(shù)據(jù)，也可以是通過對(duì)循環(huán)變量i進(jìn)行計(jì)算得到的數(shù)值等各種各樣的數(shù)據(jù)，但不能是循環(huán)之間相互依賴的數(shù)據(jù)。mode用于控制優(yōu)化策略模式，其取值為0、1、2。0代表無(wú)法對(duì)循環(huán)進(jìn)行提前，循環(huán)按原有順序執(zhí)行。1代表圖2(b)中先F路徑后T路徑的模式，此時(shí)需要將第N+1次循環(huán)中的T路徑提前到本次進(jìn)行，因此需要將循環(huán)變量以及各環(huán)境變量調(diào)整到第N+1次循環(huán)時(shí)的狀態(tài)，之后再執(zhí)行第N次循環(huán)中的F路徑，此時(shí)又需要將循環(huán)變量和各環(huán)境變量重新調(diào)整回來(lái)，當(dāng)兩個(gè)路徑都執(zhí)行完畢之后再把循環(huán)變量遞增1。2代表圖2(a)中先T路徑后F路徑的模式，同樣也需要類似的在兩次循環(huán)的不同循環(huán)變量和環(huán)境變量之間進(jìn)行切換。

4 試驗(yàn)結(jié)果及分析

試驗(yàn)采用的GPU加速設(shè)備是GeForce GT 550M(GF108)，擁有兩顆SIMD核心，每個(gè)核心有48道，單精度峰值計(jì)算性能為284.16GFlops。軟件環(huán)境是CUDA toolkit 5.0。

4.1 基于循環(huán)推遲的聚合優(yōu)化策略試驗(yàn)

將32個(gè)SIMD線程(共32×48個(gè)CUDA線程)加載至同一SIMD核，以保證算術(shù)流水線滿載，避免指令級(jí)并行變化對(duì)性能的影響。每個(gè)SIMD線程中，各道的分支走向相互獨(dú)立，由 CURAND［13］庫(kù)通過偽隨機(jī)算法生成。每條分支路徑內(nèi)部包含一系列數(shù)據(jù)依賴的混合乘加(fused-multiply-add，F(xiàn)MA)運(yùn)算，并可通過改變混合乘加運(yùn)算的多少來(lái)調(diào)節(jié)分支指令－非分支指令比(核函數(shù)中，分支路徑內(nèi)指令數(shù)/分支路徑外指令數(shù))。試驗(yàn)對(duì)不同的分支指令－非分支指令比分別使用多數(shù)優(yōu)先和輪轉(zhuǎn)兩種選路策略進(jìn)行優(yōu)化，并與未經(jīng)優(yōu)化的分支執(zhí)行進(jìn)行比較，得出加速比(優(yōu)化前執(zhí)行時(shí)間/優(yōu)化后執(zhí)行時(shí)間)，試驗(yàn)數(shù)據(jù)結(jié)果如圖4所示。

從圖4中可以看出，當(dāng)分支指令－非分支指令比較小時(shí)，由于聚合本身所帶來(lái)的開銷，加速比低于1，隨著分支指令規(guī)模的提升，加速比逐步提升。多數(shù)優(yōu)先策略測(cè)試取得的最佳加速比為1.152，輪轉(zhuǎn)策略測(cè)試取得的最佳加速比為1.256。由于多數(shù)優(yōu)先策略需要定期處理道饑餓現(xiàn)象，所以在多數(shù)情況下加速比低于輪轉(zhuǎn)策略。

圖4 基于循環(huán)推遲的聚合優(yōu)化對(duì)性能的影響Fig.4 Performance impact of converging optimization strategy based on loop postpone

4.2 基于循環(huán)提前的聚合優(yōu)化策略試驗(yàn)

加載的SIMD線程配置和分支路徑內(nèi)的運(yùn)算與基于循環(huán)推遲的聚合優(yōu)化策略相同，且同時(shí)滿足基于循環(huán)提前的聚合優(yōu)化策略的3個(gè)前提條件，針對(duì)條件(3)需要將循環(huán)內(nèi)部原本位于條件分支語(yǔ)句后的非分支代碼封裝成函數(shù)移入條件分支內(nèi)部。此處將這些函數(shù)稱為非分支代碼函數(shù)，并仍將其視作非分支代碼。

循環(huán)提前的效果除了依賴于分支指令－非分支指令比，還依賴于循環(huán)中出現(xiàn)圖2中兩種情況的比例。此處將能夠提前的循環(huán)數(shù)與循環(huán)總數(shù)的比值稱為可提前比。由于同一SIMD道中每?jī)蓚€(gè)相鄰循環(huán)都選擇不同路徑時(shí)也只有50%的循環(huán)可以提前，因此可提前比最大是0.5，最小是0，并且加速效果取決于可提前比最低的SIMD道。理想情況下，若只考慮分支代碼，則可提前比與加速比的關(guān)系為

為更直觀反應(yīng)本策略的有效性，在這里用線程號(hào)threadIdx和循環(huán)變量i使所有SIMD道中的可提前比一致，試驗(yàn)時(shí)取了間隔相等的6個(gè)值。同時(shí)為了代表一般性，利用CURAND偽隨機(jī)算法生成分支走向，試驗(yàn)數(shù)據(jù)結(jié)果如圖5所示。

需要說明的是，圖中每條曲線的前兩個(gè)點(diǎn)的分支指令－非分支指令比是0.25和0.5，第三個(gè)點(diǎn)是1，以后每次遞增1。在不同的可提前比情況下，隨著分支代碼－非分支代碼比的增加，程序的加速比都在逐步提升并趨近于只有分支代碼時(shí)的理想情況。當(dāng)程序中可提前比過低且分支指令少于非分支指令時(shí)，本策略產(chǎn)生的額外開銷將導(dǎo)致程序的加速比低于1。

圖5 基于循環(huán)提前的聚合優(yōu)化對(duì)性能的影響Fig.5 Performance impact of converging optimization strategy based on loop advance

5 結(jié)束語(yǔ)

在軟件層級(jí)提出兩種利用“聚合”思想的SIMD分支優(yōu)化策略，將不同SIMD道中選擇相同路徑的條件分支“聚合”到了同一步循環(huán)中。壓縮了GPU執(zhí)行SIMD操作的實(shí)際次數(shù)，提高了GPU硬件在每次SIMD操作時(shí)的利用率。試驗(yàn)表明，在滿足一定條件下能夠取得較為理想的加速比，與現(xiàn)有的硬件層面的優(yōu)化方案相比實(shí)現(xiàn)難度較低。本策略對(duì)分支結(jié)構(gòu)有所要求，因此在一般性方面還存在不足。另外還可能存在一些影響優(yōu)化效果的其他因素需進(jìn)一步改進(jìn)。

［1］ NVIDIA.CUDA［EB/OL］.［2013-05-12］.https://developer.nvidia.com/cuda-downloads.

［2］ NARASIMAN V，SHEBANOW M，LEE C J，et al.Improving GPU performance via large warps and two-level warp scheduling［C］//Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture.New York:ACM，c2011.

［3］ DIAMOS G，ASHBAOGH B，MAIYURAN S，et al.SIMD re-convergence at thread frontiers［C］//Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture.New York:ACM，c2011.

［4］ BRUNIE N，COLLANGE S，DIAMOS G.Simultaneous branch and warp interweaving for sustained GPU performance［C］//Proceedings of the 39th International Symposium on Computer Architecture.Washington:IEEE Computer Society，c2012.

［5］ FUNG W L，AAMODT T M.Thread block compaction for efficient SIMT control flow［C］Proceedings of the 17th International Symposium on High Performance Computer Architecture(HPCA).Washington:IEEE Computer Society，c2011.

［6］ NVIDIA.CUDA C Programming Guide 5.0［EB/OL］.［2013-05-12］.http://docs.nvidia.com/cuda/cuda-cprogramming-guide/index.html.

［7］ NVIDIA.NVIDIA Compute:Parallel Thread Execution ISA Version 3.0［EB/OL］.［2013-05-12］.http://docs.nvidia.com/cuda/parallel-thread-execution/index.html.

［8］ GLASKOWSKY P N.NVIDIA1s Fermi:the first complete GPU computing architecture［EB/OL］.［2013-05-12］.http://www.nvidia.com/object/fermi_architecture.html.

［9］ CUI Z，LIANG Y，RUPNOW K，et al.An accurate GPU performance model for effective control flow divergence optimization［C］//Proceedings of the 26th International Symposium on Parallel＆ Distributed Processing.Washington:IEEE Computer Society，c2012.

［10］ MENG J，TARJAN D，SKADRON K.Dynamic warp subdivision for integrated branch and memory divergence tolerance［C］//Proceedings of the 37th annual international symposium on Computer Architecture.New York:ACM，c2010.

［11］ FUNG W W L，SHAM I，YUAN G，et al.Dynamic warp formation and scheduling for efficient gpu control flow［C］//Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture.Washington:IEEE Computer Society，c2007.

［12］ ZHANG E Z，JIANG Y，GUO Z，et al.Streamlining GPU applications on the fly:thread divergence elimination through runtime thread-data remapping［C］//Proceedings of the 24th ACM International Conference on Supercomputing.New York:ACM，c2010.

［13］ NVIDIA.CUDA toolkit 5.0 CURAND guide［EB/OL］.［2013-05-12］.http://docs.nvidia.com/cuda/curand/index.html