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

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

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

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

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

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

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

大數據；并行計算；線程調度；GPU節能

引 言

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

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

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

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

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

1.1 GPGPU線程層級

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

圖1 GPGPU線程結構

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

1.2 GPU宏觀體系結構

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

圖2 GPGPU硬件映射

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

圖3 GPGPU宏觀體系結構

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

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

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

2.1 線程組級別線程調度

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

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

圖4 分支轉移執行圖

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

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

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

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

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

2.2 線程塊級別線程調度

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

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

圖5 SIMT調度圖

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

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

3 通用圖形處理器節能方法

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

動態功耗的計算公式為：

(1)

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

(2)

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

(3)

其中K′為一個常數,若用Wd表示系統的動態能耗，則：

(4)

由數學知識可得到如下公式：

(5)

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

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

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

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

結 語

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

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

[4] Cook S. CUDA 并行程序設計：GPU編程指南 [M].蘇統華,李東,李松澤，譯.[J].北京：機械工業出版社，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 線程調度模型分析及優化[D]. 哈爾濱：哈爾濱工業大學,2013.

[7] 劉孝伍.面向Linux系統的處理器節能技術研究及應用[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.

張鵬博(碩士在讀)，主要研究方向為嵌入式系統下的綠色計算、GPU并行計算、區塊鏈溯源;郭兵(教授)，主要研究方向為嵌入式實時系統、綠色計算、個人大數據、區塊鏈溯源；黃義純、曹亞波(碩士在讀)，主要研究方向為個人大數據、區塊鏈溯源。

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)