張　軍　何炎祥　沈凡凡　江　南,4　李清安

1(武漢大學(xué)計算機學(xué)院　武漢　430072)2(軟件工程國家重點實驗室(武漢大學(xué))　武漢　430072)3(東華理工大學(xué)軟件學(xué)院　南昌　330013)4　　　(湖北工業(yè)大學(xué)計算機學(xué)院　武漢　430068) (zhangjun_whu@whu.edu.cn)

?

基于2階段同步的GPGPU線程塊壓縮調(diào)度方法

張軍1,3何炎祥1,2沈凡凡1江南1,4李清安1,2

1(武漢大學(xué)計算機學(xué)院武漢430072)2(軟件工程國家重點實驗室(武漢大學(xué))武漢430072)3(東華理工大學(xué)軟件學(xué)院南昌330013)4(湖北工業(yè)大學(xué)計算機學(xué)院武漢430068) (zhangjun_whu@whu.edu.cn)

摘要通用圖形處理器(general purpose graphics processing unit, GPGPU)在面向高性能計算、高吞吐量的通用計算領(lǐng)域的應(yīng)用日益廣泛，它采用的SIMD(single instruction multiple data)執(zhí)行模式使其能獲得強大的并行計算能力.目前主流的通用圖形處理器均通過大量高度并行的線程完成計算任務(wù)的高效執(zhí)行.但是在處理條件分支轉(zhuǎn)移的控制流中，由于通用圖形處理器采用串行的方式順序處理不同的分支路徑，使得其并行計算能力受到影響.在分析討論前人針對分支轉(zhuǎn)移處理低效的線程塊壓縮重組調(diào)度方法的基礎(chǔ)上，提出了2階段同步的線程塊壓縮重組調(diào)度方法TSTBC(two-stage synchronization based thread block compaction scheduling)，通過線程塊壓縮重組適合性判斷邏輯部件，分2個階段對線程塊進行壓縮重組有效性分析，進一步減少了無效的線程塊壓縮重組次數(shù).模擬實驗結(jié)果表明：該方法較好地提高了線程塊的壓縮重組有效性，相對于其他同類方法降低了對線程組內(nèi)部數(shù)據(jù)局部性的破壞，并使得片上一級數(shù)據(jù)cache的訪問失效率得到有效降低；相對于基準(zhǔn)體系結(jié)構(gòu)，系統(tǒng)性能提升了19.27%.

關(guān)鍵詞通用圖形處理器；線程調(diào)度；線程塊壓縮重組；2階段同步；分支轉(zhuǎn)移

近年來，通用圖形處理器(general purpose gra-phics processing unit, GPGPU)以其強大的并行計算能力在高性能計算領(lǐng)域得到了廣泛的應(yīng)用，并隨著其處理不規(guī)則應(yīng)用程序能力的日益提升，GPGPU在通用計算領(lǐng)域的應(yīng)用也越來越廣泛.GPGPU通過采用單指令多數(shù)據(jù)(single instruction multiple data, SIMD)執(zhí)行模式獲得強大的并行處理能力和高計算吞吐量[1].SIMD執(zhí)行模式將單條程序指令映射到多個數(shù)據(jù)通道上同時執(zhí)行.NVIDIA將這種執(zhí)行模式又稱為單指令多線程(single instruction multiple thread, SIMT)執(zhí)行模式[1-2]，并將映射到不同數(shù)據(jù)通道的指令流看作邏輯線程.SIMT執(zhí)行模式對線程實行分組管理，每個分組包含多個線程，其大小(稱為線程組寬度)一般為32(NVIDIA系列顯卡)或64(AMD系列顯卡)，這些寬度的分組分別被稱為warp[3-4]和wavefront[5].多個相互協(xié)作的線程分組又構(gòu)成了線程塊(thread block, TB).

SIMT執(zhí)行模式將計算任務(wù)映射到不同的數(shù)據(jù)通道同時執(zhí)行，以獲得高的線程級并行度(thread level parallelism, TLP).但是當(dāng)遇到不規(guī)則計算任務(wù)時，例如分支轉(zhuǎn)移(branch divergence)指令，其執(zhí)行任務(wù)的TLP會降低.主要是由于當(dāng)出現(xiàn)分支轉(zhuǎn)移指令時，同一個線程組中的不同線程會選擇不同的分支路徑執(zhí)行，而不同分支路徑以串行的方式執(zhí)行.另外，由于線程組采用鎖步的方式執(zhí)行[3]，執(zhí)行完的線程需要等待其他分支路徑上的線程完成執(zhí)行.因此，系統(tǒng)性能會受到一定的影響.

為了有效降低由于分支轉(zhuǎn)移引起的性能下降，當(dāng)前有一類方法將線程塊中執(zhí)行相同分支路徑的線程組合在一起執(zhí)行，以提升分支轉(zhuǎn)移情況下的線程級并行度，從而提升SIMD通道資源的利用率.Fung等人[6]提出了線程塊壓縮重組調(diào)度策略TBC(thread block compaction).然而，該方法在進行線程塊壓縮重組時，會出現(xiàn)屬于不同warp的線程對應(yīng)相同數(shù)據(jù)通道的情形，使得重組之后的warp數(shù)量并沒有減少，總的通道利用率和線程級并行度并未得到提升，這種情況被視為無效的線程重組.針對這種情況.Rhu等人[7]提出了基于壓縮適合性預(yù)測的線程塊壓縮重組調(diào)度策略CAPRI(compaction-adequacy predictor)，實現(xiàn)了基于壓縮重組歷史的預(yù)測機制，有效減少了不合理的線程塊壓縮重組.但是該方法采用首次保守預(yù)測和TB范圍內(nèi)一次分支單次預(yù)測的靜態(tài)預(yù)測方法，在一定程度上降低了預(yù)測的準(zhǔn)確度.另外，CAPRI方法在分析線程塊重組適合性時，并未考慮線程塊壓縮重組產(chǎn)生的性能收益(performance gains, PG)和性能開銷(performance overhead, PO)之間的關(guān)系，只有當(dāng)PG大于PO時，線程塊的壓縮重組才是有益的.

基于對TBC和CAPRI兩種策略的分析，本文提出了一種基于2階段同步的線程塊壓縮重組調(diào)度方法TSTBC(two-stage synchronization based thread block compaction scheduling).當(dāng)遇到分支轉(zhuǎn)移時，經(jīng)過2個階段的分析來判斷當(dāng)前線程塊是否適合進行壓縮重組.相對于CAPRI方法，壓縮重組的有效性得到了較好的提升.

本文的主要貢獻包括：分析了CAPRI方法對線程塊壓縮適合性判斷方法的不足和局限性；提出了2階段同步的線程塊壓縮重組調(diào)度方法和線程塊局部壓縮重組思想，進一步提高了線程塊壓縮重組適合性判斷的準(zhǔn)確度，并減少了因同步線程塊中的warp而產(chǎn)生的等待開銷；在分析線程塊壓縮重組適合性時，考慮了線程塊壓縮重組帶來的性能收益和開銷之間的關(guān)系，進一步提升了線程塊壓縮重組的有效性；實驗結(jié)果表明，相對于CAPRI，TSTBC在系統(tǒng)平均性能方面提升了9.4%.

本文首先介紹了基準(zhǔn)GPGPU體系結(jié)構(gòu)和相關(guān)概念以及重匯聚棧的分支轉(zhuǎn)移控制機制；其次分析了CAPRI方法的核心思想及其不足；然后重點分析闡述了TSTBC方法的算法設(shè)計和具體實現(xiàn)細節(jié)，并對實驗方法和實驗結(jié)果進行了分析；最后對相關(guān)工作進行了分析，并對全文進行了總結(jié).

1背景

1.1基準(zhǔn)GPGPU體系結(jié)構(gòu)

本文討論的基準(zhǔn)GPGPU體系結(jié)構(gòu)主要參考NVIDIA Fermi系列和文獻[8]，如圖1所示：

Fig. 1　Baseline architecture of GPGPU.圖1　基準(zhǔn)GPGPU體系結(jié)構(gòu)

GPGPU由多個流式多處理器(stream multi-processor, SM)組成，每個SM稱之為核.為了有效控制邏輯控制單元的數(shù)量，通常將多個SM組織成為一個圖形處理核組(graphics processing cluster, GPC).每個SM包含了眾多的處理單元(processing unit, PU)，每個PU負責(zé)最終的指令執(zhí)行.

SM的整個處理流水線可以分為前端和后端.前端主要包括取指部件、譯碼部件、記分板、線程調(diào)度器及分支處理單元等部件，其余部件均屬于后端.

取指部件負責(zé)根據(jù)每個線程組對應(yīng)的PC值從片外存儲將指令取到指令cache中.指令cache中的指令則依次送入到指令譯碼部件，經(jīng)過譯碼后的指令被送入到指令buffer中.指令buffer為每個線程組緩沖譯碼后的指令，便于指令快速執(zhí)行，并為每個線程組分配了一定數(shù)量的專用指令槽.記分板部件用來記錄每個線程組當(dāng)前執(zhí)行指令目的寄存器的使用情況.指令發(fā)射器負責(zé)按一定策略選取準(zhǔn)備就緒的指令發(fā)射.

經(jīng)過指令發(fā)射器發(fā)射的指令到達SIMD流水線后端執(zhí)行通道后，需要通過寄存器訪存部件獲取執(zhí)行所需要的操作數(shù).GPGPU為了滿足大量并發(fā)線程的同時執(zhí)行，設(shè)置了數(shù)量眾多的寄存器，并將這些寄存器組織為多個單端口的寄存器塊，方便多個并發(fā)線程的同時訪問.分支處理單元用來正確處理程序中的分支轉(zhuǎn)移指令，該部件為每個線程組均分配了1個棧結(jié)構(gòu)，又稱為重匯聚棧.SM通過訪存端口和片上網(wǎng)絡(luò)通信，以此實現(xiàn)對片外存儲器的訪問.

為了提高數(shù)據(jù)訪問效率，GPGPU采用多級高速緩存結(jié)構(gòu)，目前常見的GPGPU采用2級高速緩存結(jié)構(gòu).通常情況下，寄存器和1級cache放置在SM片上，2級cache則通過片上互聯(lián)網(wǎng)絡(luò)和所有的SM相連.

1.2基于重匯聚棧的分支轉(zhuǎn)移控制

分支轉(zhuǎn)移指令在通用應(yīng)用程序中非常普遍.如果線程組在執(zhí)行過程中遇到分支轉(zhuǎn)移指令，不同分支路徑只能串行執(zhí)行，必然降低執(zhí)行任務(wù)的TLP.而且，不同分支路徑的線程在執(zhí)行完相應(yīng)的分支路徑后，如果沒有進行特殊的重匯聚處理，會影響后續(xù)指令的執(zhí)行效率.基于重匯聚棧的重匯聚機制(post-dominator, PDOM)[9-10]可以有效解決由于分支轉(zhuǎn)移帶來的性能降低.該機制能在重匯聚處將同一線程組中執(zhí)行不同分支路徑的線程重組為分支前的線程組，以提高后續(xù)指令的TLP.

PDOM機制主要通過重匯聚棧實現(xiàn)對轉(zhuǎn)移分支的控制執(zhí)行.重匯聚棧的表項由重匯聚地址(recon-vergence program counter, RPC)、線程活躍掩碼和每個程序基本塊的首條指令PC(program counter) 3部分組成，其中活躍掩碼的每一位對應(yīng)1個線程的狀態(tài)，為“1”表示對應(yīng)線程活躍.圖2展示了PDOM重匯聚機制對分支控制流的處理過程示例，并假設(shè)1個warp由8個線程組成.1)在遇到分支轉(zhuǎn)移時，將棧頂初始化為重匯聚基本塊的PC，將其對應(yīng)的活躍掩碼位全部置為1；2)將不同分支路徑對應(yīng)的表項依次壓入棧中，并將棧頂指針TOS指向最終的棧頂，如圖2(b)所示；3)選擇棧頂對應(yīng)的分支路徑執(zhí)行，將該表項從棧中彈出，并修改棧頂指針TOS的指向，如圖2(c)(d)所示.此時，棧頂只剩下重匯聚基本塊對應(yīng)的表項，warp中的線程在此進行重匯聚，匯聚完成后繼續(xù)按鎖步的方式向前執(zhí)行.

Fig. 2　Example of PDOM reconvergence mechanism based on reconvergence stack.圖2　基于重匯聚棧的PDOM重匯聚機制示例

Fig. 3　Example of thread compaction, regrouping and prediction.圖3　線程塊壓縮、重組、預(yù)測過程示例

2CAPRI

CAPRI方法主要通過預(yù)測的方式來判斷后續(xù)線程塊是否適合壓縮重組.為了進行壓縮適合性預(yù)測，CAPRI方法設(shè)置了1張壓縮預(yù)測表來記錄各個轉(zhuǎn)移分支的壓縮重組歷史.在遇到分支轉(zhuǎn)移時，依據(jù)壓縮預(yù)測表中對應(yīng)分支的壓縮重組歷史信息來判斷是否對當(dāng)前線程組進行壓縮重組.另外，不管是否進行壓縮重組，在每次進行線程塊壓縮重組之后，CAPRI都需要對當(dāng)前分支的壓縮適合性進行重新分析，并對相應(yīng)的壓縮重組歷史信息進行修正.圖3展示了CAPRI方法進行線程塊壓縮重組預(yù)測的示例.線程壓縮重組單元沿用了TBC策略中的設(shè)計，它主要負責(zé)對多個線程組進行線程重組.內(nèi)部的優(yōu)先級編碼器會依次從不同的SIMD通道中選取第1個未選中的活躍線程進行組合，如圖3(b)(d)所示，其組合的結(jié)果分別如圖3(c)(e)所示.

線程塊壓縮重組完成后，會將對應(yīng)的活躍掩碼傳送給線程塊壓縮適合性預(yù)測器進行分析.該預(yù)測器主要統(tǒng)計每個通道的活躍線程數(shù)，并選擇其中的最大值.如果該最大值小于壓縮重組前的活躍線程數(shù)，則表明此次壓縮重組是適合的，并修正該分支的壓縮重組歷史位.從圖3(f)可以看出，經(jīng)過線程塊壓縮重組后的線程塊數(shù)量為3，與壓縮前的線程塊數(shù)量相同，表明此次線程塊壓縮重組不適合.

然而，CAPRI方法仍然會產(chǎn)生一定的無效壓縮重組，主要原因包括3個方面：1)由于CAPRI策略采用首次保守預(yù)測，某個分支第1次出現(xiàn)時均按適合壓縮重組執(zhí)行，這種預(yù)測錯誤的概率接近50%.對于某些類型的轉(zhuǎn)移分支來說，這種預(yù)測錯誤可能會對性能產(chǎn)生較大的影響.例如訪存密集型分支路徑或是執(zhí)行次數(shù)較少的分支，此時一次預(yù)測錯誤產(chǎn)生的開銷可能占整個開銷較大的比例.2)活躍線程對應(yīng)的通道分布情況與分支指令計算參數(shù)相關(guān)，而不同TB的線程對應(yīng)參數(shù)并不一定具有相似性和相關(guān)性，因此用當(dāng)前TB的壓縮適合性預(yù)測后續(xù)TB的壓縮適合性存在不確定性.3)在進行壓縮適合性預(yù)測時，CAPRI并沒有考慮壓縮重組產(chǎn)生的PG和PO之間的關(guān)系.即使CAPRI策略預(yù)測當(dāng)前線程塊適合壓縮重組，若線程塊壓縮重組后PG小于PO，系統(tǒng)性能仍然會下降.

32階段同步的線程塊壓縮重組調(diào)度(TSTBC)

CAPRI在預(yù)測線程塊壓縮適合性的準(zhǔn)確度上存在一定的誤差，仍然會出現(xiàn)一定比例的無效壓縮重組.與CAPRI方法采用預(yù)測的方式不同，TSTBC采用主動分析的方式，分2個階段對線程塊壓縮適合性進行分析，并在第2階段采用線程塊局部重組壓縮，進一步提高了壓縮重組的有效性.

為了實現(xiàn)TSTBC，相對于基準(zhǔn)的GPGPU體系結(jié)構(gòu)，對重匯聚棧進行了適當(dāng)修改，增加了壓縮適合性判斷邏輯部件和線程塊壓縮重組部件.其中，線程塊壓縮重組部件的實現(xiàn)參考TBC方法中的實現(xiàn).

3.1線程塊局部壓縮重組

在對線程塊進行壓縮重組的過程中，對線程塊壓縮重組有利的warp分布與處理任務(wù)本身和其計算的數(shù)據(jù)有關(guān)，有利于壓縮重組的warp將分布在各種可能的位置，甚至有可能集中分布在線程塊的某個局部區(qū)域.例如對于線程塊Ttb，假設(shè)其包含8個warp，分別為w1，w2，…，w8.如果只有w5，w6，w7，w8對Ttb的壓縮重組有貢獻，則真正發(fā)生重組的warp集中在該線程塊的后半部分，稱這種情況為線程塊的局部壓縮重組，它是TSTBC方法的基礎(chǔ).

3.2TSTBC的算法思想

TSTBC方法分2個階段對線程塊壓縮適合性進行判斷，在階段1進行整體分析，在階段2則對線程塊進行局部壓縮重組適合性分析，以進一步挖掘線程塊中適合壓縮重組的機會.

與TBC和CAPRI一樣，TSTBC同樣需要在分支轉(zhuǎn)移處對屬于同一個線程塊的warp同步.然而，與它們不同的是，這種同步分為2個階段.

階段1. TSTBC僅對前n個到達的warp進行同步.n在此取經(jīng)驗值，通過在實驗中測試n取不同值時(n=1，2，…，N，其中N為TB包含的warp數(shù))不同測試程序?qū)?yīng)的系統(tǒng)性能，取對應(yīng)平均性能最好的n值作為n的最終取值.在對前n個warp同步之后，需要對這n個warp進行壓縮適合性分析.通過對這n個warp的活躍掩碼分析，可以分析出壓縮重組后的warp數(shù)量.如果分析的結(jié)果小于壓縮重組前的warp數(shù)量，則表明前n個warp對整個壓縮重組是有利的，從而可以認為該線程塊有可能適合重組壓縮.然后，再對當(dāng)前TB余下的warp進行同步，并對所有warp對應(yīng)的掩碼進行進一步的壓縮適合性分析.如果當(dāng)前TB壓縮后生成的warp數(shù)小于某個warp壓縮閾值(warp compaction threshold, WCT)TWCT，表明當(dāng)前TB壓縮重組后產(chǎn)生的PG大于PO，則最終判斷當(dāng)前TB適合進行壓縮重組，并對當(dāng)前TB進行壓縮重組.若分析結(jié)果表明前n個warp不適合壓縮重組，則使前n個warp跳過線程塊壓縮重組部件繼續(xù)向前執(zhí)行，并進入到階段2.壓縮閾值參數(shù)TWCT的取值與參數(shù)n取值的方法類似.

階段2. 首先調(diào)度前n個已經(jīng)到達的warp，讓其跳過后續(xù)的線程壓縮重組并繼續(xù)向前執(zhí)行；然后對余下的N-n個warp進行同步；最后對這N-n個warp進行壓縮適合性分析.如果分析結(jié)果表明余下的warp適合壓縮重組，則對余下的warp進行壓縮重組，否則表明當(dāng)前線程塊不適合局部壓縮重組.為了實現(xiàn)的簡單，階段2的壓縮適合性判斷僅比較壓縮前后warp的數(shù)量.但是，階段2也可以增加與新的壓縮閾值參數(shù)的比較，以進一步提高重組壓縮適合性判斷的有效性.該壓縮閾值參數(shù)與階段1中壓縮閾值參數(shù)選取的方法一致，此工作將在以后的研究中繼續(xù)完善.

TSTBC具體的線程塊壓縮適合性判斷算法如算法1所示.在算法1中，最外層的if語句對不同的分支路徑進行處理，其if語句部分實現(xiàn)了對當(dāng)前分支進行2階段同步的線程塊壓縮重組；else部分用于處理與當(dāng)前分支路徑對應(yīng)的其他分支.對其他分支的處理無需再對線程組進行同步，因為處理完第1條分支后，所有的warp均已達到.

算法1. 2階段同步的線程塊壓縮適合性判斷算法.

if (wcnt

{ 同步前n個warp;

tmax=maximum(每個通道的線程數(shù));

if (tmax

{ 同步所有的warp;

tmax=maximum(每個通道的線程數(shù));

if (tmax

wcu(tTB);

}

else

{ 調(diào)度前n個到達的warp;

同步剩余的N-n個warp;

tmax=maximum(剩余每個通道的線程數(shù));

if (tmax

wcu(剩余的N-n個warp);

}

}

else

{tmax=maximum(每個通道的線程數(shù));

if (tmax

wcu(tTB);

}

如果某個warp中所有線程在分支轉(zhuǎn)移處均選擇相同的分支路徑，稱該warp沒有發(fā)生轉(zhuǎn)移.對于這樣的warp將不進行任何壓縮適合性判斷，因為這樣的warp對于線程壓縮重組不會有任何貢獻.因此，在進行TB的壓縮適合性判斷分析之前，應(yīng)過濾掉所有沒有發(fā)生轉(zhuǎn)移的warp，讓它們繼續(xù)向前執(zhí)行.因而，可能會存在一種特殊情形，即當(dāng)所有warp達到后，發(fā)生轉(zhuǎn)移的warp數(shù)量有可能少于n，此時僅比較壓縮前后的warp數(shù)量多少，主要原因是由于可供分析的warp數(shù)量偏少.該細節(jié)在算法實現(xiàn)時進行了考慮，但在算法1中沒有體現(xiàn).

分2階段對線程塊進行同步，可以進一步減少因同步等待產(chǎn)生的開銷.在階段1僅對前n個warp同步，并對它們進行了初步的壓縮適合性判斷.如果分析結(jié)果為真，則表明它們對整個線程塊的壓縮重組是有利的，可以將它們納入到整個線程塊的壓縮重組過程；否則，表明它們對整個線程塊的壓縮重組沒有貢獻，可以在后續(xù)的壓縮重組處理過程中忽略它們，此時可以讓這部分warp繼續(xù)向前執(zhí)行，減少了它們的同步等待延時，從而能減少整個線程塊的同步等待開銷.

當(dāng)階段1分析表明前n個warp對整個線程塊的壓縮重組沒有貢獻，根據(jù)線程塊局部壓縮重組的思想，并不意味著剩余的warp不適合進行壓縮重組.設(shè)置同步階段2，可以進一步挖掘適合壓縮重組的局部線程塊，提高壓縮重組的機會和有效性.因此，若通過分析判斷剩余的warp適合進行壓縮重組，則線程塊局部壓縮重組有利于系統(tǒng)的性能提升.

3.3改進的重匯聚棧

改進的重匯聚棧中，每個表項的活躍掩碼以線程塊級為單位，且增加了字段wcnt，該字段用來統(tǒng)計不同分支路徑當(dāng)前達到的線程塊數(shù).雖然活躍掩碼的寬度是線程塊級，但是線程調(diào)度執(zhí)行的基本單位仍然是warp.

圖4展示了改進的重匯聚棧結(jié)構(gòu)示例.這里假設(shè)一個TB包含4個warp，每個warp包含4個線程.圖4中棧頂?shù)膚cnt值表明基本塊C所在分支路徑已經(jīng)有2個warp到達.

Fig. 4　Example of improved reconvergence stack structure.圖4　改進的重匯聚棧結(jié)構(gòu)示例

3.4壓縮適合性判斷邏輯部件

壓縮適合性判斷邏輯部件在線程塊壓縮適合性分析的2個階段都需要用到，它對每個SIMD執(zhí)行通道對應(yīng)的線程數(shù)進行統(tǒng)計，并從中選出最大值，該最大值就是線程塊壓縮重組后產(chǎn)生的warp數(shù)量.圖5展示了壓縮適合性判斷邏輯部件的結(jié)構(gòu)示例.此處仍然假設(shè)1個TB包含4個warp，每個warp包含4個線程.從圖5可以看出，該TB對應(yīng)活躍掩碼經(jīng)過壓縮后將產(chǎn)生3個新的warp.在CAPRI方法中，下一個TB被判斷為適合進行壓縮重組；但是，TSTBC方法還需要將分析得到的最大值與TWCT進行比較方能進行判斷.

Fig. 5　Example of thread block compaction adequacydecision logic structure.圖5　線程塊壓縮適合性判斷邏輯部件結(jié)構(gòu)示例

圖6展示了出現(xiàn)分支轉(zhuǎn)移時壓縮適合性判斷邏輯部件對1個線程塊進行壓縮適合性分析判斷的示例.該示例中同樣假設(shè)1個TB包含4個warp，每個warp包含4個線程，參數(shù)n和TWCT均取值為2.圖6(b)表示線程塊壓縮適合性判斷分析的階段1.當(dāng)遇到分支轉(zhuǎn)移時，首先將重匯聚塊D對應(yīng)的表項壓入棧中，此時同步等待前2個warp到達，并將不同分支路徑對應(yīng)的表項壓入棧頂，通過邏輯分析部件對棧頂?shù)难诖a進行分析.分析的結(jié)果為2，表明如果對前2個warp進行壓縮，壓縮后將產(chǎn)生2個新的warp，這和壓縮之前的warp數(shù)量相同.因此，先前到達的2個warp并不適合進行壓縮重組.圖6(c)表示線程塊壓縮適合性判斷分析進入了階段2.在階段2，首先對剩下的warp進行同步，再對它們進行壓縮適合性分析.分析的結(jié)果為1，表示此部分線程塊壓縮重組后只產(chǎn)生1個新的warp，小于壓縮前的warp數(shù)量，表示余下的warp適合進行壓縮重組.

Fig. 6　Example of thread block compaction adequacy decision analysis using TSTBC as branch divergence occurs.圖6　分支轉(zhuǎn)移時TSTBC進行線程塊壓縮適合性判斷分析示例

3.5TSTBC與CAPRI的比較

CAPRI方法和本文提出的TSTBC方法都是從線程壓縮重組適合性的角度對線程的壓縮重組進行優(yōu)化，都是為了提高線程壓縮重組的有效性，盡量避免無效的線程塊壓縮重組，從而減少對線程組內(nèi)甚至是線程組間的數(shù)據(jù)局部性的破壞.然而，相對于CAPRI方法，TSTBC方法在對線程塊的壓縮重組優(yōu)化方面具有2方面的優(yōu)勢：

1) CAPRI方法用預(yù)測的方式來對后續(xù)線程塊壓縮重組的適合性進行判斷，而TSTBC方法對每個線程塊均采用主動的分析判斷其壓縮重組的適合性，并分2個階段進行判斷，其準(zhǔn)確度和有效性更高.

2) CAPRI方法和TSTBC方法對于適合進行壓縮重組的線程塊均需對包含的warp同步，但是由于TSTBC方法分2個階段來對線程塊進行同步，當(dāng)出現(xiàn)線程塊適合局部壓縮重組的情形時，TSTBC方法導(dǎo)致的同步等待延時相對更短.

4實驗及結(jié)果分析

4.1實驗平臺

為了對提出的方法進行驗證，我們對時鐘周期級性能模擬器GPGPU-sim(3.2.2版本)[11]進行了相應(yīng)的修改，并分別實現(xiàn)了對TSTBC，SCC(swizzled cycle compaction)[12]， CAPRI(1bL) (簡稱為CAPRI)方法的模擬.其中，選用SCC方法進行比對，是因為該方法是一種線程組內(nèi)的線程壓縮重組方法且具有代表性，這樣可以從其他的角度進行分析比較，也使得實驗更加充分合理.實驗過程中對GPGPU-sim的配置主要參照NVIDIA Fermi系列體系結(jié)構(gòu)，具體的部分參數(shù)配置如表1所示.

測試程序的選取來源于GPGPU-sim模擬器、NVIDIA CUDA SDK[13]和Rodinia[14]等.我們將測試程序分為2類:1)一類測試程序在出現(xiàn)分支時并未發(fā)生分支轉(zhuǎn)移現(xiàn)象，對這類測試程序進行線程塊壓縮重組的意義不大，將這類程序劃分為分支非轉(zhuǎn)移類測試程序；2)另一類測試程序劃分為轉(zhuǎn)移類測試程序.實驗過程一共使用了14個測試程序，涵蓋了圖像處理、概率統(tǒng)計分析、生物信息、模式識別、線性代數(shù)等多個領(lǐng)域，其中分支轉(zhuǎn)移類測試程序有6個，分支非轉(zhuǎn)移類測試程序有7個.所用的測試程序如表2所示.

Table 1　GPGPU-sim Parameter Configuration

Table 2　Benchmark for the Evaluation

4.2結(jié)果分析

本文從壓縮有效性、1級數(shù)據(jù)cache(L1D cache)訪問失效率、系統(tǒng)性能等方面對實驗結(jié)果進行了分析，并分別對PDOM,SCC,CAPRI,TSTBC四種線程調(diào)度方法進行了比較.

4.2.1壓縮有效性

實驗中主要用壓縮適合性分析的準(zhǔn)確度對壓縮有效性進行度量.圖7展示了一組分支轉(zhuǎn)移類測試程序的線程塊壓縮重組有效性.圖7中，StallBypass表示線程塊不應(yīng)該進行壓縮重組，但實際進行了壓縮重組；BypassStall表示線程塊應(yīng)該進行壓縮重組，但實際未進行壓縮重組；StallStall表示對線程塊進行了有效地壓縮重組；BypassBypass表示有效地跳過了線程塊的壓縮重組.4種情形中，只有StallStall和BypassBypass表示對線程塊壓縮重組的適合性進行了正確分析.實驗中對每個測試程序均用4種不同線程調(diào)度方法進行測試.從圖7可以看出，對于該類測試程序，TSTBC壓縮重組的有效性分析(包括StallStall和BypassBypass)均優(yōu)于其他3種方法，其平均準(zhǔn)確率達到了92.24%，相對PDOM和CAPRI分別提高了16.07%和7.59%，尤其是對于需要跳過的線程塊壓縮重組，其準(zhǔn)確率和PDOM非常接近;SCC壓縮重組的有效性最低，因為實際上只有平均18.7%的分支真正發(fā)生了轉(zhuǎn)移，而真正適合用SCC進行線程組內(nèi)的壓縮重組的分支比例為15.68%.另外，從圖7可以看出，在NW中幾乎所有的分支轉(zhuǎn)移均不適合線程塊壓縮重組，這是由于在該測試程序中絕大部分的分支判斷處線程塊均未發(fā)生實際轉(zhuǎn)移.

Fig. 7　Compaction validity of branch divergent benchmarks.圖7　分支轉(zhuǎn)移類測試程序壓縮有效性

圖8展示了一組分支非轉(zhuǎn)移類測試程序的線程塊壓縮重組有效性.由于此類程序執(zhí)行過程中幾乎沒有發(fā)生分支轉(zhuǎn)移，因此傳統(tǒng)的PDOM方法執(zhí)行此類程序時并不會對性能產(chǎn)生影響.TSTBC對該類程序的線程塊壓縮重組有效性分析的準(zhǔn)確率接近100%，CAPRI方法的準(zhǔn)確率也達到了99.3%，而SCC對此類程序進行的線程塊壓縮重組幾乎都是無效的.

Fig. 8　Compaction validity of branch non-divergent benchmarks.圖8　分支非轉(zhuǎn)移類測試程序壓縮有效性

4.2.2L1D cache訪問失效率

由于將屬于不同warp的線程重組在一起，線程壓縮重組在一定程度上破壞了原來warp內(nèi)部的數(shù)據(jù)局部性，會增加片外訪存次數(shù)和L1D cache的訪問失效率.圖9和圖10分別展示了分支轉(zhuǎn)移類測試程序和分支非轉(zhuǎn)移類測試程序?qū)?yīng)于PDOM,SCC,CAPRI,TSTBC四種方法的L1D cache訪問失效率對比情況.從圖9可以看出，對于分支類測試程序，由于提高了線程塊壓縮重組的有效性，相對于CAPRI，TSTBC的L1D cache的平均訪問失效率減少了4.53%.對于NW，由于CAPRI和TSTBC對線程壓縮重組的判定基本和PDOM一致.因此，這2種方法產(chǎn)生的失效率也接近PDOM.

Fig. 9　Normalized L1D cache miss rate of branchdivergent benchmarks.圖9　分支轉(zhuǎn)移類測試程序歸一化L1D cache失效率

Fig. 10　Normalized L1D cache miss rate of branchnon-divergent benchmarks.圖10　分支非轉(zhuǎn)移類測試程序歸一化L1D cache失效率

對于分支非轉(zhuǎn)移類測試程序，CAPRI和TSTBC的壓縮重組有效性基本上都接近100%，因此對數(shù)據(jù)局部性的破壞很小，因此這2種方法的L1D cache訪問失效率和PDOM的非常接近.由于SCC屬于線程組內(nèi)的線程壓縮重組，對所有測試程序的L1D cache訪問失效率均不會產(chǎn)生其他的影響，因此它和PDOM產(chǎn)生的失效率是一致的.

4.2.3性能分析

本文主要以IPC(instruction per cycle)為主要性能指標(biāo)對測試程序的運行性能進行分析.圖11和圖12分別展示了對應(yīng)于上述4種方法分支轉(zhuǎn)移類測試程序和分支非轉(zhuǎn)移類測試程序的性能結(jié)果比較.從圖11可以看出，對于分支轉(zhuǎn)移類測試程序，后3種線程塊調(diào)度方法均有不同程度的性能提升，其中TSTBC的IPC提升幅度最大，平均IPC比SCC和CAPRI分別提高了13.3%和9.4%，相對于基準(zhǔn)的PDOM方法提升了19.27%.

Fig. 11　Normalized IPC of branch divergent benchmarks.圖11　分支轉(zhuǎn)移類測試程序歸一化IPC

Fig. 12　Normalized IPC of branch non-divergentbenchmarks.圖12　分支非轉(zhuǎn)移類測試程序歸一化IPC

對于分支非轉(zhuǎn)移類測試程序，TSTBC和CAPRI方法的性能均接近于PDOM方法，主要是因為它們都對非轉(zhuǎn)移分支進行了過濾.因此，TSTBC對這類應(yīng)用程序的系統(tǒng)性能并不會產(chǎn)生太大的影響，CAPRI方法由于對壓縮重組適合性判斷存在誤差，會產(chǎn)生少許的同步開銷.

4.2.4參數(shù)取值分析

為了確定TSTBC算法中參數(shù)n和壓縮閾值參數(shù)TWCT的值，我們分別對n和TWCT取1,2,…,N之間的所有值，然后測試對應(yīng)每種n和TWCT取值組合下所有分支轉(zhuǎn)移類測試程序運行的IPC，從最終N2個結(jié)果中選取IPC最好情況下對應(yīng)的n和TWCT的值作為這2個參數(shù)最終的值.由于篇幅的限制，在此僅將結(jié)果最好的2組數(shù)據(jù)展示出來.

圖13展示了當(dāng)TWCT=2、n=1,2,…,8時整個分支轉(zhuǎn)移類測試程序的平均IPC.從圖13可以看出，當(dāng)TWCT=2,n=3時，該類測試程序的平均IPC最高.另外，當(dāng)TWCT取一定值且n=1,7,8時的IPC相差無幾，此時TSTBC基本上退化成階段1同步的線程塊壓縮重組，因為此時階段2分析中的某階段的warp數(shù)量為1或0，已經(jīng)無需再進行分析處理.

Fig. 13　Normalized IPC of branch divergent benchmarks.圖13　分支轉(zhuǎn)移類測試程序的歸一化IPC

圖14展示了當(dāng)n=3且TWCT=1,2,…,8時分支轉(zhuǎn)移類測試程序的平均IPC.圖14同樣可以發(fā)現(xiàn)當(dāng)TWCT=2，n=3時，分支轉(zhuǎn)移類測試程序的平均IPC最高.因此，最終將確定TWCT=2，n=3.在4.2.1,4.2.2,4.2.3節(jié)的實驗結(jié)果均以此為基礎(chǔ).

另外，從圖14可以看出，當(dāng)TWCT>5時，各測試程序的性能基本上都是低于PDOM方法，原因是因為此時壓縮程度超過5的線程塊非常少，而且同步線程塊內(nèi)的warp會產(chǎn)生一定的開銷，反而降低了系統(tǒng)性能.

Fig. 14　Normalized IPC of branch divergent benchmarks.圖14　分支轉(zhuǎn)移類測試程序的歸一化IPC

4.2.5硬件開銷

本方法需在傳統(tǒng)基準(zhǔn)體系結(jié)構(gòu)的基礎(chǔ)上增加線程塊壓縮重組部件以及線程塊壓縮適合性判斷邏輯2個部件，并對重匯聚棧的結(jié)構(gòu)進行了一定的改動.其中，重匯聚棧的結(jié)構(gòu)是在參照TBC方法中的基礎(chǔ)上進行了一定的改動，每個表項增加了字段wcnt，該字段用4 b表示.由于每個線程塊設(shè)置一個棧，實驗中每個棧的表項長度設(shè)為32，因此每個棧只需增加16 B.另外，每個核上允許執(zhí)行的最大TB數(shù)為8，因此一個SM增加的硬件大小僅為128 B.線程塊壓縮重組部件的設(shè)計參考TBC的設(shè)計，其硬件開銷參考文獻[6]中的分析.線程塊壓縮適合性判斷邏輯相對于CAPRI中的壓縮適合性判斷邏輯部件的設(shè)計，去掉了記錄壓縮重組適合性歷史信息的表結(jié)構(gòu)，因此其硬件開銷要小于CAPRI的硬件開銷.

5相關(guān)工作

分支轉(zhuǎn)移在很多通用應(yīng)用程序中都存在，GPGPU在處理該類應(yīng)用程序時的性能會由此受到影響.目前，對分支轉(zhuǎn)移處理進行性能優(yōu)化的研究主要集中在線程組間的線程重組、線程組內(nèi)的線程重組和多分支并行執(zhí)行3個方面.

Fung等人[10]提出了動態(tài)的warp重組策略DWF(dynamic warp formation)和線程塊壓縮重組策略TBC[6].Narasiman等人[15]提出了LWM(large warp microarchitecture)策略，通過提高線程組的寬度來增加每個分支路徑上的活躍線程數(shù)量，并在大的線程組內(nèi)進行線程重組.LWM中提到的large warp由多個warp組成，實質(zhì)上還是在線程組間進行線程重組.Malits等人[16]提出的線程重組策略O(shè)DGS(oracle dynamic global scheduling)將線程組間的線程重組從SM內(nèi)擴展至SM之間.上述線程重組壓縮方法都屬于線程組間的線程重組，但是這些方法都沒有考慮線程壓縮重組的有效性，產(chǎn)生的無效壓縮重組會帶來較大的開銷.本文提出的TSTBC方法著重考慮了線程組間線程壓縮重組的有效性，產(chǎn)生的開銷更小.

Vaidya等人[12]提出了線程組內(nèi)的線程重組機制BCC(basic cycle compaction)和SCC，利用實際的物理SIMD通道數(shù)比線程組寬度小的特點，將線程組內(nèi)的線程重組為與實際物理SIMD通道寬度相等的線程組，壓縮了原始線程組的執(zhí)行周期數(shù).Jin等人[17]提出的線程組內(nèi)的線程重組機制HWS (hybrid warp size)也包含了這樣的思想.此類方法避免了破壞線程組內(nèi)的數(shù)據(jù)局部性，然而該方法受限于實際SIMD通道數(shù)的配置情況，尤其當(dāng)實際SIMD物理通道數(shù)接近或等于線程組的寬度時，線程組內(nèi)可供重組的機會大大減少，有效的線程壓縮重組更少，對整個系統(tǒng)性能提升影響很小.因此，線程組內(nèi)的線程重組方法僅適用于某些特定的硬件環(huán)境，適用性較差.而本文提出的TSTBC方法沒有這方面的限制.

Brunie等人[18]同時提出的線程重組策略SBI(simultaneous branch interweaving)和SWI(simul-taneous warp interweaving)，通過對指令發(fā)射部件的修改實現(xiàn)了雙分支路徑上同時發(fā)射指令，同時也包含了線程壓縮重組的思想.Wang等人[19]提出并實現(xiàn)了MSMD(multiple SIMD, multiple data)執(zhí)行模型，設(shè)置了多個可靈活劃分的、獨立的SIMD數(shù)據(jù)通道，使得不同分支路徑上的線程組可以同時執(zhí)行.但是，該類方法的物理實現(xiàn)更加復(fù)雜，實用性較低.

6總結(jié)

本文對前人提出的線程塊壓縮重組調(diào)度算法進行了分析和討論，并在此基礎(chǔ)上提出了2階段同步的線程塊壓縮重組調(diào)度方法TSTBC.該方法分2個階段對線程塊的壓縮重組適合性進行分析，提出了線程塊局部壓縮重組的思想.相對于CAPRI方法，TSTBC方法能進一步提高線程塊壓縮重組的有效性，減少了由線程塊壓縮重組而產(chǎn)生的開銷和對線程組內(nèi)數(shù)據(jù)局部性的破壞，并降低L1D cache訪問的失效率.實驗結(jié)果表明相對于PDOM方法和CAPRI方法，TSTBC方法的平均IPC分別提高了19.27%和9.4%.

然而，本方法在實現(xiàn)上仍然存在一定的不足，主要是實驗過程中對參數(shù)n和TWCT選取靜態(tài)值，對于有的應(yīng)用程序并不是最佳取值.因此，后續(xù)工作中還需進一步考慮對不同的應(yīng)用程序動態(tài)確定參數(shù)n和TWCT的取值.

參考文獻

[1]Meng J, Tarjan D, Skadron K. Dynamic warp subdivision for integrated branch and memory divergence tolerance[C] //Proc of the 37th Int Symp on Computer Architecture. New York: ACM, 2010: 235-246

[2]Lindholm E, Nickolls J, Oberman S, et al. NVIDIA Tesla: A unified graphics and computing architecture[J]. IEEE Micro, 2008, 28(2): 39-55

[3]Keckler S W, Dally W J, Khailany B, et al. GPUs and the future of parallel computing[J]. IEEE Micro, 2011, 31(5): 7-17

[4]Nickolls J, Dally W J. The GPU computing era[J]. IEEE Micro, 2010, 30(2): 56-69

[5]Du P, Weber R, Luszczek P, et al. From CUDA to OpenCL: Towards a performance-portable solution for multi-platform GPU programming[J]. Parallel Computing, 2012, 38(8): 391-407

[6]Fung W W L, Aamodt T M. Thread block compaction for efficient SIMT control flow[C] //Proc of the 17th Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2011: 25-36

[7]Rhu M, Erez M. CAPRI: Prediction of compaction-adequacy for handling control-divergence in GPGPU architectures[C] //Proc of the 39th Int Symp on Computer Architecture. Piscataway, NJ: IEEE, 2012: 61-71

[8]Aamodt T M, Fung W W L. GPGPU-Sim3.x manual[EB/OL]. (2012-08-08) [2015-02-01]. http://gpgpu-sim.org/manual/index.php/GPGPU -Sim_3.x_Manual[9]Levinthal A, Porter T. Chap—A SIMD graphics processor[C] //Proc of ACM SIGGRAPH’84. New York: ACM, 1984: 77-82

[10]Fung W W L, Sham I, Yuan G, et al. Dynamic warp formation and scheduling for efficient GPU control flow[C] //Proc of the 40th Annual IEEE/ACM Int Symp on Microarchitecture. Piscataway, NJ: IEEE, 2007: 407-420

[11]Bakhoda A, Yuan G L, Fung W W L, et al. Analyzing CUDA workloads using a detailed GPU simulator[C] //Proc of the IEEE Int Symp on Performance Analysis of Systems and Software. Piscataway, NJ: IEEE, 2009: 163-174

[12]Vaidya A S, Shayesteh A, Woo D H, et al. SIMD divergence optimization through intra-warp compaction[J]. ACM SIGARCH Computer Architecture News, 2013, 41(3): 368-379

[13]NVIDIA Corporation. CUDA C/C++ SDK 4.0 CODE Samples[CP/OL]. 2011 [2015-02-01]. https://developer.nvidia.com/cuda-toolkit-40[14]Che S, Boyer M, Meng J, et al. Rodinia: A benchmark suite for heterogeneous computing[C] //Proc of the IEEE Int Symp on Workload Charact-erization. Piscataway, NJ: IEEE, 2009: 44-54

[15]Narasiman V, Shebanow M, Lee C J, et al. Improving GPU performance via large warps and two-level warp scheduling[C] //Proc of the 44th Annual IEEE/ACM Int Symp on Microarchitecture. New York: ACM, 2011: 308-317

[16]Malits R, Bolotin E, Kolodny A, et al. Exploring the limits of GPGPU scheduling in control flow bound applications[J]. ACM Trans on Architecture and Code Optimization, 2012, 8(4): 29

[17]Jin X, Daku B, Ko S B. Improved GPU SIMD control flow efficiency via hybrid warp size mechanism[J]. Microprocessors and Microsystems, 2014, 38(7): 717-729

[18]Brunie N, Collange S, Diamos G. Simultaneous branch and warp interweaving for sustained GPU performance[C] //Proc of the 39th Int Symp on Computer Architecture. Piscataway, NJ: IEEE, 2012: 49-60

[19]Wang Y, Chen S, Wan J, et al. A multiple SIMD, multiple data (MSMD) architecture: Parallel execution of dynamic and static SIMD fragments[C] //Proc of the 19th Int Symp on High Performance Computer Architecture. Piscataway, NJ: IEEE, 2013: 603-614

Zhang Jun, born in 1978. PhD candidate, associate professor. Member of China Computer Federation. His research interests include high performance computing and computer architecture.

He Yanxiang, born in 1952. PhD, professor and PhD supervisor. Member of China Computer Federation. His research interests include trusted software, distributed parallel processing and high performance computing.

Shen Fanfan, born in 1987. PhD candidate. His research interests include high perfor-mance computing, computer architecture and storage system (shenfanfan_168@qq.com).

Jiang Nan, born in 1976. PhD candidate, lecturer. Member of China Computer Federation. Her research interests include trusted software, trusted compilation and computer architecture (nanjiang@whu.edu.cn).

Li Qing’an, born in 1986. PhD, associate professor. Member of China Computer Federation. His research interests include compilation optimization, computer archi-tecture and embedded system (qali@whu.edu.cn).

Two-Stage Synchronization Based Thread Block Compaction Scheduling Method of GPGPU

Zhang Jun1,3, He Yanxiang1,2, Shen Fanfan1, Jiang Nan1,4, and Li Qing’an1,2

1(ComputerSchool,WuhanUniversity,Wuhan430072)2(StateKeyLaboratoryofSoftwareEngineering(WuhanUniversity),Wuhan430072)3(SchoolofSoftware,EastChinaUniversityofTechnology,Nanchang330013)4(SchoolofComputerScience,HubeiUniversityofTechnology,Wuhan430068)

AbstractThe application of general purpose graphics processing unit (GPGPU) has become increasingly extensive in the general purpose computing fields facing high performance computing and high throughput. The powerful computing capability of GPGPU comes from single instruction multiple data (SIMD) execution model it takes. Currently, it has become the main stream for GPGPU to implement the efficient execution of the computing tasks via massive high parallel threads. However the parallel computing capability is affected during dealing with the branch divergent control flow as different branch path is processed sequentially. In this paper, we propose TSTBC (two-stage synchronization based thread block compaction scheduling) method based on analyzing the previously proposed thread block compaction scheduling methods in inefficient dealing with divergent branches. This method analyzes the effectiveness of thread block compaction and reconstruction via taking the use of the adequacy decision logic of thread block compaction and decreases the number of inefficient thread block compaction. The simulation experiment results show that the effectiveness of thread block compaction and reconstruction is improved to some extent relative to the other same type of methods, and the destruction on data locality inside the thread group and the on-chip level-one data cache miss rate can be reduced effectively. The performance of the whole system is increased by 19.27% over the baseline architecture.

Key wordsgeneral purpose graphics processing unit (GPGPU); thread scheduling; thread block compaction and reconstruction; two-stage synchronization; branch divergence

收稿日期：2015-02-09；修回日期：2015-07-06

基金項目：國家自然科學(xué)基金重點項目(91118003)；國家自然科學(xué)基金項目(61373039,61170022,61462004)；江西省教育廳科技項目(GJJ150605)

通信作者：何炎祥(yxhe@whu.edu.cn)

中圖法分類號TP302

This work was supported by the Key Program of the National Natural Science Foundation of China (91118003), the National Natural Science Foundation of China (61373039,61170022,61462004), and the Science and Technology Project of Jiangxi Province Education Department (GJJ150605).