Stencil code

Stencil codes are a class of iterative kernelswhich update array elements according to some fixed pattern, called a stencil. They are most commonly found in the codes of 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 codes apart from other modeling methods such as the Finite element method. Most finite difference codes which operate on regular grids can be formulated as stencil codes. Stencil codes are a class of iterative kernelswhich update array elements according to some fixed pattern, called a stencil. They are most commonly found in the codes of 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 codes apart from other modeling methods such as the Finite element method. Most finite difference codes which operate on regular grids can be formulated as stencil codes. Stencil codes 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, the stencil code updates all array elements. Using neighboring array elements in a fixed pattern (called 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 stencil codes as a 5-tuple ( I , S , S 0 , s , T ) {displaystyle (I,S,S_{0},s,T)} with the following meaning: 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 cin 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}} 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 o S^{l}} is defined as follows: 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} o S} with i ∈ N {displaystyle iin mathbb {N} } : Note that S i {displaystyle S_{i}} is defined on Z k {displaystyle mathbb {Z} ^{k}} and not just on I {displaystyle I} since the boundary conditions need to be set, too. Sometimes the elements of I c {displaystyle I_{c}} may be defined by a vector addition modulo the simulation space's dimension to realize toroidal topologies: This may be useful for implementing periodic boundary conditions, which simplifies certain physical models. To illustrate the formal definition, we'll have a look at how a two dimensional Jacobi iteration can be defined. The update function computes the arithmetic mean of a cell's four neighbors. In this case we set off with an initial solution of 0. The left and right boundary are fixed at 1, while the upper and lower boundaries are set to 0. After a sufficient number of iterations, the system converges against a saddle-shape.