基于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男,,,

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

#4116#

2 基于GPU的并行优化技术

计算机应用研究 第26卷

数据时,会产生共享缓存访问冲突,此时GPU只能串行地对数据进行访问。

代码2中采用式(2)来产生线程访问共享缓存的索引:

index=stride*tid=2*k*tid;1[index[maxThreadnum

(2)

代码1中包含了一系列有代表性的GPU并行优化问题,下文分别从指令优化、共享缓存访问优化、解循环优化和线程过载优化四个方面介绍GPU的并行优化技术。211 指令优化

GPU的指令方法分为两个方面:

a)采用专有指令或运算时间少的指令代替复杂的运算指令。代码1的¼在核心循环中使用了效率很低的求模运算,每次计算至少需要32个时钟周期,如果将求模改写为等价的乘法指令,则只需4个时钟周期。此外,GPU还提供了许多专用指令代替一些常用的复杂计算,如三角函数运算、模运算、指数运算和开方运算等,这些函数用一条指令即可代替复杂的标准C函数,大大降低了运算的复杂度,具体指令集见参考文献[1]。

b)尽量避免在同一个warp(包,GPU基本执行单位,由32个线程组成)中使用产生分支的语句。在同一个warp中的线程如果出现了分支执行,GPU会将不同的分支线程串行处理,严重影响GPU的并行度。代码1的¼中的运行判断条件tid%(2*k)会导致同一个warp中的线程产生分支,当k=1时,在第一个warp内线程的执行情况如图2(a)所示。

从图2(a)可知,当k=1时,在warp中有一半的线程无法运行,GPU的并行效率降低了50%,这种情况就称为交叉寻址(interleavedaddressing)。交叉寻址大大降低了GPU的执行效率,应尽量避免,代码2给出了优化方法。

代码2

//将求模指令改写为乘法指令intindex=2*k*tid;

//采用不会产生分支的判断条件if(index3maxThreadnum4

sdata[index]+=sdata[index+k];

由于线程的寻址步长为偶数(stride=2*k),会产生共享缓存冲突[1]。图3(a)描述了GPU的共享缓存结构以及在代码2中k=1时产生的缓存冲突。

从式(2)可知,随着k的增大,会产生更加严重的冲突,当k=8时将产生16路访问冲突,此时16个线程访问同一个bank,将导致16步串行操作。解决共享缓存冲突的方法是令线程寻址步长为奇数,因此代码1的»¼可改写为代码3。

代码3

//将循环条件倒置,避免偶数步长for(unsignedintk=maxThreadnum/2;k>0;k>>=1){//访问步长k=1,无冲突paralle:lif(tid<k)

sdata[tid]=+=sdata[tid+k];}

代码3将循环条件倒置,每个线程顺序寻址,stride为1,半包内的线程顺序访问共享缓存,满足无冲突访问条件,避免了缓存冲突,图3(b)给出了代码3的寻址示意图。

在代码2中,将取模指令改为乘法指令,在寻址共享缓存时线程按线程号顺序执行,每个warp内的线程均参与寻址,不会产生空闲的线程,线程的执行情况如图2(b)

所示。

213 解循环优化

用循环控制算法流程,可使代码简洁易懂,但同时引入两个问题:a)循环控制增加了额外的计算量,尤其是核心计算简单的情况下,循环控制会占用主要的计算资源;b)采用循环控制有时会带来冗余的运算,这两种情况统称为指令过载(in2structionoverhead)[11]。代码1中,核心计算只有一次加法,而循环控制指令需要一次加法和一次比较,所占的运算量超过了核心运算;在核心计算时每个线程都需要进行循环和执行条件判断,而实际上GPU中最后一个warp的32个线程可直接计算,无须判断。如果直接运算每个线程包含了六次冗余计算(循环和执行条件判断),而理论上每个线程的最大计算次数

212 共享缓存访问优化

CUDA技术采用了共享缓存(sharedmemory)技术,使得GPU能够在4个时钟周期内访问共享缓存,远低于访问全局缓存(globalmemory)的400~600个时钟周期。为提高处理速度,通常要将数据从GPU的全局缓存读取到共享缓存中再进行核心计算[10],如代码1的º所示。当处于half2warp(半包,

16为九次[1](受最大线程数maxThreadnum约束),因此必须对指令过载进行优化以提高GPU性能。

解循环的关键在于是否能预先知道运算时的循环次数。由于GPU限制一个block(块,GPU内核加载的基本单位)内最多有512个线程[1],这就限定循环次数的最大值为九次,可以根据不同的线程数设置执行条件,为解循环提供基础;同时如数,从而每一加运对称

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

第11期左颢睿,等:基于GPU的并行优化技术#4117 #

性,就可以采用树型算法解开GPU的循环[11]。代码1中的循环可改写为代码4。

代码4

if(maxThreadnum>=512){paralle:l

if(tid<256){sdata[tid]+=sdata[tid+256];}}if(maxThreadnum>=256){paralle:l

if(tid<128){sdata[tid]=+sdata[tid+128];}}if(maxThreadnum>=128){paralle:lif(tid<64){sdata[tid]+=sdata{tid+64];}}if(tid<32) {if(maxThreadnum>=64)

{sdata[tid]+=sdata[tid+32];} if(maxThreadnum>=32)

{sdata[tid]+=sdata[tid+16];} if(maxThreadnum>=16)

{sdata[tid]+=sdata[tid+8];} if(maxThreadnum>=8)

{sdata[tid]+=sdata[tid+4];} if(maxThreadnum>=4)

{sdata[tid]+=sdata[tid+2];} if(maxThreadnum>=2)

{sdata[tid]+=sdata[tid+1];}

将式(6)代入式(3)(4),可得树型算法的时间复杂度依然为O(log2N),而运算成本也保持在O(N)的数量级上。在GPU实现时,就是适当减少参与运算线程的数目,然后让每个线程处理多个数据,据此将代码1中的º作如下改写。

代码5

//累加log2n个元素到共享缓存中

sdata[tid]=g_idata[i]+g_idata[i+1]+,+g_idata[i+log2n-1]

代码5在数据搬运时,每个线程串行地将log2n个数据累加到共享缓存中,然后在共享缓存中并行地执行树型算法。采用这种方式,每个线程在搬运数据时,尽可能多地对数据进行操作,减少共享缓存中树型计算在全部计算中所占的比重,降低了树型运算对线程的浪费。215 最终优化代码

采用各种优化方法后,最终结果如代码6所示。

代码6

Sharedsdata[];

sdata[tid]=g_idata[i]+g_idata[i+1]+,+g_idata[i+log2n-1];if(maxThreadnum>=512)

{paralle:l

if(tid<256){sdata[tid]+=sdata[tid+256];}}if(maxThreadnum>=256){paralle:l

if(tid<128){sdata[tid]+=sdata[tid+128];}}if(maxThreadnum>=128){paralle:l

if(tid<64){sdata[tid]+=sdata{tid+64];}}if(tid<32) {if(maxThreadnum>=64)

{sdata[tid]+=sdata[tid+32];} if(maxThreadnum>=32) {sdata[tid]+=sdata[tid+16];} if(maxThreadnum>=16)

{sdata[tid]+=sdata[tid+8];} if(maxThreadnum>=8)

{sdata[tid]+=sdata[tid+4];} if(maxThreadnum>=4)

{sdata[tid]+=sdata[tid+2];} if(maxThreadnum>=2)

{sdata[tid]+=sdata[tid+1];}

代码4中,列出了所有可能出现的执行条件,maxThread2num值由用户预先指定,并且在编译时就可以确定诸如if(maxThreadnum\512)的条件语句是否执行,不会增加核心计算复杂度,这样就取消了循环控制语句,提高了计算资源的利用率。

214 线程过载优化

线程过载是指在并行计算时,系统中存在着大量空闲或无效的线程,从而导致计算效率的降低。从代码1的º可知,对于n个数据,需要使用n个线程进行加载。然而在核心计算中,随着k值的增大,每一层核心运算使用的线程数按2k指数幅度减少,第一层树型算法参与计算的线程有n/2个,而最后一层参与计算的线程数仅有1个。没有利用的线程也要进行执行循环和条件判断,从而导致很多无效的计算。对线程过载,可以根据Brent定理[12]进行分析,Brent公式如式(3)(4)所示:

T=t+(m-t)/p

cost=p*T

(3)(4)

3 实验结果与分析

本文所采用的实验平台为IntelCore2Q6600,主频2.4GHz,内存为4GB,显卡型号为GeForceGF8800Ultra,显存为768MB,核心频率为612MHz,数据带宽为103.68GBps,驱动版本为6.14.11.6909,操作系统为WindowsXP,整个实现基于CUDASDK1.1。

实验分为两组,第一组实验对固定长度的数组用不同的优化方法进行优化,表1列出了每种方法的优化效果,实验数据为8M个元素的单精度浮点数组。

表1 并行优化效果

优化方法

12345CPU实现最初实现指令优化共享存储优化解循环优化时间/msGPU优化效果/倍相对PC优化效果/倍30.6915.116.553.241.4112.314.6710.7312.034.699.4721.77式(3)中,T表示并行算法的时间复杂度;t表示多少级不相关的运算;m表示算法在理论上需要的运算量;p表示并行运行的处理器(GPU中用线程数代替)。式(4)中,cost表示并行处理时算法的运算成本。由(3)(4)易知(t=1,p=1)长度为N的数组串行算法的时间复杂度为O(N),运算成本为O(N);如果分配N个线程执行树型算法,可得式(5):

t=log2n,m=n-1,p=n

(5)

将式(5)代入式(3)(4),可知算法时间复杂度为O(log2

N),运算成本为O(Nlog2N)。树型算法的运算成本是串行算法的log2N倍,当N较大时,并行运算的运算成本会大大超过串行运算。

根据Brent公式,可以采用如下方法解决线程过载问题:使处理器的个数p=n/log2n,让每个处理器串行处理log2n个数据,能达到最优的运算成本,据此可得式(6):

tl(/log2n),m=n1,p=n/2n

针对标准并行算法难以在图形处理器(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

本文来源：https://www.bwwdw.com/article/w3b1.html