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:

    “Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
    —Walter Pater (1839–1894)

    “... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
    —Adrienne Rich (b. 1929)

    “The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
    —Jean Baudrillard (b. 1929)