基于2階段同步的GPGPU線程塊壓縮調度方法

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

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

?

基于2階段同步的GPGPU線程塊壓縮調度方法

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

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

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

關鍵詞通用圖形處理器；線程調度；線程塊壓縮重組；2階段同步；分支轉移

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

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

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

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

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

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

1背景

1.1基準GPGPU體系結構

本文討論的基準GPGPU體系結構主要參考NVIDIA Fermi系列和文獻[8]，如圖1所示：

Fig. 1　Baseline architecture of GPGPU.圖1　基準GPGPU體系結構

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

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

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

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

為了提高數據訪問效率，GPGPU采用多級高速緩存結構，目前常見的GPGPU采用2級高速緩存結構.通常情況下，寄存器和1級cache放置在SM片上，2級cache則通過片上互聯網絡和所有的SM相連.

1.2基于重匯聚棧的分支轉移控制

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

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

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

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

2CAPRI

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

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

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

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

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

為了實現TSTBC，相對于基準的GPGPU體系結構，對重匯聚棧進行了適當修改，增加了壓縮適合性判斷邏輯部件和線程塊壓縮重組部件.其中，線程塊壓縮重組部件的實現參考TBC方法中的實現.

3.1線程塊局部壓縮重組

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

3.2TSTBC的算法思想

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

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

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

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

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

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

if (wcnt

{ 同步前n個warp;

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

if (tmax

{ 同步所有的warp;

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

if (tmax

wcu(tTB);

}

else

{ 調度前n個到達的warp;

同步剩余的N-n個warp;

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

if (tmax

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

}

}

else

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

if (tmax

wcu(tTB);

}

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

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

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

3.3改進的重匯聚棧

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

圖4展示了改進的重匯聚棧結構示例.這里假設一個TB包含4個warp，每個warp包含4個線程.圖4中棧頂的wcnt值表明基本塊C所在分支路徑已經有2個warp到達.

Fig. 4　Example of improved reconvergence stack structure.圖4　改進的重匯聚棧結構示例

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

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

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

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

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

3.5TSTBC與CAPRI的比較

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

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

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

4實驗及結果分析

4.1實驗平臺

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

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

Table 1　GPGPU-sim Parameter Configuration

Table 2　Benchmark for the Evaluation

4.2結果分析

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

4.2.1壓縮有效性

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

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

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

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

4.2.2L1D cache訪問失效率

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

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

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

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

4.2.3性能分析

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

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

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

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

4.2.4參數取值分析

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

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

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

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

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

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

4.2.5硬件開銷

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

5相關工作

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

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

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

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

6總結

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

然而，本方法在實現上仍然存在一定的不足，主要是實驗過程中對參數n和TWCT選取靜態值，對于有的應用程序并不是最佳取值.因此，后續工作中還需進一步考慮對不同的應用程序動態確定參數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

基金項目：國家自然科學基金重點項目(91118003)；國家自然科學基金項目(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).