基于GPU的并行优化技术(4)

针对标准并行算法难以在图形处理器(GPU)上高效运行的问题, 以累加和算法为例, 基于Nvidia公司统一计算设备架构(CUDA) GPU介绍了指令优化、共享缓存冲突避免、解循环优化和线程过载优化四种优化方法。实验结果表明, 并行优化能有效提高算法在GPU上的执行效率, 优化后累加和算法的运算速度相比标准并行算法提高了约34倍, 相比 CPU串行实现提高了约 70倍。

#4118#计算机应用研究 第26卷

第二组实验对不同长度的数组(1~64M个单精度浮点数)采用最优化方法进行累加和运算,对GPU的数据带宽使用情况进行了测试,实验结果如图4

所示。

GPU上进行并行优化的重要性和必要性;同时多种优化方法的使用说明了基于GPU的并行优化是一个复杂的过程,需要全面考虑指令、存储器和并行算法复杂度等对运算效率的影响。本文介绍的优化方法和思路有很强的通用性,可以应用于各种算法在GPU上的并行优化。参考文献:

[1]NVIDIA.NVIDIACUDAprogrammingguideversion1.1[EB/OL].

(2007201)./object/cuda_home.htm.l[2]HARADAT.Real2timerigidbodysimulationonGPUs[M].

.l]:AddisonWesleyProfessiona,l2007:6112632.

[S.

从上面两组实验结果可以得到如下结论:

a)GPU可以有效地对算法进行加速,在累加和算法中采用最优化方法时GPU可以达到同代CPU的70倍左右。

b)结合GPU的硬件特点对并行算法进行优化是非常有效的,在累加和算法中最优化方法比不作任何优化的方法效率提高了约34倍。

c)在算法优化的过程中,应根据算法的特点选择恰当的方法。例如,累加和运算是传输密集型算法,如何让多个线程高效地访问数据是并行优化的主要问题,从表1所列的优化效果可以看到,针对线程分配进行优化的线程过载优化方法可以取得最好的效果。

d)同一算法对不同长度的数据进行处理,GPU的运算速度有很大的不同,如图4曲线所示,当处理4M以下的数据时GPU带宽利用率远低于处理4M以上的数据,这是因为数据量太小时每线程的运算量不充分,线程切换频繁,系统调度的开销占用了较多执行时间;随着数据量的增大,每线程处理数据增多,此时系统调度占用执行时间的比例降低,因此GPU的带宽利用率得以提高。在优化算法时要充分考虑这个问题,通过实验以选择最优的数据处理长度,如在累加和算法中,数据长度应选择在8~32M。

[3]NYLANDL,HARRISM,PRINSJ.FastN2bodysimulationwithCU2

DA[M].[S..l]:AddisonWesleyProfessiona,l2007:6772696.[4]PODLOZHNYUKV,HARRISM.Monte2Carlooptionpricing[EB/

OL].(2007211221)./object/cuda_home.htm.l

[5]PODLOZHNYUKV.Black2scholesoptionpricing[EB/OL].(20072

04206)./object/cuda_home.htm.l[6]DESCHIZEAUXB,BLANCJY.Imagingearth.ssubsurfaceusing

CUDA[M].[S..l]:AddisonWesleyProfessiona,l2007:8312850.[7]HARISHP,NARAYANANPJ.Acceleratinglargegraphalgorithms

ontheGPUusingCUDA[C]//ProcofIEEEInternationalConferenceonHighPerformanceComputing.2007:1972208.[8]

SHAMSR,BARNESN.SpeedingupmutualinformationcomputationusingNVIDIACUDAhardware[C]//ProcofDigitalImageCompu2ting:TechniquesandApplications.Adelaide,Australia:[s.n.],2007:5552560.

[9]陈国良.并行算法的设计与分析[M].北京:高等教育出版社,

2002.

[10]SHAMSR,KENNEDYRA.Efficienthistogramalgorithmsfor

NVIDIACUDAcompatibledevices[C]//ProcofInternationalConfer2enceonSignalProcessingandCommunicationsSystems,2007:4182422.

[11]HARRISM.OptimizingparallelreductioninCUDA[EB/OL].

(2007211)./object/cuda_home.htm.l[12]BRENTRP.Theparallelevaluationofgeneralarithmeticexpressions

[J].JournaloftheAssociationforComputingMachinery,1974,21(2):2012206.

4 结束语

本文以累加和算法的优化实现为例介绍了在GPU上进行并行优化的典型方法,包括指令优化、共享缓存优化、解循环优化和线程过载优化。优化后算法效率提高了约34倍,表明在

(上接第4114页)

[6]TPC2WBenchmark[EB/OL].(2009)..[7]LAZOWSKAED,ZAHORJANJ,GRAHAMGS,etal.Quantitative

systemperformance:computersystemanalysisusingqueueingnetworkmodels[M].UpperSaddleRiver:Prentice2Hal,l1984.

[8]杜才华,张文博,王伟.ASRMF:一种基于资源调用链的应用服务

器资源监控框架[J].计算机科学,2007,34(9A):2652269.[9]Mercurydiagnostics[EB/OL].(2009)./

us/products/diagnostics/.

[10]IBMCorp.TivoliWebmanagementsolutions[EB/OL].

www.tivol.icom/products/demos/twsm.htm.l

[11]CAWilyIntroscope[EB/OL].(2009)..[(ttp:./.

http://

[13]Netuitive[EB/OL].(2009)./.

[14]CHENMY,KICIMANE,FRATKINE,etal.Pinpoint:problemde2

terminationinlarge,dynamicInternetservices[C]//ProcofDepend2ableSystemsandNetworks.2002:5952604.

[15]JAINAK,DUBESRC.Algorithmsforclusteringdata[M].[S.

.l]:Prentice2Hal,l1988.

[16]ROMESBURGHC.Clusteranalysisforresearchers[M].[S..l]:

Life2timeLearningPublications,1984.

[17]BARHAMP,DONNELLYA,ISAACSR,ingmagpieforre2

questextractionandworkloadmodelling[C]//ProcofOperatingSys2temsDesignandImplementation.2004:2592272.

[18]COHENI,ZHANGS,GOLDSZMIDTM,etal.Capturing,

umses.2inde2

xing,clustering,andretrievingsystemhistory[C]//ProcofSymposi2