Compiler-Directed Transformation for Higher-Order Stencils
Authors:
- Protonu BasuPBProtonu Basu
- Mary HallMHMary Hall
- Samuel WilliamsSWSamuel Williams
- Brian Van StraalenBSBrian Van Straalen
- Leonid OlikerLOLeonid Oliker
- Phillip ColellaPCPhillip Colella
- 1 May 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302075,p. 313-323
Abstract
As the cost of data movement increasingly dominates performance, developers of finite-volume and finite-difference solutions for partial differential equations (PDEs) are exploring novel higher-order stencils that increase numerical accuracy and computational intensity. This paper describes a new compiler reordering transformation applied to stencil operators that performs partial sums in buffers, and reuses the partial sums in computing multiple results. This optimization has multiple effect son improving stencil performance that are particularly important to higher-order stencils: exploits data reuse, reduces floating-point operations, and exposes efficient SIMD parallelism to backend compilers. We study the benefit of this optimization in the context of Geometric Multigrid (GMG), a widely used method to solve PDEs, using four different Jacobi smoothers built from 7-, 13-, 27- and 125-point stencils. We quantify performance, speedup, and numerical accuracy, and use the Roofline model to qualify our results. Ultimately, we obtain over 4× speedup on the smoothers themselves and up to a 3× speedup on the multigrid solver. Finally, we demonstrate that high-order multigrid solvers have the potential of reducing total data movement and energy by several orders of magnitude.Keywords
This publication has 28 references indexed in Scilit:
- A framework for enhancing data reuse via associative reorderingACM SIGPLAN Notices, 2014
- Auto-generation and auto-tuning of 3D stencil codes on GPU clusters2012
- Improving the arithmetic intensity of multigrid with the help of polynomial smoothersNumerical Linear Algebra with Applications, 2012
- A Fourth-Order Accurate Finite-Volume Method with Structured Adaptive Mesh Refinement for Solving the Advection-Diffusion EquationSIAM Journal on Scientific Computing, 2012
- RooflineCommunications of the ACM, 2009
- 3D finite difference computation on GPUs using CUDA2009
- Optimization and Performance Modeling of Stencil Computations on Modern MicroprocessorsSIAM Review, 2009
- Introducing a parallel cache oblivious blocking approach for the lattice Boltzmann methodProgress in Computational Fluid Dynamics, An International Journal, 2008
- Cache-Efficient Multigrid AlgorithmsThe International Journal of High Performance Computing Applications, 2004
- Tiling Optimizations for 3D Scientific Computations2000