利用訪存模式構(gòu)建GPU高效率數(shù)據(jù)訪問

張 瑞，田 密

(1.延安大學(xué)教育科學(xué)學(xué)院，陜西延安716000；2.北京理工大學(xué)計算機(jī)學(xué)院，北京100081；3.延安職業(yè)技術(shù)學(xué)院網(wǎng)絡(luò)信息中心，陜西延安716000)

計算機(jī)性能的提升越來越受制于頻率墻、功耗墻和存儲墻等因素，因此業(yè)界認(rèn)為增加計算資源比單純地提高時鐘頻率能夠帶來更大的性能提升[1]，GPU的高并行性正符合這一需求。GPU以及與其匹配的通用編程語言的發(fā)展使其成為數(shù)據(jù)并行和計算密集應(yīng)用的理想平臺之一并在通用計算領(lǐng)域發(fā)揮越來越重要的作用[2-4]。GPU采用同時執(zhí)行大量線程的方式隱藏訪問存儲器帶來的延遲，但是大量線程同時訪存會引發(fā)訪問延遲而導(dǎo)致線程數(shù)據(jù)饑餓，從而浪費(fèi)GPU的計算資源。GPU訪存系統(tǒng)效率主要受GPU硬件性能制約以及應(yīng)用程序的訪存模式影響[5]。因此為了使應(yīng)用程序能夠充分發(fā)揮GPU體系結(jié)構(gòu)的計算潛能，非常有必要對應(yīng)用程序的訪存模式進(jìn)行分析并結(jié)合GPU的存儲器件特性探索提高訪存系統(tǒng)效率的技術(shù)。

1 相關(guān)工作

目前國內(nèi)外對GPU訪存系統(tǒng)的研究已取得一些研究成果。研究表明GPU系統(tǒng)總體性能與訪存系統(tǒng)效率密切相關(guān)，因此存儲子系統(tǒng)是影響GPU性能的一個非常關(guān)鍵的因素[6]。

Govindaraju等[7]提出了一種基于GPU紋理硬件的存儲模型，該模型采用分塊訪問的方法利用數(shù)據(jù)的局部性特性，不足在于分塊帶來計算開銷的增加從而引起新的性能瓶頸。Fatahalian等[8]分析了GPU上的訪存與計算的供求關(guān)系，得出GPU存儲系統(tǒng)帶寬對計算的性能至關(guān)重要的結(jié)論。Silberstein等[9]針對存儲受限應(yīng)用實(shí)現(xiàn)了片上scratchpad memory的數(shù)據(jù)重用，但是不適合對存儲資源(如寄存器)需求較大的應(yīng)用。Ryoo等[10]針對計算受限應(yīng)用定義了GPU效率和利用率模型，通過對優(yōu)化空間的裁剪來獲得應(yīng)用程序的最優(yōu)配置。Baskaran等[11]針對CUDA平臺利用多面體模型對循環(huán)嵌套結(jié)構(gòu)進(jìn)行優(yōu)化進(jìn)而提高全局存儲器的訪存效率。Ueng等[12]同樣針對CUDA平臺，提出CUDA-Lite實(shí)現(xiàn)程序的存儲優(yōu)化，該方法在源程序中加入注釋以實(shí)現(xiàn)對全局存儲器的聯(lián)合訪問。Jang等[13]提出多層嵌套循環(huán)結(jié)構(gòu)內(nèi)存訪問模型，在該模型指導(dǎo)下分別針對AMD和NVIDIA GPU進(jìn)行全局內(nèi)存向量化和分類存儲取得較高的性能提升，缺陷是耗費(fèi)較多的片外存儲且在對數(shù)組進(jìn)行讀寫交替操作時，帶來數(shù)據(jù)的一致性問題。Stuart等[14]提出RSVM動態(tài)創(chuàng)建和管理大小靈活的數(shù)據(jù)區(qū)域，解決了靜態(tài)內(nèi)存需求較大的應(yīng)用程序的運(yùn)行問題，缺陷是對于不同的應(yīng)用程序數(shù)據(jù)區(qū)域大小的設(shè)定是需要多次實(shí)驗(yàn)才能取得最好性能。

Cope等[15]對GPU硬件進(jìn)行了改進(jìn)，即在GPU中加入可重構(gòu)地址映射硬件邏輯，主要針對視頻處理領(lǐng)域的數(shù)據(jù)訪存優(yōu)化，因而其局限性有兩個方面，一是基于硬件的實(shí)現(xiàn)缺少靈活性，二是只適用領(lǐng)域局限在視頻處理，無法適用在通用計算中。Kim等[16]提出GPUdmm(Dynamic GPU Memory Management)，主要思想是利用顯存先天的數(shù)據(jù)局部性高的特點(diǎn)，通過修改GPU存儲控制器，對DRAM進(jìn)行兩級控制，將顯存看作主存到CU之間的最低級cache以提供給程序員一個面向主存大小的編程視圖，減輕了程序員因?yàn)轱@存容量限制手動劃分?jǐn)?shù)據(jù)，修改kernel的負(fù)擔(dān)，同時避免了因數(shù)據(jù)劃分導(dǎo)致的多余CPU-GPU間的數(shù)據(jù)傳輸。

2 GPU訪存子系統(tǒng)

為了滿足GPU架構(gòu)的高并行性要求，GPU訪存子系統(tǒng)的設(shè)計以高帶寬，低延遲為特征。大部分的GPU內(nèi)存子系統(tǒng)由多種不同訪存延遲的存儲器組成，可以分成片上存儲和片外存儲兩部分，見圖1。

圖1 GPU訪存子系統(tǒng)

片上存儲包含caches，軟件可管理的本地數(shù)據(jù)共享存儲(如scratchpad memory)以及寄存器等。一般而言組成GPU的每個流多處理器(如NVIDIA的SM，AMD的SIMD引擎)都有自己的L1cache和本地共享存儲器，這些存儲器對其他流多處理器透明。本地共享存儲器主要用作存放線程塊內(nèi)的共享數(shù)據(jù)和重用數(shù)據(jù)以減少對片外存儲器的訪問次數(shù)，它一般被分為多個組，即bank結(jié)構(gòu)，連續(xù)的數(shù)據(jù)存儲在相鄰的bank中，線程塊內(nèi)的所有線程可以通過它通信，帶寬高，訪存延遲略大于寄存器但遠(yuǎn)小于片外存儲器。寄存器屬于線程私有，訪問速度非?？?，延遲可忽略，當(dāng)容量不足時借用片外存儲器空間充當(dāng)，這時訪問延遲相當(dāng)于片外存儲器。GPU的緩存一般由兩級構(gòu)成，每個流多處理器擁有屬于自己的L1 cache，所有的流多處理器共享L2 cache。

片外存儲一般有全局存儲，常量存儲和紋理存儲組成，通常共享顯存容量。片外存儲器訪問延遲比較大，一般在幾百個時鐘周期。受顯存控制器影響，需要按照一定方式訪存才能夠取得較高的帶寬，在計算能力比較強(qiáng)的產(chǎn)品上具有cache機(jī)制提高訪存效率。

3 基于訪存模式的高效率數(shù)據(jù)訪問

GPU采用SIMD或SIMT的方式并行處理大量數(shù)據(jù)集，創(chuàng)建和切換線程完全由硬件自動完成，當(dāng)線程數(shù)據(jù)饑餓，硬件會自動調(diào)度其他線程運(yùn)行，因此理論上當(dāng)硬件自動調(diào)度多線程時可以隱藏訪存延遲，但是當(dāng)大量線程數(shù)據(jù)饑餓時，計算資源多處于空轉(zhuǎn)狀態(tài)得不到充分利用。因此當(dāng)應(yīng)用程序移植到GPU平臺上時，非常必要對其數(shù)據(jù)訪問的模式和特性進(jìn)行分析并利用數(shù)據(jù)訪問優(yōu)化技術(shù)避免重復(fù)訪問或減少訪問延遲盡可能地確?；顒泳€程的數(shù)據(jù)供給。

3.1 數(shù)組訪存模式

程序的訪存模式是程序在訪問存儲器件時所體現(xiàn)出來的規(guī)律[17]。通過對應(yīng)用程序進(jìn)行分析可以得出其訪存模式的形式化表達(dá)。數(shù)組是科學(xué)計算中使用最頻繁的數(shù)據(jù)結(jié)構(gòu)，其訪問方式分規(guī)則和不規(guī)則兩類，以二維數(shù)組A[N][N]數(shù)據(jù)訪問為例，存在如圖2(a)所示的多種常見的訪問方式。將圖2(a)中的數(shù)組訪問方式進(jìn)行組合變換可得出數(shù)組訪問的各種情況，并可借鑒多面體模型的概念做抽象化的表示。

多面體模型是一種通過迭代域、訪問函數(shù)和仿射調(diào)度三種操作表示程序的代數(shù)框架，可用于處理具有仿射數(shù)組訪問和循環(huán)邊界的循環(huán)結(jié)構(gòu)。假設(shè)程序循環(huán)邊界和數(shù)組訪問與循環(huán)索引和全局參數(shù)存在映射關(guān)系，那么一個n重嵌套循環(huán)就定義了一個n維空間里的迭代空間多面體，可以表示為

其中DS表示循環(huán)邊界限制，一般為常數(shù)矩陣；xs表示外層到內(nèi)層的循環(huán)迭代向量；n表示全局參數(shù)，如問題規(guī)模。一個以數(shù)組操作為循環(huán)體的D層嵌套循環(huán)S即定義了一個在D維空間里的多面體，多面體里的每個點(diǎn)代表一個數(shù)組元素，多面體的子空間代表數(shù)組的非空子集，那么循環(huán)體對一個數(shù)組的訪問函數(shù)可以用齊次方程表示。循環(huán)體S對數(shù)組A的訪問可以表示為：

FA表示對數(shù)組A的訪問矩陣，F(xiàn)A的行數(shù)由數(shù)組A的維數(shù)決定，F(xiàn)A的列數(shù)由對數(shù)組訪問的迭代空間維數(shù)決定，因此有圖2(b)即為圖2(a)中迭代循環(huán)對數(shù)組A的訪問矩陣。如對一個二維數(shù)組A[10][10]進(jìn)行元素的按行優(yōu)先遍歷訪問，那么數(shù)組A的訪問矩陣FA可以表示為：

其中FA的第一行第一列的1表示對A按行優(yōu)先訪問，且從下標(biāo)為0的行開始訪問，第一行第四列的0表示從行下標(biāo)為0的元素開始由小到大的順序訪問，第二行第二列的1表示從下標(biāo)為0的列開始訪問，第二行第四列的0表示從列下標(biāo)為0的元素開始由小到大順序訪問，如遇到負(fù)數(shù)則表示下標(biāo)由大到小的順序訪問。

(a)行主遍歷 (b)列主遍歷

(c)偏移 (d)行主列逆向

(e)三角訪問 (f)跳躍訪問

(b)

3.2 應(yīng)用程序數(shù)據(jù)的訪存模式分析

訪存優(yōu)化技術(shù)作為緩解存儲墻問題的有效手段，可以分為三類：避免存儲訪問延遲、減少冗余訪問和隱藏存儲訪問延遲。三者都可以提高訪存系統(tǒng)性能，但是有本質(zhì)的區(qū)別。避免存儲訪問延遲是通過對數(shù)據(jù)的重新組織改善數(shù)據(jù)局部性以減少訪存開銷。減少冗余訪問是通過對迭代循環(huán)程序訪問模式的分析重新構(gòu)造循環(huán)空間以去掉對數(shù)據(jù)的冗余訪問。隱藏存儲訪問延遲時通過將訪存和計算重疊進(jìn)行以隱藏訪存延遲，既不減少訪存次數(shù)也沒有減少訪存延遲。本文提出的優(yōu)化方法是通過減少冗余訪問提高訪問的效率。

圖3 迭代循環(huán)示例

利用多面體模型對迭代循環(huán)程序數(shù)據(jù)訪問模式進(jìn)行形式化表達(dá)，可得到數(shù)據(jù)的訪存矩陣，通過將訪存矩陣的秩與循環(huán)迭代空間的維數(shù)進(jìn)行對比可以得出該數(shù)組是否存在迭代循環(huán)里的重復(fù)訪問，如果存在數(shù)組的重復(fù)訪問則結(jié)合GPU存儲系統(tǒng)特性重新構(gòu)造程序的迭代空間減少對全局存儲的訪存次數(shù)從而達(dá)到不影響程序性能卻提高訪存效率的目的。以圖3中的迭代循環(huán)為例，其構(gòu)成的迭代空間可以用S矩陣表示，

數(shù)組A、B、C的訪問矩陣分別為：

R(X)表示矩陣X的秩，由矩陣秩的概念可得

R(S)=3，R(FA)=2，R(FB)=2，R(FC)=2，

可得到：

R(A)

根據(jù)多面體模型的理論，如果一個數(shù)組的訪問矩陣的秩小于訪問該數(shù)組的迭代空間的維數(shù)，那么該數(shù)組在此迭代空間中存在重復(fù)訪問。在迭代空間S上，即數(shù)組A，B，C在迭代循環(huán)中存在重復(fù)訪問，因此可以通過構(gòu)造新的迭代空間并創(chuàng)建能夠被快速訪問的臨時變量，從而將對原數(shù)據(jù)的訪問替換為對臨時變量的訪問。注意存儲臨時變量的存儲器的訪問代價一定要小于存放原數(shù)組數(shù)據(jù)存儲器的訪問代價。一般CPU-GPU結(jié)構(gòu)中，數(shù)據(jù)通過PCIE總線從主機(jī)端到設(shè)備端后都存放在片外存儲中，論文第2節(jié)提到GPU訪存子系統(tǒng)上的寄存器和片上共享存儲都有高于片外存儲器的特性，那么符合上面存放臨時變量的條件，所以通過合理的存儲器使用可以減少數(shù)據(jù)的訪存延遲。在上例中對數(shù)組A、B、C的訪問都存在重復(fù)性，是否存在新的迭代循環(huán)可以一并消除三者的片外重復(fù)訪問呢？通過對三個訪問矩陣的比較得出結(jié)論，因?yàn)镕A，F(xiàn)B，F(xiàn)C任意兩個訪問矩陣之間不存在相似關(guān)系，因此不存在可以同時消除三者重復(fù)訪問的迭代循環(huán)，但是FA與FC，F(xiàn)B與FC存在相同的行向量，因此可以采用消除FA或FB片外重復(fù)訪問的方法減少訪存延遲。

3.3 基于訪存模式的高效率數(shù)據(jù)布局算法

通過上面對應(yīng)用程序數(shù)據(jù)訪存模式的分析，結(jié)合GPU訪存子系統(tǒng)的特點(diǎn)提出以下基于訪存模式的高效率數(shù)據(jù)布局算法(Data Placement Based on Memory Access Patterns)。

算法：DPoMAP

輸入：平臺類型，程序迭代空間維數(shù)D，數(shù)組個數(shù)n，數(shù)組迭代矩陣F[n]，迭代矩陣的秩R[n]，ArraySize[n][2]，寄存器文件個數(shù)RF，片上共享存儲容量SM，

輸出：各個數(shù)組的內(nèi)存位置Placement[n]

Placement[n]<—0；

SM_Occupancy=0；

RF_Occupancy=0；

For(i=0；i

{

If平臺==NVIDIA

{

If F[i]行重用&&SM_Occupancy

{Placement[i]=1；行取到片上共享存儲

SM_Occupancy=SM_Occupancy+

ArraySize[i][0]；

}

Else

{

If F[i]列重用&&SM_Occupancy

{Placement[i]=11；列取到片上共享存儲

SM_Occupancy=SM_Occupancy+

ArraySize[i][1]；

}

Else Placement[i]=2；2表示寄存器

}

}

If平臺==AMD

{If F[i]列重用&&SM_Occupancy

{Placement[i]=11；列取到片上共享存儲

SM_Occupancy=SM_Occupancy+

ArraySize[i][1]；

}

Else

If SM_Occupancy

}

}

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)的硬件平臺基于CPU+GPU結(jié)構(gòu)，其中CPU采用Inteli7系列8核心、主頻為2.8GHZ的處理器，內(nèi)存為2G，GPU采用AMD和NVIDIA兩個主流廠商的兩款同性能等級的產(chǎn)品Caicos R5200 Series和GeForce GTS250，具體參數(shù)見表1，二者均支持基于OpenCL的開發(fā)，硬件之上運(yùn)行著兩個型號GPU對應(yīng)的最新版本驅(qū)動程序。鑒于實(shí)驗(yàn)跨AMD和NVIDIA兩個GPU兩個平臺，因此實(shí)驗(yàn)采用開放的并支持異構(gòu)系統(tǒng)平臺的開放計算語言O(shè)penCL[18]。實(shí)驗(yàn)選取廣泛存在于多個高性能測試集Rodinia、SPEC、NVIDIA OpenCL SDK和AMD OpenCL SDK的被廣泛使用的矩陣乘法作為優(yōu)化對象，為了驗(yàn)證EAoMAP算法的有效性以及方便對比，共計入Original、AL、BL、ALCL、ALBP、APBL和ALBL 7個不同的內(nèi)核(內(nèi)核代表的含義見表2)并分別在AMD和NVIDIA平臺上進(jìn)行了測試，結(jié)果見圖4和圖5，因?yàn)镺riginal內(nèi)核的加速比為1，所以在圖中沒有劃出。

表1 實(shí)驗(yàn)平臺參數(shù)

表2 內(nèi)核含義

4.1 AMD GPU上的訪存優(yōu)化測試

在AMD GPU分別對設(shè)計的7個內(nèi)核采用7個不同大小的數(shù)據(jù)集進(jìn)行測試，分別是64*64，128*128，265*256，512*512，640*640，768*768，832*832，目的是為了觀察同一個內(nèi)核程序在不同數(shù)據(jù)量上的性能表現(xiàn)。

圖4 優(yōu)化策略在Caicos R5200上的效果

從圖4中可以看出在AMD GPU上消除重復(fù)的片外訪問取得明顯的程序加速，最高達(dá)到8x，見上圖4中matrixsize取768時，BL和ALBL加速比。AL中，將A數(shù)組的一行存儲到local memory減少了重復(fù)的global memory訪問，縮短了數(shù)組A的load時間以取得訪存性能提升，然而與BL相比較，加速效果明顯較差，因?yàn)槌瞬僮髦袑?yīng)的兩個操作數(shù)同時load成功，乘法操作指令才能執(zhí)行，BL中將數(shù)組B的一列存放于local memory，減少數(shù)組B對global memory的重復(fù)訪問，因?yàn)樵绦驅(qū)?shù)組B的訪問是列序進(jìn)行，即圖2(b)中的(b)類型，屬于物理上的不連續(xù)訪問，訪存性能很低，因而采用BL優(yōu)化后取得了比AL更高的性能提升。ALCL相比AL只有平均2%的性能提升，其原因在于在對數(shù)組C的訪問密度相較于處理器的計算密度屬于非密集，此時程序的性能主要由計算操作決定，因而即使提高了訪存的性能，程序總體性能提升卻并不明顯。ALBP相較于AL平均有近25%的性能下降，這與AMD架構(gòu)及其wave的組織策略相關(guān)，AMD架構(gòu)規(guī)定每個CU上的最大wave數(shù)，但是在實(shí)際運(yùn)行時，如果每個線程占用的寄存器空間較多，那么會導(dǎo)致分配在CU上的wave量減少從而降低處理核的利用效率。APBL相較于BL平均有近51%的性能下降，原因同ALBP。ALBL相較于AL有近77%的性能提升，相較于BL有8%的性能提升?？傮w而言，對于AMD架構(gòu)，數(shù)據(jù)的非連續(xù)性訪問明顯降低系統(tǒng)效率，因而充分合理利用LDS(Local Data Share)器件對性能提升助益顯著。

4.2 NVIDIA GPU上的訪存優(yōu)化測試

在NVIDIA GPU上同樣對設(shè)計的7個內(nèi)核采用與AMD GPU上相同大小的7個數(shù)據(jù)集進(jìn)行測試以觀察NVIDIA GPU上同一個內(nèi)核程序在不同數(shù)據(jù)量上的性能表現(xiàn)。

圖5 優(yōu)化策略在GeForce GTS250上的效果

從圖5中可以看出在NVIDIA GPU上消除重復(fù)的片外訪問同樣取得明顯的程序加速，最高達(dá)到9x，見圖5中matrixsize取640時ALBL的加速比。就AL和BL而言，將A數(shù)組的一行存儲到shared memory或?qū)?shù)組B的一列存放于shared memory，兩種策略都減少了重復(fù)的global memory訪問，縮短了數(shù)組A或B的load時間而取得訪存性能提升，平均取得2x的加速效果，與AMD架構(gòu)不同的是，N卡的AL與BL加速效果區(qū)別微小，源于N卡數(shù)據(jù)訪問非向量化的機(jī)制，數(shù)組B的列數(shù)據(jù)訪問對系統(tǒng)性能的影響力遠(yuǎn)小于AMD架構(gòu)。ALCL相比AL幾乎沒有性能提升，此處原因同AMD架構(gòu)。ALBP和APBL相較于AL和BL平均有近138%的性能提升，同時ALBL平均有212%的性能提升，這個結(jié)果與AMD架構(gòu)完全不同，在后三者中，矩陣相乘的兩個操作數(shù)同時通過shared memory和寄存器批量存儲，有效避免對同一數(shù)據(jù)反復(fù)地片外訪問，較大地減少了操作數(shù)的load時間。需要注意的是以上兩個圖中當(dāng)矩陣比較小時(如圖4和5中Matrixsize<128，Matrixsize為二維方陣的單維大小)，ALBP和APBL兩個內(nèi)核效率不提升反而降低，尤其當(dāng)Matrixsize=64，效率下降為AL的1/3不到，原因是當(dāng)矩陣比較小時，程序總體開銷比較小，數(shù)據(jù)訪存優(yōu)化帶來的額外開銷相比總體開銷訪存開銷較大，因而導(dǎo)致系統(tǒng)性能不升反降。

4.3 NVIDIA GPU和AMD GPU加速率效果對比

針對NVIDIA GPU和AMD GPU，分別求出六種優(yōu)化策略的平均加速比，如圖6所示，從中可以看出NVIDIA GPU和AMD GPU的訪存優(yōu)化特征顯然不同，因此在選擇訪存優(yōu)化策略時，一定要考慮程序運(yùn)行的平臺因素，選擇適合平臺特性的訪存優(yōu)化策略，才能取得理想的加速效果。

圖6 NVIDIA GPU和AMD GPU加速率效果對比

5 結(jié)論

GPU的高性能的確保需要處理核的高速運(yùn)轉(zhuǎn)和數(shù)據(jù)的及時充足供給，因此對于一些數(shù)據(jù)訪問相對密集的應(yīng)用，其數(shù)據(jù)訪存成為性能瓶頸，提高其數(shù)據(jù)訪問效率對提升系統(tǒng)性能至關(guān)重要。本文借助多面體模型理論，在對應(yīng)用程序訪存模式分析的基礎(chǔ)上提出的多個提高數(shù)據(jù)訪問效率的策略在NVIDIA和AMD GPU上最高取得9倍于原程序的加速效果，一方面說明了優(yōu)化策略的有效性，另一方面進(jìn)一步證明訪存效率的確是影響GPU高性能發(fā)揮的重要因素。由于不同架構(gòu)GPU訪存特性的不同，同一優(yōu)化策略會有差異懸殊的效果，那么在實(shí)際中應(yīng)該根據(jù)平臺選擇適合的優(yōu)化策略。