Stencils in Scientific Computations
Anshu Dubey · 2014
Stencils occur in many areas, but they are ubiquitous in scientific computing. They range from the simple Jacobi iterations to the extremely complex ones used in the solution of highly nonlinear partial differential equations (PDE). High level programming languages typically used in implementation of scientific software, by not providing explicit support for stencils, force each implementation to make choices about expressing its specifics such as dimensionality, data layout, order of access and order of operations. These choices often hide the opportunity for optimizations from the compilers. Therehave been attempts to provide abstractions for simpler stencils, and they have met with success in some areas, but multiphysics scientific applications present challenges that cannot be met by simple stencil abstractions. The applications may have hierarchy, or non-uniformity, or both in their discretizations which cannot be expressed by stencils describing uniform discretizations. The physics operators being applied maybe non-linear which would demand composability of stencils. As the order of the solution method increases, the size and the reach of stencil also increases, and there may be conditions that imply the application of the stencil to an arbitrary subset of the discretized points. And finally, if there are multiple steps involved in an update, intermediate results need to be managed. AMR Shift Calculus, (Phil Colella and Brian Van Straalen 2014), provides a generalized abstraction that addresses many of these concerns. It provides a means of expressing stencil computations in the form of a collection of shift operations combined with associated weights, that can be applied to a specified collection of discretized points. The shift calculus also addresses the hierarchy in the discretization, and defines operators on stencils that allow more complex stencils to be composed from simpler ones. Because the shift calculus makes it possible to express the computation concisely and precisely, it gets around the problem of false dependencies. Additionally, the composability of the stencil operators exposes possibilities of loop or even function fusion, and the granularity for holding intermediate values to the compiler for better optimization opportunities.