Jigsaw: Toward Conflict-free Vectorized Stencil Computation by Tessellating Swizzled Registers

Abstract: Stencil computation plays a pivotal role in numerous scientific and engineering applications. Previous studies have extensively investigated vectorization techniques to enhance in-core parallelism; however, the performance bottleneck caused by data alignment conflicts (DAC) has not been effectively resolved in all dimensions. This paper proposes Jigsaw, a conflict-free vectorization method to reduce DAC across all dimensions by tessellating swizzled finest-grained lanes. Jigsaw comprises three key components: Lane-based Butterfly Vectorization, SVD-based Dimension Flattening, and Iteration-based Temporal Merging. These components effectively address DAC across spatial and temporal dimensions. Experimental results on different machines demonstrate that Jigsaw could achieve a significant improvement compared to the state-of-the-art techniques, with an average speedup of 2.31x on various stencil kernels.

@inproceedings{ppoppjigsaw,
  title={Jigsaw: Toward Conflict-free Vectorized Stencil Computation by Tessellating Swizzled Registers},
  author={Yiwei Zhang and Kun Li and Liang Yuan and Yunquan Zhang and Ting Cao and Mao Yang},
  booktitle={30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP)},

  year={2025}
}