Locally Recursive Non-Locally Asynchronous Algorithms for Stencil Computation

Abstract

LRnLA algorithms provide many advantages for stencil computations. In contrast to the traditional stepwise approaches, the performance efficiency does not decrease with the problem data size and the parallel scaling is close to linear. This is achieved by tracing the data dependencies of the problem, taking into account the finite information propagation speed in the numerical scheme. The optimal traversal rule is found from the requirement to use all memory hierarchy levels and all levels of parallelism with higher efficiency. Stencil computing is applied, among others, in wave modeling (FDTD scheme for optics; Levander scheme for seismic waves; finite difference scheme for acoustics), gas and fluid dynamics (RKDG scheme, Lattice–Boltzmann method), plasma physics (particle-in-cell). The experience of the application of LRnLA algorithm approach in all mentioned fields aided the development of its theory. Firstly, for a given computer, given simulation problem, and a given method the achievable performance may be estimated. Secondly, based on these estimates the optimal algorithmmay be found. The conclusions provide a guidance on how to apply the LRnLA method to any local stencil scheme on any relevant computer, to achieve new breakthroughs in the performance efficiency.