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

(四川大學 計算機學院，成都 610065)

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

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

(四川大學 計算機學院，成都 610065)

隨著圖形處理器(GPU)從僅用來進行圖形圖像渲染，脫離成為并行計算平臺通用圖形處理器(GPGPU)，其計算能力越來越強，本文在研究GPGPU體系結構的基礎上對GPGPU并行計算線程調度進行深入研究，闡述了GPU線程調度原理，揭示了SIMT調度模式的不足。通過公式推導闡述了系統(tǒng)功耗與系統(tǒng)運行頻率的關系。

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

引 言

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

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

傳統(tǒng)并行調度模式主要分為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í)行模式，但為了獲得更高的并行計算效率，主流的圖形處理器又派生出單指令多線程(Single Instruction Multiple Thread SIMT)模式。

1 通用圖形處理器體系結構及相關概念

目前市場上通用圖形處理器廠商主要有(英偉達NVIDIA)、AMD、英特爾(Intel)三大廠商，其產品在宏觀結構上沒有太大差別,但在微觀體系結構上各有特點。因為NVIDIA公司的通用圖形處理器市場占有率比較高，所以本文關于GPU的論述皆以NVIDIA的產品為標準。

1.1 GPGPU線程層級

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

圖1 GPGPU線程結構

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

1.2 GPU宏觀體系結構

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

圖2 GPGPU硬件映射

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

圖3 GPGPU宏觀體系結構

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

2 通用圖形處理器線程調度方法

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

2.1 線程組級別線程調度

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

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

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

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

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

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

因為通用圖形處理器最小的執(zhí)行單位是warp，所以如果warp內不同線程的循環(huán)次數(shù)不同，就會產生另一種分支情況，并且warp的執(zhí)行時間是循環(huán)次數(shù)最多的那個線程所花費的時間。

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

2.2 線程塊級別線程調度

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

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

圖5 SIMT調度圖

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

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

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

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

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

(1)

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

(2)

由于設計的電路中，頻率和電壓具有線性關系，所以上述公式進一步簡化為：

(3)

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

(4)

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

(5)

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

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

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

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

結 語

本文介紹了通用圖形處理器(GPGPU)的體系結構和相關概念，以及GPGPU線程調度的方法和功耗節(jié)能方法。這些方法只是在一定程度上解決了通用圖形處理器的相關問題，提升了并行性能，這樣就導致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高性能運算之CUDA[M].北京：中國水利水電出版社，2009:27-38.

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

[4] Cook S. CUDA 并行程序設計：GPU編程指南 [M].蘇統(tǒng)華,李東,李松澤，譯.[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 線程調度模型分析及優(yōu)化[D]. 哈爾濱：哈爾濱工業(yè)大學,2013.

[7] 劉孝伍.面向Linux系統(tǒng)的處理器節(jié)能技術研究及應用[D].成都：四川大學，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.

張鵬博(碩士在讀)，主要研究方向為嵌入式系統(tǒng)下的綠色計算、GPU并行計算、區(qū)塊鏈溯源;郭兵(教授)，主要研究方向為嵌入式實時系統(tǒng)、綠色計算、個人大數(shù)據(jù)、區(qū)塊鏈溯源；黃義純、曹亞波(碩士在讀)，主要研究方向為個人大數(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

國家自然科學基金重點項目(項目編號：61332001)；國家自然科學基金資助項目(項目編號：61272104)。

TP302

A

?迪娜

2017-03-24)