![3D von Neumann Stencil Model](https://upload.wikimedia.org/wikipedia/commons/6/64/3D_von_Neumann_Stencil_Model.svg)
Iterative Stencil Loops (ISLs) are a class of numerical data processing solution
[
Roth, Gerald et al. (1997)
Proceedings of SC'97: High Performance Networking and Computing.
]
Compiling Stencils in High Performance Fortran.
'
which update
array elements according to some fixed pattern, called a stencil.
[
Sloot, Peter M.A. et al. (May 28, 2002)
]
Computational Science – ICCS 2002: International Conference, Amsterdam, The Netherlands, April 21–24, 2002. Proceedings, Part I.
'
Page 843. Publisher: Springer. .
They are most commonly found in
computer simulation
Computer simulation is the process of mathematical modelling, performed on a computer, which is designed to predict the behaviour of, or the outcome of, a real-world or physical system. The reliability of some mathematical models can be dete ...
s, e.g. for
computational fluid dynamics
Computational fluid dynamics (CFD) is a branch of fluid mechanics that uses numerical analysis and data structures to analyze and solve problems that involve fluid flows. Computers are used to perform the calculations required to simulate th ...
in the context of scientific and engineering applications.
Other notable examples include solving
partial differential equations
In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a multivariable function.
The function is often thought of as an "unknown" to be solved for, similarly to ...
,
the
Jacobi Jacobi may refer to:
* People with the surname Jacobi (surname), Jacobi
Mathematics:
* Jacobi sum, a type of character sum
* Jacobi method, a method for determining the solutions of a diagonally dominant system of linear equations
* Jacobi eigenva ...
kernel, the
Gauss–Seidel method
In numerical linear algebra, the Gauss–Seidel method, also known as the Liebmann method or the method of successive displacement, is an iterative method used to solve a system of linear equations. It is named after the German mathematicians Carl ...
,
image processing
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
and
cellular automata
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
.
[
Fey, Dietmar et al. (2010)
]
Grid-Computing: Eine Basistechnologie für Computational Science
'.
Page 439. Publisher: Springer.
The regular structure of the arrays sets stencil techniques apart from other modeling methods such as the
Finite element method
The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat ...
. Most
finite difference codes which operate on regular grids can be formulated as ISLs.
Definition
ISLs perform a sequence of sweeps (called timesteps) through a given array.
Generally this is a 2- or 3-dimensional regular grid.
The elements of the arrays are often referred to as cells. In each timestep, all array elements are updated.
Using neighboring array elements in a fixed pattern (the stencil), each cell's new value is computed. In most cases boundary values are left unchanged, but in some cases (e.g.
LBM codes) those need to be adjusted during the computation as well. Since the stencil is the same for each element, the pattern of data accesses is repeated.
More formally, we may define ISLs as a
5-tuple with the following meaning:
*