基于循环分块的流水粒度优化算法  

Pipelining granularity optimization algorithm based on loop tiling

作　　者：刘晓娴[1,2] 赵荣彩[1,2] 丁锐[1,2] 李雁冰[1,2] 

机构地区：[1]信息工程大学,郑州450002 [2]数学工程与先进计算国家重点实验室,郑州450002

出　　处：《计算机应用》2013年第8期2171-2176,共6页journal of Computer Applications

基　　金："核高基"国家科技重大专项(2009ZX01036-001-001-2)

摘　　要：当计算划分层迭代数目较大,或是循环体单次迭代工作量较大,但可用的并行线程数目较小时,传统的基于循环分块的流水粒度优化方法无法进行处理。为此,提出一种基于循环分块减小流水粒度的方法,并根据流水并行循环的代价模型实现最优流水粒度的求解,设计实现了一个流水计算粒度的优化算法。对有限差分松弛法(FDR)的波前循环和时域有限差分法(FDTD)中典型循环的测试表明,与传统的流水粒度选择方法相比,所提算法能够得到更优的循环分块大小。When the pipelining loop has a great number of iterations,or the size of its body is large,but the number of available threads is small,the workload between two synchronizations of a thread is so heavy,which produces pretty low degree of parallelism.The traditional trade-off approach based on loop tiling cannot handle the above situation.To solve this problem,a pipelining granularity decreasing approach based on loop tiling was proposed.The optimal pipelining granularity was obtained by building the cost model for pipelining loop and a pipelining granularity optimizing algorithm was implemented.By measuring the wavefront loops of Finite Difference Relaxation（FDR） and the representative loops of Finite Difference Time Domain（FDTD）,the loops show better performance improvement by using the proposed algorithm than the traditional one.

关 键 词：自动并行化 流水并行 流水粒度 循环分块 代价模型 

分 类 号：TP314[自动化与计算机技术—计算机软件与理论]