Locally Recursive Non-Locally Asynchronous Algorithms for Stencil Computation
- Authors: Levchenko V.D.1, Perepelkina A.Y.1
-
Affiliations:
- Keldysh Institute of Applied Mathematics
- Issue: Vol 39, No 4 (2018)
- Pages: 552-561
- Section: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/202032
- DOI: https://doi.org/10.1134/S1995080218040108
- ID: 202032
Cite item
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.
About the authors
V. D. Levchenko
Keldysh Institute of Applied Mathematics
Author for correspondence.
Email: lev@keldysh.ru
Russian Federation, Miusskaya sq. 4, Moscow, 125047
A. Y. Perepelkina
Keldysh Institute of Applied Mathematics
Email: lev@keldysh.ru
Russian Federation, Miusskaya sq. 4, Moscow, 125047