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