通用圖形處理器GPGPU的并行計(jì)算研究*

張鵬博，郭兵，黃義純，曹亞波

(四川大學(xué) 計(jì)算機(jī)學(xué)院，成都 610065)

通用圖形處理器GPGPU的并行計(jì)算研究*

張鵬博，郭兵，黃義純，曹亞波

(四川大學(xué) 計(jì)算機(jī)學(xué)院，成都 610065)

隨著圖形處理器(GPU)從僅用來進(jìn)行圖形圖像渲染，脫離成為并行計(jì)算平臺通用圖形處理器(GPGPU)，其計(jì)算能力越來越強(qiáng)，本文在研究GPGPU體系結(jié)構(gòu)的基礎(chǔ)上對GPGPU并行計(jì)算線程調(diào)度進(jìn)行深入研究，闡述了GPU線程調(diào)度原理，揭示了SIMT調(diào)度模式的不足。通過公式推導(dǎo)闡述了系統(tǒng)功耗與系統(tǒng)運(yùn)行頻率的關(guān)系。

大數(shù)據(jù)；并行計(jì)算；線程調(diào)度；GPU節(jié)能

引 言

隨著大數(shù)據(jù)研究技術(shù)的進(jìn)步，大數(shù)據(jù)已經(jīng)進(jìn)入到各行各業(yè)，美國麥肯錫公司稱：“數(shù)據(jù)已經(jīng)滲透到當(dāng)今每個行業(yè)和業(yè)務(wù)職能領(lǐng)域，成為重要的生產(chǎn)因素。人們對于大數(shù)據(jù)的挖掘和運(yùn)用，預(yù)示著新一波生產(chǎn)力增長和消費(fèi)盈余浪潮的到來”[1]。大數(shù)據(jù)自身5V(體量大、速度快、模態(tài)多、難辨識、價值大密度低)特征決定了馮·諾依曼計(jì)算機(jī)CPU用來處理數(shù)據(jù)還遠(yuǎn)遠(yuǎn)不能滿足處理要求。

由于游戲產(chǎn)業(yè)的帶動，早期GPU多用來對圖形圖像進(jìn)行渲染。隨著工藝技術(shù)的進(jìn)步，今天GPU的功能已經(jīng)遠(yuǎn)遠(yuǎn)不止于此，其逐漸成為研究者進(jìn)行并行計(jì)算的通用并行處理器。GPGPU的體系結(jié)構(gòu)及多核硬件架構(gòu)也很好地適應(yīng)了并行計(jì)算的要求。

傳統(tǒng)并行調(diào)度模式主要分為4類：單指令，多數(shù)據(jù)(Single Instruction Multiple Data SIMD)；多指令，多數(shù)據(jù)(Multiple Instruction Multiple Data MIMD)；單指令，單數(shù)據(jù)(Single Instruction Single Data SISD)；多指令，單數(shù)據(jù)(Multiple Instruction Single Data MISD)。GPGPU采用的是SIMD執(zhí)行模式，但為了獲得更高的并行計(jì)算效率，主流的圖形處理器又派生出單指令多線程(Single Instruction Multiple Thread SIMT)模式。

1 通用圖形處理器體系結(jié)構(gòu)及相關(guān)概念

目前市場上通用圖形處理器廠商主要有(英偉達(dá)NVIDIA)、AMD、英特爾(Intel)三大廠商，其產(chǎn)品在宏觀結(jié)構(gòu)上沒有太大差別,但在微觀體系結(jié)構(gòu)上各有特點(diǎn)。因?yàn)镹VIDIA公司的通用圖形處理器市場占有率比較高，所以本文關(guān)于GPU的論述皆以NVIDIA的產(chǎn)品為標(biāo)準(zhǔn)。

1.1 GPGPU線程層級

GPGPU對線程的管理分為3個層級：線程網(wǎng)格(Grid)、線程塊(ThreadBlock)、線程組(Warp)。GPGPU線程結(jié)構(gòu)如圖1所示。

圖1 GPGPU線程結(jié)構(gòu)

運(yùn)行在GPU上的程序稱為kernel(內(nèi)核函數(shù))，kernel以線程網(wǎng)格的形式組織，每個線程網(wǎng)格由若干個線程塊組成，每個線程塊又由若干個線程組成。實(shí)際運(yùn)行時kernel以block為單位執(zhí)行,引入Grid只是用來表示一系列可以被并行執(zhí)行的block的集合。各線程塊之間無法通信也沒有執(zhí)行順序,線程塊內(nèi)的線程可以通過共享存儲器通信。線程組(warp)則通常由32個線程組成,是線程并發(fā)執(zhí)行的基本單位。GPGPU內(nèi)的并行分為線程塊并行和線程塊內(nèi)線程并行兩個級別。

1.2 GPU宏觀體系結(jié)構(gòu)

圖2為GPGPU的硬件映射?？梢钥闯?，通用圖形處理器中有若干個SM(流多處理器)，SM是GPGPU的計(jì)算核心。每個SM中又包含8個標(biāo)量流處理器SP和少量其他的計(jì)算單元。在商業(yè)上，GPU通常被說成擁有數(shù)百個“核”,這個“核”指的是這里的SP，這種說法不夠準(zhǔn)確，因?yàn)镾P只是執(zhí)行單元，并不是完整的處理核心。

圖2 GPGPU硬件映射

可以看出,通用圖形處理器存儲層次有寄存器、高速緩存、芯片外存儲器三個級別。高速緩存又可以分為一級緩存、二級緩存、三級緩存，每個SM中會包含眾多數(shù)量的寄存器，通常一級緩存和寄存器放在SM內(nèi)部。GPGPU的宏觀體系結(jié)構(gòu)如圖3所示。

圖3 GPGPU宏觀體系結(jié)構(gòu)

kernel函數(shù)以block為單位執(zhí)行，同一block中的線程可以通過共享存儲器共享數(shù)據(jù)，所以同一個block內(nèi)的線程需要發(fā)射到同一個SM。而每個線程則會被發(fā)射到一個SP上執(zhí)行。值得注意的是,一個線程塊要被發(fā)送到同一個SM，但是同一個SM上并不一定只有一個block的上下文。因?yàn)楫?dāng)一個block 訪存時另一個block可以搶占SM執(zhí)行。

2 通用圖形處理器線程調(diào)度方法

線程調(diào)度是指將計(jì)算任務(wù)分配到不同的處理單元，并按照一定的順序執(zhí)行的過程[3]。通用圖形處理器中的線程調(diào)度一共分為三個級別：線程組級別、線程塊級別、kernel級別。目前對線程調(diào)度的研究主要集中在線程組級別和線程塊級別，相比之下，kernel級別的調(diào)度研究比較少，所以主要研究前兩種調(diào)度方式。

2.1 線程組級別線程調(diào)度

32個線程組成的線程束(warp)是GPU的基本執(zhí)行單元。每個線程束中的線程同時執(zhí)行，在理想的情況下，如果要獲取當(dāng)前指令只需要訪問內(nèi)存一次取出指令，然后將取出的指令發(fā)射到這個線程束占用的所有SP中執(zhí)行[4]。通用圖形處理器的并行計(jì)算的高效率則主要是依賴于SIMT模式，NVIDIA公司GPU的SIMT調(diào)度過程分為軟件調(diào)度和硬件調(diào)度。在GPGPU進(jìn)行計(jì)算時，系統(tǒng)以一組(NVIDIA規(guī)定32個線程為一組)線程組成一個warp，然后以warp 為單位進(jìn)行取指運(yùn)算，而不是以線程為單位取指。warp 的調(diào)度組織形式考慮到了線程組之間的耦合性，主要體現(xiàn)在每一個warp中分配的線程相關(guān)性要盡量小。

如果一個warp 與另一個相鄰的warp有比較高的相關(guān)性，并且該線程束需要等待另一個warp 執(zhí)行結(jié)果，那么要等待warp就會被調(diào)度器暫時掛起，接著調(diào)度器會自動越過該warp去調(diào)度下一個不相關(guān)的warp執(zhí)行。這樣就保證在等待的warp被掛起等待相關(guān)事件的時候，釋放處理器去處理其他線程束，這種措施使得線程等待處理器執(zhí)行的開銷接近為零。

圖4 分支轉(zhuǎn)移執(zhí)行圖

然而應(yīng)用程序中會普遍出現(xiàn)分支轉(zhuǎn)移指令，按結(jié)構(gòu)化屬性可以分為：結(jié)構(gòu)化分支轉(zhuǎn)移指令和非結(jié)構(gòu)化分支轉(zhuǎn)移指令兩類。結(jié)構(gòu)化分支轉(zhuǎn)移指令主要是指程序中包含if語句和for、while、switch循環(huán)分支轉(zhuǎn)移指令等；非結(jié)構(gòu)化則主要是指程序中包含break、continue、goto等指令或者異常處理中的異常跳轉(zhuǎn)指令等。分支轉(zhuǎn)移執(zhí)行如圖4所示。

任何的分支指令(if/for/while/switch/break)都有可能會導(dǎo)致線程分歧，線程遇到分歧時會順序執(zhí)行每個分支路徑，同時阻止不在此路徑上的線程執(zhí)行，直到所有分支路徑上線程執(zhí)行完成，線程重新匯合到主路徑執(zhí)行路徑。

線程分支主要有以下情況：如果一個線程束內(nèi)的32個線程都只滿足同一個分支，就稱該warp滿足“分支按warp對齊”，這時程序的分支基本不會影響系統(tǒng)執(zhí)行效率。但是，如果一個warp的32個線程分別滿足多個不同的分支，那么不滿足當(dāng)前正在執(zhí)行分支的線程就有可能會采用插入等待或者假執(zhí)行(會參加計(jì)算，但是不保留計(jì)算結(jié)果)的方式。因?yàn)?，warp內(nèi)的每個線程都會判定是否滿足某個分支。一旦判定滿足，就會立即執(zhí)行分支內(nèi)的代碼；如果不滿足，則線程會暫停執(zhí)行，直到其所等待的其他線程執(zhí)行完成，然后再開始下一步的執(zhí)行。這種情況下總的運(yùn)行時間就是多個運(yùn)行分支的時間之和。

因?yàn)橥ㄓ脠D形處理器最小的執(zhí)行單位是warp，所以如果warp內(nèi)不同線程的循環(huán)次數(shù)不同，就會產(chǎn)生另一種分支情況，并且warp的執(zhí)行時間是循環(huán)次數(shù)最多的那個線程所花費(fèi)的時間。

這種調(diào)度方法的缺點(diǎn)是在程序執(zhí)行過程中，如果線程組遇到分支轉(zhuǎn)移指令，則warp中的每一個線程就會根據(jù)分支指令的執(zhí)行結(jié)果選擇后續(xù)執(zhí)行的分支路徑，這種情況會出現(xiàn)部分線程執(zhí)行不同分支路徑的情形。而且通用圖形處理器SIMT模式下只允許線程組在一個時刻執(zhí)行一條指令，導(dǎo)致不同的分支路徑只能串行執(zhí)行，則必然導(dǎo)致線程級并行的效率降低。

2.2 線程塊級別線程調(diào)度

通用圖形處理器運(yùn)行的SIMT線程調(diào)度模型需要基于NVIDIA公司的CUDA平臺，利用NVIDIA CUDA編程平臺編寫的程序一般要分為主機(jī)端串行部分和設(shè)備端并行部分，其中串行部分依然在傳統(tǒng)CPU上運(yùn)行，而并行部分則要發(fā)射到NVIDIA公司通用圖形處理器上執(zhí)行。通過上文介紹我們知道，執(zhí)行在GPGPU上的程序又被稱為kernel程序，kernel程序在發(fā)射到通用GPU硬件執(zhí)行前會形成一組并行執(zhí)行的線程組。執(zhí)行在GPU上的內(nèi)核程序需要由程序員手動編寫，同時程序員還需要編寫一些準(zhǔn)備程序，如數(shù)據(jù)從CPU存儲空間向GPGPU存儲空間的傳遞程序、指定線程數(shù)量、線程塊的劃分、存儲空間的分配程序等。

設(shè)備端的程序從程序員編寫到最終在NVIDIA的GPU上執(zhí)行的全過程中會涉及到兩個調(diào)度過程：線程軟件調(diào)度和硬件調(diào)度過程。SIMT調(diào)度圖如圖5所示，軟件調(diào)度過程流程見圖5(a),硬件調(diào)度流程見圖5(b)。

圖5 SIMT調(diào)度圖

在軟件調(diào)度過程中，系統(tǒng)中內(nèi)核代碼會根據(jù)程序員指定的線程數(shù)量形成一定數(shù)量的線程。軟件調(diào)度將這組線程分成若干個線程塊(block)，線程塊的數(shù)目也是由程序員在編程時顯示指定的，每個block中都會包含一定數(shù)量的線程。最終形成的這些block就是由軟件調(diào)度的結(jié)果，接著以這些block為單位進(jìn)入硬件調(diào)度過程。

在硬件調(diào)度過程中,block中的線程又會重新組合形成warp。在內(nèi)核線程被執(zhí)行時，以整個線程塊的形式發(fā)射到GPGPU上的SM，每一個block發(fā)射到同一個SM，然后以warp為單位進(jìn)行SIMT 調(diào)度執(zhí)行。warp中線程指令載入到指令緩存后會被譯碼單元譯碼，每個線程取自己的操作數(shù)進(jìn)入ALU執(zhí)行，等待存儲器數(shù)據(jù)訪問的warp進(jìn)入等待區(qū)。當(dāng)warp中線程全部執(zhí)行完成并進(jìn)入寫回操作，SIMT調(diào)度全部任務(wù)執(zhí)行完成。

3 通用圖形處理器節(jié)能方法

目前，學(xué)術(shù)上實(shí)現(xiàn)計(jì)算機(jī)節(jié)能的技術(shù)主要有兩類：一類考慮軟件級的節(jié)能，主要從操作系統(tǒng)或應(yīng)用軟件中尋找優(yōu)化方法；第二類考慮硬件級的節(jié)能，節(jié)能措施主要是設(shè)計(jì)綠色平臺架構(gòu)、搭建節(jié)能中心、開發(fā)低功耗設(shè)備[7]。

動態(tài)功耗的計(jì)算公式為：

(1)

其中，Pd代表動態(tài)功耗，Vdd表示系統(tǒng)的電壓，f表示系統(tǒng)的頻率；C1與Nsw是與電路自身特性有關(guān)的參數(shù)，當(dāng)電路固定下來后可以看成一個常量K，則上述公式化簡為：

(2)

由于設(shè)計(jì)的電路中，頻率和電壓具有線性關(guān)系，所以上述公式進(jìn)一步簡化為：

(3)

其中K′為一個常數(shù),若用Wd表示系統(tǒng)的動態(tài)能耗，則：

(4)

由數(shù)學(xué)知識可得到如下公式：

(5)

其中，C′只與具體電路特性有關(guān)。由式(5)可知，任務(wù)執(zhí)行時的頻率完全決定任務(wù)運(yùn)行的功耗。主要是常用的節(jié)能動態(tài)電壓與頻率調(diào)節(jié)(DynamicVoltageandFrequencyScaling，DVFS)技術(shù)是基于系統(tǒng)頻率實(shí)現(xiàn)的。

傳統(tǒng)DVFS技術(shù)主要用在CPU節(jié)能，在CPU利用率較低時，通過降低CPU頻率實(shí)現(xiàn)處理器的節(jié)能。隨著研究的深入,DVFS也被用來實(shí)現(xiàn)GPU的節(jié)能。參考文獻(xiàn)[8]就是通過提取軟件特征量優(yōu)化了DVFS的算法，并提出一種CDVFS技術(shù)實(shí)現(xiàn)了GPU節(jié)能。

由物理知識可知，任務(wù)的運(yùn)行時間與運(yùn)行頻率具有反比關(guān)系。所以，在系統(tǒng)的運(yùn)行頻率降低時，功耗降低，但也會使任務(wù)執(zhí)行時間變長。

綜上所述，系統(tǒng)節(jié)能的最終目標(biāo)是尋找頻率的一個平衡區(qū)間，既能保證系統(tǒng)低功耗運(yùn)行，又能使任務(wù)執(zhí)行時間在用戶接受范圍內(nèi)。

結(jié) 語

本文介紹了通用圖形處理器(GPGPU)的體系結(jié)構(gòu)和相關(guān)概念，以及GPGPU線程調(diào)度的方法和功耗節(jié)能方法。這些方法只是在一定程度上解決了通用圖形處理器的相關(guān)問題，提升了并行性能，這樣就導(dǎo)致GPGPU性能還不能完全發(fā)揮出來。

[1] Manyika J,Chui M,Brown B,et al.Big data:The next frontier for innovation,competition,and productivity[EB/OL].[2017-013].http://www.mckinsey.com/insights/business_technology.

[2] 張舒，褚艷利.GPU高性能運(yùn)算之CUDA[M].北京：中國水利水電出版社，2009:27-38.

[3] 何炎祥，張軍，沈凡凡,等.通用圖形處理器線程調(diào)度優(yōu)化方法研究綜述[J].計(jì)算機(jī)學(xué)報，2016,39(9):1733-1749.

[4] Cook S. CUDA 并行程序設(shè)計(jì)：GPU編程指南 [M].蘇統(tǒng)華,李東,李松澤，譯.[J].北京：機(jī)械工業(yè)出版社，2014.

[5] Wu H, Diamos G, Wang J, et al. Characterization and transformation of unstructured control flow in bulk synchronous GPU applications[J]. The International Journal of High Performance Computing Applications,2012,26(2):170-185.

[6] 徐元旭. SIMT 線程調(diào)度模型分析及優(yōu)化[D]. 哈爾濱：哈爾濱工業(yè)大學(xué),2013.

[7] 劉孝伍.面向Linux系統(tǒng)的處理器節(jié)能技術(shù)研究及應(yīng)用[D].成都：四川大學(xué)，2016.

[8] Junke Li A Modeling Approach for Energy Saving Based on GA-BP Neural Network[J].Journal of Electrical Engineering &Technology,2016,11(5):1289-1298.

張鵬博(碩士在讀)，主要研究方向?yàn)榍度胧较到y(tǒng)下的綠色計(jì)算、GPU并行計(jì)算、區(qū)塊鏈溯源;郭兵(教授)，主要研究方向?yàn)榍度胧綄?shí)時系統(tǒng)、綠色計(jì)算、個人大數(shù)據(jù)、區(qū)塊鏈溯源；黃義純、曹亞波(碩士在讀)，主要研究方向?yàn)閭€人大數(shù)據(jù)、區(qū)塊鏈溯源。

Research on Parallel Computing of General Purpose CPGPU

Zhang Pengbo,Guo Bing,Huang Yichun,Cao Yabo

(School of Computer Science and Technology,Sichuan University,Chengdu 610065,China)

The Graphics Processing Unit (GPU) only is been used to the graphics image rendering,so it becomes a parallel computing platform General Purpose GPU(GPGPU),the parallel computing power is growing,and the application is more and more widely.Based on the study of GPGPU architecture,the GPGPU parallel computing thread scheduling is studies,and the principle of GPU thread scheduling and the deficiency of SIMT scheduling mode are introduced.The relationship between system power consumption and system operating frequency is expounded by formula.

big data;parallel computing;thread scheduling;GPU energy saving

國家自然科學(xué)基金重點(diǎn)項(xiàng)目(項(xiàng)目編號：61332001)；國家自然科學(xué)基金資助項(xiàng)目(項(xiàng)目編號：61272104)。

TP302

A

?迪娜

2017-03-24)