基于GPU的并行优化技术

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

第26卷第11期2009年11月 计算机应用研究ApplicationResearchofComputers

Vo.l26No.11

Nov.2009

基于GPU的并行优化技术

左颢睿,张启衡,徐 勇,赵汝进

1,2

1

1,2

1,2

*

(1.中国科学院光电技术研究所,成都610209;2.中国科学院研究生院,北京100039)

摘 要:针对标准并行算法难以在图形处理器(GPU)上高效运行的问题,以累加和算法为例,基于Nvidia公司

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

中图分类号:TP391;TP311 文献标志码:A 文章编号:100123695(2009)1124115204do:i10.3969/.jissn.100123695.2009.11.034

ParalleloptimizetechnologybasedonGPU

ZUOHao2rui1,2,ZHANGQi2heng1,XUYong1,2,ZHAORu2jin1,2

(1.InstituteofOptics&Electronics,ChineseAcademyofSciences,Chengdu610209,China;2.GraduateSchool,ChineseAcademyofSciences,Beijing100039,China)

Abstract:StandardparallelalgorithmcannotworkefficientlyonGPU.Thispapertookreductionalgorithmforexample,intro2ducedfourparalleloptmiamethodsforNVIDIA.sgraphicsprocessorunit(GPU)whichsupportedCUDAarchitecture.Thesemethodsincludedinstructionoptmiizeandsharedmemoryconflictavoidandloopunrollandthreadsoverloadoptmiize.Theex2permientresultshowstha:tparalleloptmiizecansignificantlyspeeduptheGPUcomputespeed.Theoptmiizedreductionalgo2rithmis34tmiesfasterthanstandardparallelalgorithmand70tmiesthanCPU2basedmiplementation.Keywords:graphicsprocessorunit(GPU);paralleloptmiize;reduction;computeunifieddevicearchitecture(CUDA) 随着GPU技术的快速发展,当前的GPU已经具有很强的并行计算能力,浮点运算能力甚至可以达到同代CPU的10倍以上[1]。同时,随着Nvidia公司的CUDA(统一计算设备架构)的推出,使得GPU具有更好的可编程性,因此在诸如物理系统模拟[2,3]、金融建模[4,5]以及地球表面测绘[6]等通用计算领域有着广泛的应用。如何充分利用GPU的并行计算特点实现一些复杂运算的快速求解,已经成为当今的热点问题之一。

GPU具有独特的硬件结构,采用常规并行算法,很难发挥GPU的运算优势,通常需要结合GPU的硬件特点和算法的可并行性,才能有效提高GPU的计算效率并行优化技术。

[7,8]

从图1中可以看到,采用树型结构将累加和运算分为s层(s=log2n),对第k层需要进行n/2k次运算,每一层内的运算可以并行,层与层之间的计算只能串行。代码1给出了常见并行累加和算法的伪代码:

代码1

//声明共享缓存sdata¹Sharedsdata[];

//并行读取数据,tid为线程序号,i为数组下标//g_idata和g_odata分别是输入输出数组

ºparalle:lsdata[tid]=g_idata[i];

//k代表第k层运算,maxThreadnum;k*=2){

(1)

»for(k=1;k<maxThreadnum;k=*2)//每层内部并行执行累加操作¼paralle:lif(tid%(2*k))==0sdata[tid]+=sdata[tid+k];}//将结果写回到输出数组½g_odata[]=sdata[0]

。本文以具有代表

性的累加和算法在GPU上的优化实现为例介绍基于GPU的

1 累加和算法及其并行实现

已知数组x[n],累加和算法公式为

sum=Ex[k]

k=0n

累加和算法对n个元素进行加法运算,不论采用串行还是并行算法,均需要执行n-1次运算。GPU是基于SIMD架构的并行处理器,因此累加和运算可以采用树型计算将串行运算改写为并行运算

[9]

,树型算法示意图如图1所示。

收稿日期:2008212207;修回日期:2009201212 基金项目:国家/8630高技术(保密)资助项目

作者简介:左颢睿(19812),男,四川绵阳人,博士研究生,主要研究方向为并行计算和图像复原(zuohaoru@);张启衡(19502),男,四川成都人,研究员,博导,主要研究方向为光电探测、目标跟踪与识别;徐勇(19842),男,云南红河人,博士研究生,主要研究方向为实时图像压缩技

2男,,,