梁 飛，胡大裟，蒲亦非

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

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

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

梁 飛，胡大裟，蒲亦非

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

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

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

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

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

1 研究現(xiàn)狀

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

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

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

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

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

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

2.1 CUDA平臺計算特點

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

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

2.2 CUDA STM的策略選擇

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

2.2.1 演進性

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

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

2.2.2 沖突檢測粒度

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

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

2.2.3 沖突檢測時間

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

2.2.4 直寫和回寫

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

3 實現(xiàn)

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

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

圖2 對象訪問互斥鎖

3.1 Begin

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

3.2 Read

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

3.3 Write

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

3.4 Commit

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

圖3 STM commit

4 實驗結(jié)果與分析

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

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

5 結(jié)語

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

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

[2] 陳慶奎,王海峰,那麗春,等.圖形處理器通用計算的研究綜述[J].黑龍江大學(xué)自然科學(xué)學(xué)報,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高性能運算之CUDA[M].北京:中國水利水電出版社,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ù)存儲動態(tài)競爭管理策略[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

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

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

TP334.7

A

2095-5383(2013)02-0013-05