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

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

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

2、高算法在GPU上的執(zhí)行效率，優(yōu)化后累加和算法的運(yùn)算速度相比標(biāo)準(zhǔn)并行算法提高了約34倍。相比CPU串行實(shí)現(xiàn)提高了約70倍。關(guān)鍵詞：圖形處理器；并行優(yōu)化；累加和；統(tǒng)一計(jì)算設(shè)備架構(gòu)中圖分類(lèi)號(hào)：TP391；TP311文獻(xiàn)標(biāo)志碼：A文章編號(hào)：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)的并行計(jì)算能力，浮點(diǎn)運(yùn)算能力甚至可以達(dá)到同代CPU的10倍以上?。同時(shí)，隨著Nvidia公司的CUDA(統(tǒng)一計(jì)算設(shè)備架構(gòu))的推出，使得GPU具有

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

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

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