基于gpu的并行優(yōu)化技術(shù)

《基于gpu的并行優(yōu)化技術(shù)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、萬方數(shù)據(jù)第26卷第11期2009年11月計算機(jī)應(yīng)用研究ApplicationResearchofComputersV01．26No．11NoV．2009基于GPU的并行優(yōu)化技術(shù)左顥睿1’2，張啟衡1，徐勇1’2，趙汝進(jìn)1’2(1．中國科學(xué)院光電技術(shù)研究所，成都610209；2．中國科學(xué)院研究生院，北京100039)摘要：針對標(biāo)準(zhǔn)并行算法難以在圖形處理器(GPU)上高效運行的問題，以累加和算法為例，基于Nvidia公司統(tǒng)一計算設(shè)備架構(gòu)(CUDA)GPU介紹了指令優(yōu)化、共享緩存沖突避免、解循環(huán)優(yōu)化和線程過載優(yōu)化四種優(yōu)化方法。實驗結(jié)果表明，并行優(yōu)化能有效提

2、高算法在GPU上的執(zhí)行效率，優(yōu)化后累加和算法的運算速度相比標(biāo)準(zhǔn)并行算法提高了約34倍。相比CPU串行實現(xiàn)提高了約70倍。關(guān)鍵詞：圖形處理器；并行優(yōu)化；累加和；統(tǒng)一計算設(shè)備架構(gòu)中圖分類號：TP391；TP311文獻(xiàn)標(biāo)志碼：A文章編號：1001-3695(2009)11—4115．04doi：10．3969／j．issn．1001-3695．2009．11．034．ParalleloptimizetechnologybasedonGPUZUOHao-ruil”，ZHANGQi-hen91，XUYon91”，ZHAORu-jinl’2(1．Institut

3、eofoptics&Electronics，ChineseAcademyofSciences，Chengdu610209，China；2．GraduateSchool。ChineseAcademyof&拋，B4／i增100039，China)Abstract：StandardparallelalgorithmcannotworkefficientlyonGPU．Thispapertookreductionalgorithmforexample，intro—ducedfourparalleloptimamethodsforNVIDIA’Sgraphic

4、sprocessorunit(GPU)whichsupportedCUDAarchitecture．Thesemethodsincludedinstructionoptimizeandsharedmemoryconflictavoidandloopunrollandthreadsoverloadoptimize．Theex-perimentresultshowsthat：paralleloptimizecansignificantlyspeeduptheGPUcomputespeed．Theoptimizedreductionalgo-rithmis

5、34timesfasterthanstandardparallelalgorithmand70timesthanCPU—basedimplementation．Keywords：graphicsprocessorunit(GPU)；paralleloptimize；reduction；computeunifieddevicearchitecture(CUDA)隨著GPU技術(shù)的快速發(fā)展，當(dāng)前的GPU已經(jīng)具有很強(qiáng)的并行計算能力，浮點運算能力甚至可以達(dá)到同代CPU的10倍以上?。同時，隨著Nvidia公司的CUDA(統(tǒng)一計算設(shè)備架構(gòu))的推出，使得GPU具有

6、更好的可編程性，因此在諸如物理系統(tǒng)模擬心j】、金融建模H’51以及地球表面測繪哺1等通用計算領(lǐng)域有著廣泛的應(yīng)用。如何充分利用GPU的并行計算特點實現(xiàn)一些復(fù)雜運算的快速求解，已經(jīng)成為當(dāng)今的熱點問題之一。GPU具有獨特的硬件結(jié)構(gòu)，采用常規(guī)并行算法，很難發(fā)揮GPU的運算優(yōu)勢，通常需要結(jié)合GPU的硬件特點和算法的可并行性，才能有效提高GPU的計算效率¨’8o。本文以具有代表性的累加和算法在GPU上的優(yōu)化實現(xiàn)為例介紹基于GPU的并行優(yōu)化技術(shù)。1累加和算法及其并行實現(xiàn)已知數(shù)組名[n]，累加和算法公式為nsum=．Xx[k](1)E=u累加和算法對r／,個元素進(jìn)行

7、加法運算，不論采用串行還是并行算法，均需要執(zhí)行／-t一1次運算。GPU是基于SIMD架構(gòu)的并行處理器，因此累加和運算可以采用樹型計算將串行運算改寫為并行運算舊J，樹型算法示意圖如圖1所示。圖l樹型算法示意圖從圖1中可以看到，采用樹型結(jié)構(gòu)將累加和運算分為s層(s=l092n)，對第k層需要進(jìn)行n／2‘次運算，每一層內(nèi)的運算可以并行，層與層之間的計算只能串行。代碼1給出了常見并行累加和算法的偽代碼：代碼1／／聲明共享緩存sdata(DSharedsdata[]；／／并行讀取數(shù)據(jù)，tid為線程序號。i為數(shù)組下標(biāo)／／g__idata和g_odata分別是輸入

8、輸出數(shù)組蓬)parallel：sdata[tid]=g_idata[i]；／／k代表第k層運算，maxThr