Iterative Stencil Loops (ISLs) or Stencil computations are a class of numerical data processing solution which update array elements according to some fixed pattern, called a stencil. They are most commonly found in computer simulations, e.g. for computational fluid dynamics in the context of scientific and engineering applications. Other notable examples include solving partial differential equations, the Jacobi kernel, the Gauss–Seidel method, image processing and cellular automata. The regular structure of the arrays sets stencil techniques apart from other modeling methods such as the Finite element method. 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 ( I , S , S 0 , s , T ) {\displaystyle (I,S,S_{0},s,T)} with the following meaning:
I = ∏ i = 1 k [ 0 , … , n i ] {\displaystyle I=\prod _{i=1}^{k}[0,\ldots ,n_{i}]} is the index set. It defines the topology of the array.
S {\displaystyle S} is the (not necessarily finite) set of states, one of which each cell may take on any given timestep.
S 0 : Z k → S {\displaystyle S_{0}\colon \mathbb {Z} ^{k}\to S} defines the initial state of the system at time 0.
s ∈ ∏ i = 1 l Z k {\displaystyle s\in \prod _{i=1}^{l}\mathbb {Z} ^{k}} is the stencil itself and describes the actual shape of the neighborhood. There are l {\displaystyle l} elements in the stencil.
T : S l → S {\displaystyle T\colon S^{l}\to S} is the transition function which is used to determine a cell's new state, depending on its neighbors. Since I is a k-dimensional integer interval, the array will always have the topology of a finite regular grid. The array is also called simulation space and individual cells are identified by their index c ∈ I {\displaystyle c\in I} . The stencil is an ordered set of l {\displaystyle l} relative coordinates. We can now obtain for each cell c {\displaystyle c} the tuple of its neighbors indices I c {\displaystyle I_{c}}
I c = { j ∣ ∃ x ∈ s : j = c + x } {\displaystyle I_{c}=\{j\mid \exists x\in s:j=c+x\}\,}
Their states are given by mapping the tuple I c {\displaystyle I_{c}} to the corresponding tuple of states N i ( c ) {\displaystyle N_{i}(c)} , where N i : I → S l {\displaystyle N_{i}\colon I\to S^{l}} is defined as follows:
N i ( c ) = ( s 1 , … , s l ) with s j = S i ( I c ( j ) ) {\displaystyle N_{i}(c)=(s_{1},\ldots ,s_{l}){\text{ with }}s_{j}=S_{i}(I_{c}(j))\,}
This is all we need to define the system's state for the following time steps S i + 1 : Z k → S {\displaystyle S_{i+1}\colon \mathbb {Z} ^{k}\to S} with i ∈ N {\displaystyle i\in \mathbb {N} } :
… excerpt ends here. Continue reading the full article.
