一种基于空间密铺的并行Stencil算法

摘要

Stencil计算是一种科学和工程应用中常见的循环模式,而分块技术是一种提高数据局部性和并行性的强大转换方法.与以往直接对整个迭代空间进行分块的分块技术不同,本文提出了一种新的两层密铺分块的并行算法.首先,利用不同分块密铺数据空间,其次,所有分块沿时间维度的扩展能密铺迭代空间.本文提出的算法有以下优点:(1)最大化并发执行,(2)无冗余计算,(3)简洁的循环条件,(4)适应Stencil不同的尺寸、形状、阶数和边界条件.实验结果表明,对于3d27p Stencil,非周期边界的性能比Pluto高12％,周期边界的比Pochoir最高提升40％.