Stencil computations are essential for simulating the evolution of physical systems across multi-dimensional grids over multiple timesteps. State-of-the-art techniques in this field fall into three major groups: tiled looping algorithms, divide-and-conquer trapezoidal algorithms, and Krylov subspace methods.

Stencil computations are ubiquitous in modern grid-based physical simulations. In this paper, we present FOURST – a compiler to generate programs computing time iterated linear periodic and aperiodic stencil computations with fast Fourier transform methods. This paper outlines the design and implementation of the code generation approach in FOURST, to automatically generate FFT-based stencil solvers. We present experimental results on the state-of-the-art Ookami supercomputer housing Fujitsu A64FX and Intel Skylake processors, to study the performance of FOURST and a state-of-the-art tiling-based optimized code generator PLuTo on various stencil shapes and varying the number of time iterations. We discuss the performance profiles, and limitations, of both approaches on high-end modern hardware.

Stencil computations are widely used to simulate the change of state of physical systems. The current best algorithm for performing aperiodic linear stencil computations on a d (≥ 1)-dimensional grid of size N for T timesteps does Θ(TN1-1/d+N Log N) work. We introduce novel techniques based on random walks and Gaussian approximations for an asymptotic improvement of this work bound for a class of linear stencils. We also improve the span (i.e., parallel running time on an unbounded number of processors) asymptotically from the current state of the art.

The binary-forking model is a parallel computation model, formally defined by Blelloch et al., in which a thread can fork a concurrent child thread, recursively and asynchronously. The model incurs a cost of Θ(łog n) to spawn or synchronize n tasks or threads. The binary-forking model realistically captures the performance of parallel algorithms implemented using modern multithreaded programming languages on multicore shared-memory machines. In contrast, the widely studied theoretical PRAM model does not consider the cost of spawning and synchronizing threads, and as a result, algorithms achieving optimal performance bounds in the PRAM model may not be optimal in the binary-forking model. Often, algorithms need to be redesigned to achieve optimal performance bounds in the binary-forking model and the non-constant synchronization cost makes the task challenging.

Stencil computations are widely used to simulate the change of state of physical systems across a multidimensional grid over multiple timesteps. The state-of-the-art techniques in this area fall into three groups: cache-aware tiled looping algorithms, cache-oblivious divide-and-conquer trapezoidal algorithms, and Krylov subspace methods.