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:

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 with :

S_{i+1}(c) = \begin{cases}T(N_i(c)), & c \in I\\ S_i(c), & c \in \Z^k \setminus I \end{cases}

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:

I_c = \{j \mid \exists x \in s: j = ((c + x) \mod(n_1, \ldots, n_k))\}

This may be useful for implementing periodic boundary conditions, which simplifies certain physical models.

Read more about this topic:  Stencil Codes

Famous quotes containing the word definition:

    “The man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
    —William James (1842–1910)

    “Scientific method is the way to truth, but it affords, even in
    principle, no unique definition of truth. Any so-called pragmatic
    definition of truth is doomed to failure equally.”
    —Willard Van Orman Quine (b. 1908)

    “It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
    —François, Duc De La Rochefoucauld (1613–1680)