针对标准并行算法难以在图形处理器(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],这就限定循环次数的最大值为九次,可以根据不同的线程数设置执行条件,为解循环提供基础;同时如数,从而每一加运对称