Revisiting split tiling for stencil computations in polyhedral compilation

Complex tile shapes maximize parallelism and locality of stencil computations by enabling tile-wise concurrent start, i.e., all tiles along a particular tiling direction of the iteration space can be started concurrently. We study split tiling—a tiling technique exploiting tile-wise concurrent start at the expense of additional synchronizations, in the context of polyhedral compilation. Derived from classical parallelogram tiling, our approach first splits a parallelogram tile into multiple phases that can be executed simultaneously with those of the neighboring tiles. The technique then minimizes the amount of synchronizations by merging boundary phases of consecutive tiles along the time-tiled direction. We implement our approach on top of a well-defined polyhedral representation, generating code for both CPUs and GPUs. The experimental results on a 16-core Intel Xeon Silver show that our approach can achieve an average improvement of 2