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

Pipelining granularity optimization algorithm based on loop tiling

当计算划分层迭代数目较大,或是循环体单次迭代工作量较大,但可用的并行线程数目较小时,传统的基于循环分块的流水粒度优化方法无法进行处理。为此,提出一种基于循环分块减小流水粒度的方法,并根据流水并行循环的代价模型实现最优流水粒度的求解,设计实现了一个流水计算粒度的优化算法。对有限差分松弛法(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.