Jigsaw: Toward Conflict-free Vectorized Stencil Computation by Tessellating Swizzled Registers
Open Access
- 28 February 2025
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 481-495
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.Keywords
This publication has 61 references indexed in Scilit:
- FOURST: A code generator for FFT-based fast stencil computations2022
- Delivering Performance-Portable Stencil Computations on CPUs and GPUs Using Bricks2018
- Compiler-Directed Transformation for Higher-Order Stencils2015
- PATUS: A Code Generation and Autotuning Framework for Parallel Iterative Stencil Computations on Modern Microarchitectures2011
- Data Layout Transformation for Stencil Computations on Short-Vector SIMD Architectures2011
- An auto-tuning framework for parallel multicore stencil computations2010
- Efficient SIMD Code Generation for Runtime Alignment and Length Conversion2005
- Achieving Scalable Locality with Time SkewingInternational Journal of Parallel Programming, 2002
- Efficient tiling for an ODE discrete integration program: redundant tasks instead of trapezoidal shaped-tiles2002
- A Vectorizing Compiler for Multimedia ExtensionsInternational Journal of Parallel Programming, 2000