devito.ir.support package

Submodules

devito.ir.support.basic module

class devito.ir.support.basic.Vector[source]

Bases: tuple

A representation of a vector in Z^n.

The elements of a Vector can be integers or any SymPy expression.

If a comparison between a vector and a non-vector is attempted, then the non-vector is promoted to a vector; if this is not possible, an exception is raised. This is handy because it turns a vector-scalar comparison into a vector-vector comparison with the scalar broadcasted to all vector entries. For example:

(3, 4, 5) > 4 => (3, 4, 5) > (4, 4, 4) => False

When we compare two entries that are both generic SymPy expressions, it is generally not possible to determine the truth value of the relation. For example, the truth value of 3*i < 4*j cannot be determined. In some cases, however, the comparison is feasible; for example, i + 4 < i should always return false. A sufficient condition for two Vectors to be comparable is that their pair-wise indices are affine functions of the same variables, with coefficient 1.

distance(other)[source]

Compute the distance from self to other.

The distance is a reflexive, transitive, and anti-symmetric relation, which establishes a total ordering amongst Vectors.

The distance is a function [Vector x Vector –> D]. D is a tuple of length equal to the Vector rank. The i-th entry of D, D_i, indicates whether the i-th component of self, self_i, precedes (< 0), equals (== 0), or succeeds (> 0) the i-th component of other, other_i.

In particular, the absolute value of D_i represents the number of integer points that exist between self_i and sink_i.

3 | | 1 | | 2 |
source = | 2 | , sink = | 4 | , distance => | -2 |
1 | | 5 | | -4 |

There are 2, 2, and 4 points between [3-2], [2-4], and [1-5], respectively.

rank
sum
class devito.ir.support.basic.IterationInstance[source]

Bases: devito.ir.support.basic.Vector

A representation of the iteration and data points accessed by an Indexed object. Three different concepts are distinguished:

  • Index functions: the expressions telling what iteration space point is accessed.
  • aindices: the :class:`Dimension`s acting as iteration variables. There is one aindex for each index function. If the index function is non-affine, then it may not be possible to detect its aindex; in such a case, None is used as placeholder.
  • findices: the :class:`Dimension`s telling what data space point is accessed.
affine(findices)[source]

Return True if all of the provided findices appear in self and are affine, False otherwise.

affine_if_present(findices)[source]

Return False if any of the provided findices appears in self and is not affine, True otherwise.

aindices
distance(other, findex=None, view=None)[source]

Compute the distance from self to other.

Parameters:
  • other – The IterationInstance from which the distance is computed.
  • findex – (Optional) if supplied, compute the distance only up to and including findex (defaults to None).
  • view – (Optional) an iterable of findices (defaults to None); if supplied, project the distance along these dimensions.
findices_affine
findices_irregular
index_mode
irregular(findices)[source]

Return True if all of the provided findices appear in self and are irregular, False otherwise.

is_irregular
is_regular
is_scalar
section(findices)[source]

Return a view of self in which the slots corresponding to the provided findices have been zeroed.

touch_halo(findices)[source]

Return True if self accesses the halo along any of the provided findices, False otherwise.

class devito.ir.support.basic.Access[source]

Bases: devito.ir.support.basic.IterationInstance

A representation of the access performed by a Indexed object (a scalar in the degenerate case).

The comparison operators ==, !=, <, <=, >, >= should be regarded as operators for lexicographic ordering of Access objects, based on the values of the index functions (and the index functions only).

For example, if two Access objects A and B employ the same index functions, the operation A == B will return True regardless of whether A and B are reads or writes or mixed.

is_increment
is_local
is_read
is_read_increment
is_write
is_write_increment
name
class devito.ir.support.basic.TimedAccess[source]

Bases: devito.ir.support.basic.Access

A special Access object enriched with:

* a "timestamp"; that is, an integer indicating the access location
  within the execution flow;
* an array of directions; there is one direction for each index,
  indicating whether the index function is monotonically increasing
  or decreasing.

Further, a TimedAccess may be regular or irregular. A TimedAccess is regular if and only if all index functions are affine in their respective findex. The downside of irregular TimedAccess objects is that dependence testing is harder, which in turn may force the data dependence analyzer to make stronger assumptions to be conservative.

Given: findices = [x, y, z] w = an object of type Dimension

x+1 | | x | | x | | w | | x+y |
obj1 = | y+2 | , obj2 = | 4 | , obj3 => | x | , obj4 = | y | , obj5 = | y |
z-3 | | z+1 | | y | | z | | z |

We have that:

* obj1 and obj2 are regular;
* obj3 is irregular because an findex, ``x``, appears outside of its index
  function (i.e., in the second slot, whew ``y`` is expected);
* obj4 is irregular, because a different dimension, ``w``, is used in place
  of ``x`` within the first index function, where ``x`` is expected;
* obj5 is irregular, as two findices appear in the same index function --
  the one in the first slot, where only ``x`` is expected.
distance(other, findex=None)[source]

Compute the distance from self to other.

Parameters:
  • other – The IterationInstance from which the distance is computed.
  • findex – (Optional) if supplied, compute the distance only up to and including findex (defaults to None).
  • view – (Optional) an iterable of findices (defaults to None); if supplied, project the distance along these dimensions.
lex_eq(other)[source]
lex_ge(other)[source]
lex_gt(other)[source]
lex_le(other)[source]
lex_lt(other)[source]
lex_ne(other)[source]
class devito.ir.support.basic.Scope(exprs)[source]

Bases: object

accesses
d_all

Retrieve all flow, anti, and output dependences.

d_anti

Retrieve the anti dependencies, or write-after-read.

d_flow

Retrieve the flow dependencies, or true dependencies, or read-after-write.

d_output

Retrieve the output dependencies, or write-after-write.

getreads(function)[source]
getwrites(function)[source]
has_dep

Return True if at least a dependency is detected, False otherwise.

devito.ir.support.space module

class devito.ir.support.space.NullInterval(dim)[source]

Bases: devito.ir.support.space.AbstractInterval

is_Null = True
merge(o)
overlap(o)[source]
union(o)[source]
class devito.ir.support.space.Interval(dim, lower, upper)[source]

Bases: devito.ir.support.space.AbstractInterval

Create an Interval of extent:

dim.extent + abs(upper - lower)
add(o)[source]
flip()[source]
intersection(o)[source]
is_Defined = True
limits
merge(o)[source]
negate()[source]
overlap(o)[source]
subtract(o)[source]
union(o)[source]
zero()[source]
class devito.ir.support.space.IntervalGroup[source]

Bases: devito.tools.data_structures.PartialOrderTuple

A partially-ordered sequence of :class:`Interval`s with set-like operations exposed.

add(o)[source]
dimensions
drop(d)[source]
extent
classmethod generate(op, *interval_groups)[source]

Create a new IntervalGroup from the iterative application of the operation op to the IntervalGroup`s in ``interval_groups`.

Parameters:
  • op – Any legal Interval operation, such as intersection or union. This should be provided as a string.
  • interval_groups – An iterable of :class:`IntervalGroup`s.

ig0 = IntervalGroup([Interval(x, 1, -1)]) ig1 = IntervalGroup([Interval(x, 2, -2), Interval(y, 3, -3)]) ig2 = IntervalGroup([Interval(y, 2, -2), Interval(z, 1, -1)])

ret = IntervalGroup.generate(‘intersection’, ig0, ig1, ig2) ret -> IntervalGroup([Interval(x, 2, -2), Interval(y, 3, -3), Interval(z, 1, -1)])

intersection(o)[source]
is_well_defined

Return True if all :class:`Interval`s are over different :class:`Dimension`s, False otherwise.

negate()[source]
classmethod reorder(items, relations)[source]
shape
subtract(o)[source]
zero(d=None)[source]
class devito.ir.support.space.IterationSpace(intervals, sub_iterators=None, directions=None)[source]

Bases: devito.ir.support.space.Space

A representation of an iteration space and its traversal through :class:`Interval`s and :class:`IterationDirection`s. For each interval, an arbitrary number of (sub-)iterators may be specified (see below).

Parameters:
  • intervals – An ordered sequence of :class:`Interval`s defining the iteration space.
  • sub_iterators – (Optional) a mapper from Dimension`s in ``intervals` to iterables of DerivedDimension, which represent sub-dimensions along which the iteration space is traversed.
  • directions – (Optional) a mapper from Dimension`s in ``intervals` to :class:`IterationDirection`s.
args
dimensions
directions
is_compatible(other)[source]

A relaxed version of __eq__, in which only non-derived dimensions are compared for equality.

is_forward(dim)[source]
itintervals
classmethod merge(*others)[source]
nonderived_directions
project(cond)[source]

Return a new IterationSpace in which only some Dimension`s in ``self` are retained. In particular, a dimension d in self is retained if:

* either ``cond(d)`` is true (``cond`` is a callable),
* or ``d in cond`` is true (``cond`` is an iterable)
sub_iterators
class devito.ir.support.space.DataSpace(intervals, parts)[source]

Bases: devito.ir.support.space.Space

A representation of a data space.

Parameters:
  • intervals – A sequence of :class:`Interval`s describing the data space.
  • parts – A mapper from Function`s to iterables of :class:`Interval describing the individual components of the data space.
classmethod merge(*others)[source]
parts
zero(d=None)[source]
devito.ir.support.space.Forward = ++

Forward iteration direction (‘++’).

devito.ir.support.space.Backward = --

Backward iteration direction (‘–’).

devito.ir.support.space.Any = *

Wildcard direction (both ‘++’ and ‘–’ would be OK).

devito.ir.support.stencil module

class devito.ir.support.stencil.Stencil(entries=None)[source]

Bases: devito.tools.data_structures.DefaultOrderedDict

A Stencil is a mapping from Dimension symbols to the set of integer offsets used with it in expressions (the “neighboring points accessed”).

This also include zero offsets.

The mapping is ordered based on the order in which dimensions are encountered (if extracted from expressions) or inserted.

Note: Expressions must have been indexified for a Stencil to be computed.

add(o)[source]

Compute the set union of each Dimension in self with the corresponding Dimension in o.

copy()[source]

Return a deep copy of the Stencil.

diameter
dimensions
empty
entries
entry(k)[source]
get(k[, d]) → D[k] if k in D, else d. d defaults to None.[source]
prefix(o)[source]

Return the common prefix of self and o as a new Stencil.

subtract(o)[source]

Compute the set difference of each Dimension in self with the corresponding Dimension in o.

classmethod union(*dicts)[source]

Compute the union of an iterable of Stencil objects.

devito.ir.support.utils module

devito.ir.support.utils.detect_accesses(expr)[source]

Return a mapper M : F -> S, where F are Function`s appearing in ``expr` and S are Stencil`s. ``M[f]` represents all data accesses to f within expr. Also map M[None] to all Dimensions used in expr as plain symbols, rather than as array indices.

devito.ir.support.utils.detect_oobs(mapper)[source]

Given M as produced by detect_accesses(), return the set of :class:`Dimension`s that cannot be iterated over for the entire computational domain, to avoid out-of-bounds (OOB) accesses.

devito.ir.support.utils.build_iterators(mapper)[source]

Given M as produced by detect_accesses(), return a mapper M' : D -> V, where D is the set of Dimension`s in M, and V is a set of :class:`DerivedDimension`s. M'[d] provides the sub-iterators along the Dimension `d.

devito.ir.support.utils.build_intervals(stencil)[source]

Given a Stencil, return an iterable of Interval`s, one for each :class:`Dimension in the stencil.

devito.ir.support.utils.detect_flow_directions(exprs)[source]

Return a mapper from Dimension`s to iterables of :class:`IterationDirection`s representing the theoretically necessary directions to evaluate ``exprs` so that the information “naturally flows” from an iteration to another.

devito.ir.support.utils.force_directions(mapper, key)[source]

Return a mapper M : D -> I where D is the set of Dimension`s found in the input mapper ``M' : D -> {I}`, while I = {Any, Backward, Forward} (i.e., the set of possible :class:`IterationDirection`s).

The iteration direction is chosen so that the information “naturally flows” from an iteration to another (i.e., to generate “flow” or “read-after-write” dependencies).

In the case of a clash (e.g., both Forward and Backward should be used for a given dimension in order to have a flow dependence), the function key : D -> I is used to pick one value.

devito.ir.support.utils.group_expressions(exprs)[source]

{exprs} -> ({exprs'}, {exprs''}, ...) where:

* There are data dependences within exprs' and within exprs'';
* There are *no* data dependencies across exprs' and exprs''.
devito.ir.support.utils.align_accesses(expr, key=<function <lambda>>)[source]

expr -> expr', with expr' semantically equivalent to expr, but with data accesses aligned to the computational domain if key(function) gives True.

devito.ir.support.utils.detect_io(exprs, relax=False)[source]

``{exprs} -> ({reads}, {writes})

Parameters:
  • exprs – The expressions inspected.
  • relax – (Optional) if False, as by default, collect only :class:`Constant`s and :class:`Function`s. Otherwise, collect any :class:`Basic`s.

Module contents