Diamond Tiling for Periodic Stencil Loop Nests by Means of Transitive Closure-based Extraction of Overlapping Iteration Spaces

Stencil computations are a prevalent class of loop nests and a fundamental part of numerous scientific applications. The substantial parallelism potential enclosed in these loops has inspired extensive research into its efficient extraction, leading to the development of various tiling schemes that enable their concurrent and load-balanced execution, thereby maximizing the utilization of multiple processing units. Most of these techniques, however, are based on the affine transformations framework which limits the scope of optimization to loops constrained by uniform dependences. Therefore, only a handful of studies have addressed locality enhancement and parallelization of stencil computations over periodic domains, where boundary grid points on opposite edges are considered as neighbors. In this paper, we show that an effective and load-balanced tiling scheme with the concurrent start property can also be derived based on the iteration space slicing framework, by first expanding the original hyperrectangular tiles to include all their dependence sources, and then iteratively extracting the areas of redundant computations, which are identified using the transitive closure of the data dependence graph. This approach, combined with the previously introduced tiles correction technique — used across spatial dimensions — extends the scope of applicability of the optimization to stencils with periodic boundary conditions and non-uniform dependences in general. Our experimental evaluation demonstrates that the proposed algorithm achieves comparable results as state-of-the-art techniques when applied to uniform loop nests, and offers visibly improved performance for stencils over periodic domains, achieving up to 3x speedup compared to related techniques.