Stencil Codes - Definition

Definition

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 course of 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 with the following meaning:

• is the index set. It defines the topology of the array.
• is the (not necessarily finite) set of states, one of which each cell may take on on any given timestep.
• defines the initial state of the system at time 0.
• is the stencil itself and describes the actual shape of the neighborhood. (There are elements in the stencil.
• 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 . The stencil is an ordered set of relative coordinates. We can now obtain for each cell the tuple of its neighbors indices

Their states are given by mapping the tuple to the corresponding tuple of states, where is defined as follows:

This is all we need to define the system's state for the following time steps with :

Note that is defined on and not just on since the boundary conditions need to be set, too. Sometimes the elements of 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.