Abstract: Stencil computations represent a very common class of nested loops in scientific and engineering applications. The exhaustively studied tiling is one of the most powerful transformation techniques to explore the data locality and parallelism. Unlike previous work, which mostly blocks the iteration space of a Stencil directly, this paper proposes a novel two-level tessellation scheme. First, the data space is tiled with different blocks. Then, all blocks are tiled along the time dimension to iterate over the iteration space. The proposed scheme has the following advantages: (1) maximizing concurrent execution; (2) no redundancy computation; (3) simple loop conditions; (4) adapting to different sizes, shapes, orders, and boundary conditions of Stencil. The experimental results show that for 3D27p Stencil, the performance of the non-periodic boundary is 12% higher than that of Pluto, and the performance of the periodic boundary is up to 40% higher than that of Pochoir.

Key words: Stencil computation, tessellation, tiling

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

关键词: Stencil计算, 空间密铺, 分块方法