分支密集應(yīng)用在GPU上的優(yōu)化方法研究.pdf

1、現(xiàn)如今，以CPU+GPU為主的異構(gòu)模式被廣泛的使用，06年CUDA編程架構(gòu)的推出大大提高了GPU的可編程性，各領(lǐng)域內(nèi)使用CUDA進(jìn)行加速的應(yīng)用程序大量出現(xiàn)。
　　CUDA的架構(gòu)中引入了STMD的概念。STMD中在提高硬件資源利用效率的同時(shí)也引入了一些問題。STMD架構(gòu)中引入了Warp的概念，Warp是GPU創(chuàng)建，管理，執(zhí)行的最小單元，Warp有在一個(gè)周期內(nèi)其中所有線程必須執(zhí)行同一條指令的特性，因此在遇到分支等情況時(shí)會產(chǎn)生Contr

2、ol Divergence，嚴(yán)重影響程序的執(zhí)行效率。
　　本文重點(diǎn)研究方向是如何最大程度上降低分支密集型應(yīng)用在執(zhí)行過程中產(chǎn)生的Control Divergence以提高程序性能。為了解決這個(gè)問題，本文提出了一種基于線程交換的軟件優(yōu)化算法，可以在真實(shí)機(jī)器平臺上應(yīng)用于分支密集型應(yīng)用程序，并能夠有效的降低此類程序中大量存在的Control Divergence，從而提高程序性能，縮短程序運(yùn)行時(shí)間。
　　1)深入分析了多個(gè)分支密集應(yīng)

3、用產(chǎn)生Control Divergence的具體原理，并對程序按如下標(biāo)準(zhǔn)進(jìn)行分類。(1)易獲得分支特性（Easy-Handled，EH）與不易獲得分支特性（Hard-Handled，HH），(2)線程編號相關(guān)（Thread-Index Dependent，TID）與線程數(shù)據(jù)相關(guān)（Thread-Data Dependent，TDD）。通過這種分類將CUDA程序分為四類，可便于針對每一類進(jìn)行不同的優(yōu)化。
　　2)提出并設(shè)計(jì)一種基于線程

4、交換的優(yōu)化算法框架，并進(jìn)一步細(xì)化，將其分成直接構(gòu)造映射表優(yōu)化算法（DIMA，Direct Index-Map Algorithm）以及預(yù)處理構(gòu)造映射表算法（PIMA，Pre-process Index-Map Algorithm）。實(shí)驗(yàn)結(jié)果表明，優(yōu)化之后程序的Control Divergence基本降至無，使用線程交換優(yōu)化算法優(yōu)化之后相對與優(yōu)化之前運(yùn)行時(shí)間降低明顯。優(yōu)化之后Kernel的加速比平均有1.5左右，而總體運(yùn)行時(shí)間的加速比平均

5、有1.2左右。
　　3)DIMA與PIMA算法中參數(shù)的控制可能會對優(yōu)化結(jié)果產(chǎn)生影響。其中對于TID類型的程序線程交換范圍會有影響，對于適用于PIMA算法的程序中，預(yù)處理的次數(shù)也是需要考慮的因素，因此對算法執(zhí)行過程中參數(shù)的控制進(jìn)行測試研究并得出結(jié)論。測試發(fā)現(xiàn)，對于不同的程序，由于要進(jìn)行控制Control Divergence與控制不規(guī)則訪存之間的權(quán)衡，線程交換范圍的最優(yōu)解不同。同樣的，對于使用PIMA的程序，最優(yōu)的預(yù)處理次數(shù)也不同。