基于圖形處理器的STM研究與實(shí)現(xiàn)

梁 飛，胡大裟，蒲亦非

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

胡大裟(1976- )，男(漢族)，四川瀘州人，講師，博士，研究方向：并行計(jì)算、編程語(yǔ)言、軟件工程。

基于圖形處理器的STM研究與實(shí)現(xiàn)

梁 飛，胡大裟，蒲亦非

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

多核處理器和基于圖形處理器通用計(jì)算(GPGPU)的發(fā)展，提出了簡(jiǎn)化并行編程的需求,而軟件事務(wù)存儲(chǔ)(STM)通過(guò)標(biāo)記代碼段并保證其執(zhí)行的原子性為簡(jiǎn)化并行編程提供了很好的選擇。為降低圖形處理器(GPU)并行編程的復(fù)雜性，在分析GPU編程中存在的同步問(wèn)題，結(jié)合統(tǒng)一計(jì)算設(shè)備架構(gòu)(CUDA)的特點(diǎn)以及影響STM重要因素的基礎(chǔ)上，提出在編程環(huán)境中引入STM模型的編程方法，測(cè)試結(jié)果表明相對(duì)基于CPU的計(jì)算依然具有良好的加速比。

圖形處理器；軟件事務(wù)存儲(chǔ)；通用計(jì)算；統(tǒng)一計(jì)算設(shè)備架構(gòu)

圖形處理器(Graphics Processing Unit，GPU)具有高帶寬、強(qiáng)大的浮點(diǎn)處理能力，適合高密度的科學(xué)計(jì)算[1]。隨著GPU可編程性的不斷提高，利用GPU進(jìn)行通用計(jì)算的研究越來(lái)越多，但目前對(duì)GPGPU(General-purpose computing on graphics processing units)的研究大多集中在GPU應(yīng)用程序的開(kāi)發(fā)與優(yōu)化上，對(duì)GPU編程、調(diào)試、容錯(cuò)方面的研究較少，基于GPU編程面臨著開(kāi)發(fā)移植困難、維護(hù)成本高等問(wèn)題，如何開(kāi)發(fā)并行可擴(kuò)展應(yīng)用以充分利用GPU的計(jì)算能力成為一大挑戰(zhàn)[2]。這其中的一個(gè)關(guān)鍵問(wèn)題在于如何簡(jiǎn)化多核平臺(tái)下的開(kāi)發(fā)模型，如何降低復(fù)雜的同步邏輯。

近年來(lái)，事務(wù)存儲(chǔ)[3](Transactional Memory, TM)在多核并行程序開(kāi)發(fā)方面的研究越來(lái)越多，它相對(duì)于鎖機(jī)制的優(yōu)勢(shì)得到更多認(rèn)識(shí)。TM允許開(kāi)發(fā)人員只需標(biāo)記并行代碼段而不用關(guān)注同步邏輯，代碼段并行執(zhí)行的原子性由TM來(lái)保證。本文在GPU編程模型中引入TM以降低并行應(yīng)用開(kāi)發(fā)中的同步邏輯復(fù)雜性，提高基于GPU的通用計(jì)算的可編程性。

1 研究現(xiàn)狀

最初針對(duì)GPU的編程局限于頂點(diǎn)處理器(vertex processor)和像素處理器(fragment processor)提供的有限功能，必須通過(guò)圖形學(xué)的API進(jìn)行調(diào)用。隨后出現(xiàn)了完全可編程像素處理器，并提供偽匯編語(yǔ)言[4]。隨著GPU硬件單元可編程性的不斷提高以及DirectX 9的推出，出現(xiàn)了類C的高級(jí)繪制語(yǔ)言(High-level shading language, HLSL[5])、NVIDIA Cg[6]等，但是依然需要開(kāi)發(fā)人員將計(jì)算任務(wù)映射為對(duì)紋理的渲染過(guò)程，然后通過(guò)編程調(diào)用圖形學(xué)API執(zhí)行計(jì)算。這些編程方式不僅要求開(kāi)發(fā)人員熟悉需要實(shí)現(xiàn)的計(jì)算和并行算法，而且要對(duì)圖形學(xué)硬件和編程接口有深入的了解，難以在普通開(kāi)發(fā)人員中推廣。

為解決繪制語(yǔ)言存在的問(wèn)題，使開(kāi)發(fā)人員在利用GPU計(jì)算的同時(shí)不必考慮GPU的圖形結(jié)構(gòu)，研究人員將GPU的結(jié)構(gòu)納入流處理機(jī)的模型，進(jìn)而實(shí)現(xiàn)以高級(jí)語(yǔ)言編程。BrookGPU[7]是較早致力于將GPU抽象為流處理器，進(jìn)而隱藏圖形學(xué)API實(shí)現(xiàn)細(xì)節(jié)，推動(dòng)基于GPU通用計(jì)算的科研項(xiàng)目。BrookGPU通過(guò)流數(shù)據(jù)類型定義數(shù)據(jù)流，開(kāi)發(fā)人員只關(guān)注計(jì)算數(shù)據(jù)及其上的操作，由BrookGPU編譯器完成從源程序到Cg的編譯工作，然后由GPU廠家提供的Shader程序翻譯為匯編代碼，從而使開(kāi)發(fā)人員從圖形API中脫離出來(lái)。隨后NVIDIA公司借鑒BrookGPU項(xiàng)目理念推出了GPU編程平臺(tái)CUDA(Compute Unified Device Architecture)[8]，NVIDIA CUDA采用類C語(yǔ)言進(jìn)行開(kāi)發(fā)，提供了更高層次的抽象接口，利用CUDA進(jìn)行通用計(jì)算開(kāi)發(fā)完全不需要借助圖形學(xué)API。同時(shí)支持CUDA的GPU采用了統(tǒng)一處理架構(gòu)，并引入片內(nèi)共享存儲(chǔ)器，支持隨機(jī)寫入和線程塊內(nèi)通信，更有利于開(kāi)發(fā)基于GPU的通用計(jì)算應(yīng)用。

為了運(yùn)用CUDA進(jìn)行計(jì)算仍然需要分配管理存儲(chǔ)器、建立啟動(dòng)核運(yùn)算，研究人員設(shè)計(jì)了更抽象的編程語(yǔ)言如PyCUDA[9]、JCUDA[10]等。在PyCUDA中，開(kāi)發(fā)人員使用Python編程，然后由編譯器負(fù)責(zé)生成在GPU上執(zhí)行的CUDA代碼。而JCUDA利用JNI技術(shù)建立Java與CUDA的接口，開(kāi)發(fā)人員可以在Java程序中嵌入CUDA代碼實(shí)現(xiàn)應(yīng)用加速。這些建立在CUDA之上的編程語(yǔ)言，降低了基于CUDA編程的復(fù)雜性，但是并沒(méi)有考慮解決CUDA計(jì)算中的數(shù)據(jù)同步問(wèn)題。

CUDA能夠勝任高度并行的大數(shù)據(jù)量計(jì)算任務(wù)，在線程同步通信方面提供了原子操作和內(nèi)存柵欄，以及線程塊內(nèi)的共享內(nèi)存[11]。在CUDA的編程模型中，線程塊內(nèi)的線程可以使用共享內(nèi)存通信，并由synchronize實(shí)現(xiàn)內(nèi)存柵欄同步，而線程塊之間并不能進(jìn)行通信，只能在全局內(nèi)存中使用原子操作，而對(duì)全局內(nèi)存的同步操作將嚴(yán)重影響計(jì)算性能[12]。在線程塊內(nèi)，基于線程束(wrap)的執(zhí)行機(jī)制也增加了同步的復(fù)雜性，線程束內(nèi)的所有線程執(zhí)行同一個(gè)指令，如果某個(gè)線程因?yàn)橥絾?wèn)題產(chǎn)生等待，就會(huì)導(dǎo)致整個(gè)線程塊陷入忙等狀態(tài)。而基于流的計(jì)算模式在實(shí)現(xiàn)復(fù)雜計(jì)算時(shí)需要多個(gè)流執(zhí)行多個(gè)核(kernel)函數(shù)，以及核函數(shù)的并行，更是給數(shù)據(jù)同步帶來(lái)了難以想象的復(fù)雜性[13]。

2 系統(tǒng)模型及設(shè)計(jì)

為了降低并行編程中同步邏輯的復(fù)雜性，本文在GPU編程模型中引入軟件事務(wù)存儲(chǔ)[14](Software Transactional Memory, STM)，由STM來(lái)保證事務(wù)執(zhí)行的原子性，從而使開(kāi)發(fā)人員從復(fù)雜的同步邏輯中解脫出來(lái)。而CUDA已經(jīng)在各行業(yè)應(yīng)用中表現(xiàn)出優(yōu)異的加速效果，同時(shí)兼容CUDA并且計(jì)算能力2.0以上的GPU已經(jīng)可以支持浮點(diǎn)數(shù)的原子操作，比如CAS(Compare And Swap)操作，可以用來(lái)實(shí)現(xiàn)鎖互斥以及無(wú)鎖(lock free)的數(shù)據(jù)結(jié)構(gòu)[15]，進(jìn)而為在CUDA平臺(tái)上實(shí)現(xiàn)STM提供了基本保障，為此本文選擇在CUDA平臺(tái)基礎(chǔ)上實(shí)現(xiàn)STM。

2.1 CUDA平臺(tái)計(jì)算特點(diǎn)

CUDA是目前基于GPU通用計(jì)算平臺(tái)的杰出代表，由于GPU強(qiáng)大的并行計(jì)算和浮點(diǎn)計(jì)算能力，使得利用CUDA解決以往的復(fù)雜任務(wù)成為可能。從任務(wù)劃分編程來(lái)看，執(zhí)行計(jì)算任務(wù)的內(nèi)核(kernel)被組織成線程塊(block)，線程塊又被組成網(wǎng)格(grid)。同一個(gè)內(nèi)核程序可以并行運(yùn)行在網(wǎng)格中所有線程塊中的線程上，線程塊負(fù)責(zé)執(zhí)行粗粒度的并行任務(wù)，而線程塊內(nèi)的線程可以通過(guò)線程塊內(nèi)的共享內(nèi)存及同步操作協(xié)作完成細(xì)粒度的任務(wù)。從硬件架構(gòu)上來(lái)看，兼容CUDA的GPU采用統(tǒng)一的計(jì)算架構(gòu)，最基本的處理單元是流處理器(Streaming Processor, SP)，多個(gè)SP和寄存器、共享內(nèi)存等組成流多核處理器(Streaming Multiprocessor, SM)，幾個(gè)SM又組成計(jì)算陣列，進(jìn)而從硬件上支持并行任務(wù)的劃分及調(diào)度。從CUDA程序單指令多線程的執(zhí)行模式來(lái)看，每個(gè)SP對(duì)應(yīng)一個(gè)線程，每個(gè)SM對(duì)應(yīng)一個(gè)或多個(gè)線程塊，但SM執(zhí)行計(jì)算時(shí)卻是以wrap為單位而非線程塊，因?yàn)榫€程塊中分配的線程數(shù)可能遠(yuǎn)遠(yuǎn)高于SM中包含的SP數(shù)目，通常wrap由ID連續(xù)的32個(gè)線程組成，執(zhí)行指令時(shí)由調(diào)度器選擇一個(gè)準(zhǔn)備好的wrap執(zhí)行，如果某指令需要等待，SM會(huì)自動(dòng)切換到下一個(gè)wrap塊來(lái)執(zhí)行，以此隱藏線程的延遲和等待達(dá)到大量并行的目的。

無(wú)論從GPU的硬件架構(gòu)還是CUDA程序的執(zhí)行模式來(lái)看，都是為了達(dá)到大量并行計(jì)算的目的，因而GPU通常具有相對(duì)CPU更大的內(nèi)存帶寬，更多的計(jì)算執(zhí)行單元，這是GPU具備大量并行能力及強(qiáng)大的浮點(diǎn)計(jì)算能力的根本，但也同時(shí)帶來(lái)CUDA計(jì)算的缺點(diǎn)，比如對(duì)并行程度不高、具有高度分支的程序運(yùn)行效率較低，即便是對(duì)線程塊內(nèi)共享內(nèi)存的操作，也有可能因?yàn)樵L問(wèn)位置沖突而造成性能的嚴(yán)重下降，同時(shí)只提供了線程同步功能，并不能完全滿足開(kāi)發(fā)人員對(duì)并行編程數(shù)據(jù)同步的需要。

2.2 CUDA STM的策略選擇

從開(kāi)發(fā)人員的角度來(lái)看，STM需要提供以下幾個(gè)基本操作?！癰egin”用來(lái)標(biāo)記一個(gè)事務(wù)的開(kāi)始，“read”從全局內(nèi)存中讀取數(shù)據(jù)，“write”記錄更新的數(shù)據(jù)，最后如果事務(wù)沒(méi)有發(fā)生沖突“commit”操作負(fù)責(zé)將更新的數(shù)據(jù)寫回，否則事務(wù)中斷并伺機(jī)重新執(zhí)行。然而具體到如何實(shí)現(xiàn)這些操作，就必須根據(jù)STM的使用環(huán)境選擇合適的實(shí)現(xiàn)策略，以下將結(jié)合CUDA平臺(tái)架構(gòu)及高并行高密度計(jì)算環(huán)境的特點(diǎn)，從演進(jìn)性、沖突檢測(cè)粒度、沖突檢測(cè)時(shí)間、直寫/回寫方面分析CUDA環(huán)境下STM的設(shè)計(jì)需要關(guān)注的因素。

2.2.1 演進(jìn)性

并發(fā)事務(wù)的演進(jìn)性(Progress Guarantee)分為2種：阻塞和非阻塞[14]。在阻塞方式下，事務(wù)首先要獲取共享對(duì)象的訪問(wèn)權(quán)才能訪問(wèn)共享對(duì)象，而非阻塞方式下檢測(cè)到?jīng)_突的事務(wù)必須有一方放棄。非阻塞方式又分為3種：最嚴(yán)格的是無(wú)等待(wait-freedom)[15-16]，它要求一個(gè)事務(wù)必須在有限的步驟中完成，通常用于實(shí)時(shí)系統(tǒng)中，實(shí)現(xiàn)較為復(fù)雜而且性能偏低；較弱的是無(wú)鎖(lock-freedom)[17]，在此條件下至少有一個(gè)事務(wù)必須在有限的步驟中完成，采用無(wú)鎖方式系統(tǒng)不會(huì)產(chǎn)生死鎖但是有可能出現(xiàn)饑餓現(xiàn)象；要求最弱的是無(wú)干擾[18](obstruction-freedom)，無(wú)干擾環(huán)境下要求沒(méi)有發(fā)生沖突的事務(wù)能夠執(zhí)行成功，而產(chǎn)生沖突的事務(wù)可能會(huì)彼此放棄而導(dǎo)致饑餓，通常依賴沖突管理器來(lái)決定哪個(gè)沖突事務(wù)需要回退。而阻塞方式是基于鎖的實(shí)現(xiàn)，不提供任務(wù)演進(jìn)保證。

鑒于鎖機(jī)制產(chǎn)生的種種問(wèn)題，目前大多數(shù)STM實(shí)現(xiàn)方式是非阻塞的。在3種非阻塞方式中，文獻(xiàn)[19-20]證實(shí)基于無(wú)干擾的實(shí)現(xiàn)方式相對(duì)無(wú)鎖更簡(jiǎn)單，同時(shí)能夠提供更好的并發(fā)性能。而CUDA平臺(tái)的定位是高度并行計(jì)算，對(duì)復(fù)雜的邏輯控制要求較低，因而在CUDA平臺(tái)上構(gòu)建STM時(shí)選擇無(wú)干擾的實(shí)現(xiàn)方式。

2.2.2 沖突檢測(cè)粒度

STM的沖突檢測(cè)粒度分為對(duì)象[20]和字2種?；谧值臋z測(cè)粒度在事務(wù)更新內(nèi)存單元前，首先要通過(guò)原子操作進(jìn)行聲明，告知其他事務(wù)，成功獲取更新內(nèi)存的所有權(quán)后才能進(jìn)行內(nèi)存更新操作，完成后再以原子操作消除聲明，如果獲取所有權(quán)失敗，當(dāng)前事務(wù)就要中斷并消除聲明。而基于對(duì)象的檢測(cè)粒度要求事務(wù)在更新對(duì)象前，由事務(wù)生成對(duì)象的副本，事務(wù)的更新操作在副本上進(jìn)行，在提交階段校驗(yàn)對(duì)象及副本的一致性，獲取對(duì)象的訪問(wèn)權(quán)，然后將副本拷貝到對(duì)象位置。

結(jié)合CUDA的計(jì)算環(huán)境，對(duì)整數(shù)、浮點(diǎn)數(shù)都已提供原子操作[12]，基于字的實(shí)現(xiàn)在更新數(shù)據(jù)前后還要求原子聲明及消除聲明，更增添復(fù)雜性，另外基于GPU的通用計(jì)算中采用C++、Java進(jìn)行編程已是大勢(shì)所趨，應(yīng)用開(kāi)發(fā)中越來(lái)越多的采用動(dòng)態(tài)分配和使用的數(shù)據(jù)結(jié)構(gòu)，因此在CUDA平臺(tái)上構(gòu)建STM時(shí)采用基于對(duì)象的實(shí)現(xiàn)方式。

2.2.3 沖突檢測(cè)時(shí)間

STM的沖突檢測(cè)時(shí)間可分為早檢測(cè)和晚檢測(cè)[20]。早檢測(cè)策略在事務(wù)中產(chǎn)生讀寫操作時(shí)都會(huì)檢測(cè)是否有沖突存在，以此來(lái)保證共享對(duì)象的一致性。晚檢測(cè)是在事務(wù)提交階段才檢測(cè)是否存在沖突事務(wù)，相對(duì)而言，早檢測(cè)可以更及時(shí)地發(fā)現(xiàn)沖突，進(jìn)而避免后續(xù)的不必要計(jì)算，且實(shí)現(xiàn)簡(jiǎn)單，但其開(kāi)銷明顯大于晚檢測(cè)?？紤]到運(yùn)用CUDA加速應(yīng)用的初衷，在引入STM保證事務(wù)執(zhí)行特性的基礎(chǔ)上，盡可能的降低對(duì)CUDA性能的影響，同時(shí)在采用基于對(duì)象的檢測(cè)粒度的前提下，采用晚檢測(cè)策略更為方便。

2.2.4 直寫和回寫

在事務(wù)提交之前通常不知道事務(wù)能否成功提交，為保證事務(wù)執(zhí)行的原子性和一致性，一旦事務(wù)提交失敗就需要撤消事務(wù)做出的更改。我們借鑒數(shù)據(jù)庫(kù)中常采取多版本并發(fā)控制策略(Multi-Version Concurrency Control, MVCC)，在事務(wù)中記錄所有的更改，即第一次讀取對(duì)象時(shí)，就在事務(wù)中創(chuàng)建一個(gè)對(duì)象的副本，隨后的寫操作都在本地副本上進(jìn)行。到事務(wù)提交階段獲取所需的鎖，再將本地副本寫回到全局內(nèi)存，這種方式稱為回寫。另一種更積極的并發(fā)控制策略(Optimistic Concurrency Control, OCC[21])是直接操作共享內(nèi)存寫入更新對(duì)象，如果沒(méi)有沖突產(chǎn)生這種策略效率更高，但也有可能被中斷，同時(shí)需要撤銷日志來(lái)保存最初的對(duì)象。為了保證在引入STM后不帶來(lái)太多的額外開(kāi)銷，以及前面采用基于對(duì)象的實(shí)現(xiàn)方式，構(gòu)建CUDA平臺(tái)上的STM采用回寫方式。

3 實(shí)現(xiàn)

綜合以上構(gòu)建STM的設(shè)計(jì)策略并結(jié)合CUDA計(jì)算平臺(tái)的特點(diǎn)，首先確定STM采用基于無(wú)干擾的實(shí)現(xiàn)方式，相對(duì)于無(wú)等待、無(wú)鎖方式，實(shí)現(xiàn)方式更簡(jiǎn)單同時(shí)提供更好的并發(fā)性能，相對(duì)于阻塞型的實(shí)現(xiàn)方式，可以有效避免鎖機(jī)制帶來(lái)的死鎖等問(wèn)題。同時(shí)考慮到CUDA對(duì)整型、浮點(diǎn)型已提供原子操作，將STM的檢測(cè)粒度定為對(duì)象級(jí)，有利于在計(jì)算中采用更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。此外結(jié)合CUDA環(huán)境下計(jì)算高度并行沖突較低的特點(diǎn)，以及直寫方式可能帶來(lái)的可見(jiàn)性問(wèn)題，基于CUDA的STM實(shí)現(xiàn)采用回寫方式，晚檢測(cè)策略。以下詳細(xì)解析基于CUDA的STM如何實(shí)現(xiàn)4個(gè)基本操作。

圖1 STM事務(wù)描述符

圖2 對(duì)象訪問(wèn)互斥鎖

3.1 Begin

在CUDA環(huán)境中，線程塊作為任務(wù)粗粒度劃分及并行計(jì)算調(diào)度的基本單位，也只有在線程塊內(nèi)才能進(jìn)行線程間的通信同步[12]，因此筆者選擇在線程塊內(nèi)初始化事務(wù)的執(zhí)行環(huán)境，以及事務(wù)的相關(guān)描述配置信息。通過(guò)在線程塊內(nèi)構(gòu)建事務(wù)描述符來(lái)記錄事務(wù)讀寫對(duì)象的位置指針、版本號(hào)等信息。圖1展示了事務(wù)描述符的結(jié)構(gòu)，version是用于MVCC的版本號(hào)，global指針用于指向全局內(nèi)存中要讀寫的數(shù)據(jù)，local指向事務(wù)創(chuàng)建的數(shù)據(jù)副本，布爾型變量update用以指示線程塊內(nèi)的副本是否被更新，如果數(shù)據(jù)副本沒(méi)有更新，在提交階段就不必拷貝回全局內(nèi)存。

3.2 Read

Read操作首先檢測(cè)要讀取的數(shù)據(jù)是否加有排它鎖，以判斷當(dāng)前是否有其他事務(wù)正在更新數(shù)據(jù)。若沒(méi)有則從全局內(nèi)存中讀取對(duì)象并在事務(wù)中創(chuàng)建對(duì)象副本，同時(shí)記錄當(dāng)前對(duì)象的版本號(hào)，并更新事務(wù)描述符中的version字段，將global和local指針?lè)謩e指向全局內(nèi)存中對(duì)象及本地的對(duì)象副本。Read操作將返回指向本地副本的local指針，以便后續(xù)進(jìn)行讀寫操作。用于實(shí)現(xiàn)對(duì)象訪問(wèn)互斥鎖的結(jié)構(gòu)如圖2所示，version代表版本號(hào)，lock代表commit階段獲取對(duì)象寫權(quán)限的鎖，利用CUDA提供的CAS操作可以方便的實(shí)現(xiàn)排它鎖。

3.3 Write

Write操作是在副本上進(jìn)行的更新，因?yàn)閿?shù)據(jù)副本屬于線程私有，所以此階段無(wú)需加鎖。調(diào)用Write操作首先通過(guò)傳入指針參數(shù)查找到要寫入數(shù)據(jù)的位置，然后將傳入的數(shù)據(jù)參數(shù)寫入到副本位置上，同時(shí)將事務(wù)描述符中的布爾變量update設(shè)置為true，以便在Commit階段判斷是否需要將副本寫回到全局內(nèi)存。

3.4 Commit

在Commit階段首先嘗試獲取全局對(duì)象的互斥鎖，成功獲取鎖后比較事務(wù)描述符中版本號(hào)和互斥鎖版本號(hào)是否一致，如果一致則將local指向的對(duì)象副本寫回到global指向的全局內(nèi)存位置，同時(shí)使用原子遞增操作更新互斥鎖的版本號(hào)。如果無(wú)法獲取互斥鎖，或者版本號(hào)匹配不一致，當(dāng)前事務(wù)中斷并重新執(zhí)行，偽代碼如圖3所示。通過(guò)MVCC及互斥鎖機(jī)制，可以保證全局內(nèi)存數(shù)據(jù)的一致性，同時(shí)采用回寫策略避免了數(shù)據(jù)可見(jiàn)性問(wèn)題。

圖3 STM commit

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

表1 CPU、CUDA、CUDA STM下雙調(diào)排序耗時(shí)統(tǒng)計(jì) ms

從表1中可以看出，在CUDA平臺(tái)中引入STM后，確實(shí)帶來(lái)了一定的開(kāi)銷，但從統(tǒng)計(jì)數(shù)據(jù)來(lái)看，隨著數(shù)據(jù)量的增加，帶來(lái)的性能開(kāi)銷呈現(xiàn)明顯的下降趨，相對(duì)基于CPU的排序算法，依然保持著大約4～5倍的加速比。

5 結(jié)語(yǔ)

本文分析了在CUDA環(huán)境下STM的設(shè)計(jì)選擇策略及基本操作的實(shí)現(xiàn)，最后通過(guò)測(cè)試驗(yàn)證了基于GPU平臺(tái)STM的可行性。相對(duì)于CUDA支持整型、浮點(diǎn)的原子操作，引入STM后可以構(gòu)建更復(fù)雜的數(shù)據(jù)類型，并保證其執(zhí)行的原子性，簡(jiǎn)化了編程的同步邏輯。當(dāng)然相對(duì)于功能完善可以提供較復(fù)雜的事務(wù)執(zhí)行配置及動(dòng)態(tài)競(jìng)爭(zhēng)管理策略[23]的STM而言，基于GPU平臺(tái)的STM在性能上還存在一定的差距，但完全適用于GPU計(jì)算數(shù)據(jù)密度大高度并行的計(jì)算環(huán)境，引入STM帶來(lái)的開(kāi)銷完全可以由GPU強(qiáng)大的處理能力和高帶寬來(lái)彌補(bǔ)。相信隨著GPU的不斷完善和STM研究的不斷深入，兩者的結(jié)合必然可以有效推動(dòng)GPGPU的發(fā)展。

[1] 吳恩華.圖形處理器用于通用計(jì)算的技術(shù)、現(xiàn)狀及其挑戰(zhàn)[J].軟件學(xué)報(bào),2004,15(10):1493-1504.

[2] 陳慶奎,王海峰,那麗春,等.圖形處理器通用計(jì)算的研究綜述[J].黑龍江大學(xué)自然科學(xué)學(xué)報(bào),2012,29(5):672-679.

[3] HERLIHY M,MOSS J.Transactional memory:architectural support for lock-free data structures[C]//In Proceedings of the Twentieth Annual International Symposium on Computer Architecture,1993.

[4] LINDHOLM E,KILGARD M,MORETON H.A user-programmable vertex engine[C]//In:Proc.Of the SIGGRAPH,2001:149-158.

[5] PEEPER C,MITCHELL J.Introduction to the directX 9 high-level shader language[J].ShaderX2: Introduction and Tutorials with DirectX, 2003,9.

[6] MARK WR,GLANVILLE S,AKELEY K,et al.Cg:A system for programming graphics hardware in a C-like language[C]//ACM Trans on Graphics(TOG).ACM,2003,22(3):896-907.

[7] BUCK I,FOLEY T,HORN D,et al.Brook for GPUs: Stream computing on graphics hardware[C]//ACM Transaction on Graphics(TOG).ACM, 2004,23(3):777-786.

[8] NVIDIA Corporation.什么是NVIDIA CUDA? 2012[EB/OL].[2010-02-01].http://www.nvidia.cn/object/cuda-cn.html.

[9] KLOCKNER A,Pinto N,LEE Y,et al.PyCUDA:GPU runtime code generation for high performance computing[R].Providence,RI:Brown University,2009.

[10] YAN Y H,GROSSMAN M,SARKAR V.Jcuda:a programmer-friendly interface for accelerating java programs with cuda[C]// Euro-Par’09: Proceedings of the 15th International Euro-Par Conference on Parallel Processing. Berlin Heidelberg: Springer-Verlag, 2009:887-899.

[11] NVIDIA Corporation. CUDA C programming guide, 2012[EB/OL].[2013-02-01].http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html.

[12] 張舒,禇艷利.GPU高性能運(yùn)算之CUDA[M].北京:中國(guó)水利水電出版社,2009.

[13] HOU Q M,ZHOU K,GUO B N.Bsgp:bulk-synchronous GPU programming[C]//SIGRAPH’08: ACM SIGGRAPH 2008 papers.New York:ACM, 2008:1-12.

[14] SHAVIT N,TOUITOU D.Software transactional memory[C]//In PODC’95:Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing .New York,1995:204-213.

[15] DUBLA P,DEBATTISTA L,CHALMERS A.Wait-free shared-memory irradiance cache[C]//In Eurographics Symposium on Parallel Graphics and Visualization,Eurographics,2009,3:57-64.

[16] HERLIHY M.Wait-free synchronization[J].ACM Transactions on Programming Language and System,1991,13(1):124-149.

[17] FRASER K.Practical lock-freedom[D].Thesis:King’s College,University of Cambridge,2003.

[18] HERLIHY K,LUCHANGCO V,MOIR M.Obstruction-free synchronization: double-ended queue as an example[C]//In Proceedings of the 23rd International Conference on Distributed Computing Systems,2003.

[19] HARRIS T,FRASER K.Language support for lightweight transactions[C]//In Proceedings of OOPSLA,2003.

[20] HERLIHY M,LUCHANGCO V,MOIR M,et al.Software transactional memory for dynamic-sized data structures[C]//In Twenty-Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing,2003.

[21] KUNG H,ROBINS J.On optimistic methods for concurrency control[J].ACM Transactions on Database Systems,1981,6(2):213-226.

[22] YE X,FAN D,LIN W,et al.High performance comparison-based sorting algorithm on many-core GPUs[C]//In Proc. Of the 24th International Symposium on Parallel and Distributed Processing (IPDPS).IEEE Computer Society, 2010.

[23] 石東旭.軟件事務(wù)存儲(chǔ)動(dòng)態(tài)競(jìng)爭(zhēng)管理策略[J].軟件導(dǎo)刊,2012,11(4):6-8.

ResearchandImplementationofSoftwareTransactionalMemoryBasedonGraphicsProcessorUnite

LIANGFei,HUDasha,PUYifei

(College of Computer Science，Sichuan University，Chengdu 610065，China)

The development of multi-core processor and GPGPU (general purpose computing on graphics processors) creates a demand for ease of parallelization. STM (Software transactional memory) provides a good choice to simplify the development of concurrent code by allowing the programmer to mark sections of code to be executed atomically. To simplify the relatively complex of parallel programming on GPU (Graphics Processing Unit), synchronization problems of GPU programming are analyzed. Based on the comprehensive consideration of significant factors of STM and characteristics of CUDA (Compute Unified Device Architecture), the introduction of STM in GPU programming environment is proposed and the test results show that speedup ratio sustains well by comparison with computing on CPU.

GPU; STM; GPGPU; CUDA

2013-02-19

國(guó)家自然科學(xué)基金“分?jǐn)?shù)階微積分應(yīng)用于醫(yī)學(xué)核磁共振圖像處理的理論與技術(shù)”(60972131)

梁飛(1987- ),男(漢族),河南駐馬店人，在讀碩士研究生,研究方向：數(shù)據(jù)庫(kù)與信息系統(tǒng)。

TP334.7

A

2095-5383(2013)02-0013-05