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

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