Halide
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Halide::RDom Class Reference

A multi-dimensional domain over which to iterate. More...

#include <RDom.h>

Public Member Functions

EXPORT RDom ()
 Construct an undefined reduction domain. More...
 
EXPORT RDom (Internal::ReductionDomain d)
 Construct a reduction domain that wraps an Internal ReductionDomain object. More...
 
Internal::ReductionDomain domain () const
 Get at the internal reduction domain object that this wraps. More...
 
bool defined () const
 Check if this reduction domain is non-null. More...
 
bool same_as (const RDom &other) const
 Compare two reduction domains for equality of reference. More...
 
EXPORT int dimensions () const
 Get the dimensionality of a reduction domain. More...
 
EXPORT RVar operator[] (int) const
 Get at one of the dimensions of the reduction domain. More...
 
EXPORT operator RVar () const
 Single-dimensional reduction domains can be used as RVars directly. More...
 
EXPORT operator Expr () const
 Single-dimensional reduction domains can be also be used as Exprs directly. More...
 
EXPORT void where (Expr predicate)
 Add a predicate to the RDom. More...
 
NO_INLINE RDom (const std::vector< std::pair< Expr, Expr >> &ranges, std::string name="")
 Construct a multi-dimensional reduction domain with the given name. More...
 
template<typename... Args>
NO_INLINE RDom (Expr min, Expr extent, Args &&...args)
 Construct a multi-dimensional reduction domain with the given name. More...
 
EXPORT RDom (const Image<> &)
 Construct a reduction domain that iterates over all points in a given Buffer or ImageParam. More...
 
EXPORT RDom (ImageParam)
 Construct a reduction domain that iterates over all points in a given Buffer or ImageParam. More...
 
template<typename T , int D>
NO_INLINE RDom (const Image< T, D > &im)
 Construct a reduction domain that iterates over all points in a given Buffer or ImageParam. More...
 

Public Attributes

RVar x
 Direct access to the first four dimensions of the reduction domain. More...
 
RVar y
 Direct access to the first four dimensions of the reduction domain. More...
 
RVar z
 Direct access to the first four dimensions of the reduction domain. More...
 
RVar w
 Direct access to the first four dimensions of the reduction domain. More...
 

Detailed Description

A multi-dimensional domain over which to iterate.

Used when defining functions with update definitions.

An reduction is a function with a two-part definition. It has an initial value, which looks much like a pure function, and an update definition, which may refer to some RDom. Evaluating such a function first initializes it over the required domain (which is inferred based on usage), and then runs update rule for all points in the RDom. For example:

Func f;
Var x;
RDom r(0, 10);
f(x) = x; // the initial value
f(r) = f(r) * 2;
Image<int> result = f.realize(10);

This function creates a single-dimensional buffer of size 10, in which element x contains the value x*2. Internally, first the initialization rule fills in x at every site, and then the update definition doubles every site.

One use of reductions is to build a function recursively (pure functions in halide cannot be recursive). For example, this function fills in an array with the first 20 fibonacci numbers:

Func f;
Var x;
RDom r(2, 18);
f(x) = 1;
f(r) = f(r-1) + f(r-2);

Another use of reductions is to perform scattering operations, as unlike a pure function declaration, the left-hand-side of an update definition may contain general expressions:

ImageParam input(UInt(8), 2);
Func histogram;
Var x;
RDom r(input); // Iterate over all pixels in the input
histogram(x) = 0;
histogram(input(r.x, r.y)) = histogram(input(r.x, r.y)) + 1;

An update definition may also be multi-dimensional. This example computes a summed-area table by first summing horizontally and then vertically:

ImageParam input(Float(32), 2);
Func sum_x, sum_y;
Var x, y;
RDom r(input);
sum_x(x, y) = input(x, y);
sum_x(r.x, r.y) = sum_x(r.x, r.y) + sum_x(r.x-1, r.y);
sum_y(x, y) = sum_x(x, y);
sum_y(r.x, r.y) = sum_y(r.x, r.y) + sum_y(r.x, r.y-1);

You can also mix pure dimensions with reduction variables. In the previous example, note that there's no need for the y coordinate in sum_x to be traversed serially. The sum within each row is entirely independent. The rows could be computed in parallel, or in a different order, without changing the meaning. Therefore, we can instead write this definition as follows:

ImageParam input(Float(32), 2);
Func sum_x, sum_y;
Var x, y;
RDom r(input);
sum_x(x, y) = input(x, y);
sum_x(r.x, y) = sum_x(r.x, y) + sum_x(r.x-1, y);
sum_y(x, y) = sum_x(x, y);
sum_y(x, r.y) = sum_y(x, r.y) + sum_y(x, r.y-1);

This lets us schedule it more flexibly. You can now parallelize the update step of sum_x over y by calling:

sum_x.update().parallel(y).

Note that calling sum_x.parallel(y) only parallelizes the initialization step, and not the update step! Scheduling the update step of a reduction must be done using the handle returned by Func::update(). This code parallelizes both the initialization step and the update step:

sum_x.parallel(y);
sum_x.update().parallel(y);

When you mix reduction variables and pure dimensions, the reduction domain is traversed outermost. That is, for each point in the reduction domain, the inferred pure domain is traversed in its entirety. For the above example, this means that sum_x walks down the columns, and sum_y walks along the rows. This may not be cache-coherent. You may try reordering these dimensions using the schedule, but Halide will return an error if it decides that this risks changing the meaning of your function. The solution lies in clever scheduling. If we say:

sum_x.compute_at(sum_y, y);

Then the sum in x is computed only as necessary for each scanline of the sum in y. This not only results in sum_x walking along the rows, it also improves the locality of the entire pipeline.

Examples:
tutorial/lesson_09_update_definitions.cpp, and tutorial/lesson_13_tuples.cpp.

Definition at line 179 of file RDom.h.

Constructor & Destructor Documentation

EXPORT Halide::RDom::RDom ( )
inline

Construct an undefined reduction domain.

Definition at line 194 of file RDom.h.

NO_INLINE Halide::RDom::RDom ( const std::vector< std::pair< Expr, Expr >> &  ranges,
std::string  name = "" 
)
inline

Construct a multi-dimensional reduction domain with the given name.

If the name is left blank, a unique one is auto-generated.

Definition at line 199 of file RDom.h.

template<typename... Args>
NO_INLINE Halide::RDom::RDom ( Expr  min,
Expr  extent,
Args &&...  args 
)
inline

Construct a multi-dimensional reduction domain with the given name.

If the name is left blank, a unique one is auto-generated.

Definition at line 204 of file RDom.h.

EXPORT Halide::RDom::RDom ( const Image<> &  )

Construct a reduction domain that iterates over all points in a given Buffer or ImageParam.

Has the same dimensionality as the argument.

EXPORT Halide::RDom::RDom ( ImageParam  )

Construct a reduction domain that iterates over all points in a given Buffer or ImageParam.

Has the same dimensionality as the argument.

template<typename T , int D>
NO_INLINE Halide::RDom::RDom ( const Image< T, D > &  im)
inline

Construct a reduction domain that iterates over all points in a given Buffer or ImageParam.

Has the same dimensionality as the argument.

Definition at line 219 of file RDom.h.

EXPORT Halide::RDom::RDom ( Internal::ReductionDomain  d)

Construct a reduction domain that wraps an Internal ReductionDomain object.

Member Function Documentation

Internal::ReductionDomain Halide::RDom::domain ( ) const
inline

Get at the internal reduction domain object that this wraps.

Definition at line 226 of file RDom.h.

bool Halide::RDom::defined ( ) const
inline

Check if this reduction domain is non-null.

Definition at line 229 of file RDom.h.

References Halide::Internal::ReductionDomain::defined().

bool Halide::RDom::same_as ( const RDom other) const
inline

Compare two reduction domains for equality of reference.

Definition at line 232 of file RDom.h.

References Halide::Internal::ReductionDomain::same_as().

EXPORT int Halide::RDom::dimensions ( ) const

Get the dimensionality of a reduction domain.

EXPORT RVar Halide::RDom::operator[] ( int  ) const

Get at one of the dimensions of the reduction domain.

EXPORT Halide::RDom::operator RVar ( ) const

Single-dimensional reduction domains can be used as RVars directly.

EXPORT Halide::RDom::operator Expr ( ) const

Single-dimensional reduction domains can be also be used as Exprs directly.

EXPORT void Halide::RDom::where ( Expr  predicate)

Add a predicate to the RDom.

An RDom may have multiple predicates associated with it. An update definition that uses an RDom only iterates over the subset points in the domain for which all of its predicates are true. The predicate expression obeys the same rules as the expressions used on the right-hand-side of the corresponding update definition. It may refer to the RDom's variables and free variables in the Func's update definition. It may include calls to other Funcs, or make recursive calls to the same Func. This permits iteration over non-rectangular domains, or domains with sizes that vary with some free variable, or domains with shapes determined by some other Func.

Note that once RDom is used in the update definition of some Func, no new predicates can be added to the RDom.

Consider a simple example:

RDom r(0, 20, 0, 20);
r.where(r.x < r.y);
r.where(r.x == 10);
r.where(r.y > 13);
f(r.x, r.y) += 1;

This is equivalent to:

for (int r.y = 0; r.y < 20; r.y++) {
if (r.y > 13) {
for (int r.x = 0; r.x < 20; r.x++) {
if (r.x == 10) {
if (r.x < r.y) {
f[r.x, r.y] += 1;
}
}
}
}
}

Where possible Halide restricts the range of the containing for loops to avoid the cases where the predicate is false so that the if statement can be removed entirely. The case above would be further simplified into:

for (int r.y = 14; r.y < 20; r.y++) {
f[r.x, r.y] += 1;
}

In general, the predicates that we can simplify away by restricting loop ranges are inequalities that compare an inner Var or RVar to some expression in outer Vars or RVars.

You can also pack multiple conditions into one predicate like so:

RDom r(0, 20, 0, 20);
r.where((r.x < r.y) && (r.x == 10) && (r.y > 13));
f(r.x, r.y) += 1;

Member Data Documentation

RVar Halide::RDom::x

Direct access to the first four dimensions of the reduction domain.

Some of these variables may be undefined if the reduction domain has fewer than four dimensions.

Examples:
tutorial/lesson_09_update_definitions.cpp.

Definition at line 315 of file RDom.h.

RVar Halide::RDom::y

Direct access to the first four dimensions of the reduction domain.

Some of these variables may be undefined if the reduction domain has fewer than four dimensions.

Examples:
tutorial/lesson_09_update_definitions.cpp.

Definition at line 315 of file RDom.h.

RVar Halide::RDom::z

Direct access to the first four dimensions of the reduction domain.

Some of these variables may be undefined if the reduction domain has fewer than four dimensions.

Definition at line 315 of file RDom.h.

RVar Halide::RDom::w

Direct access to the first four dimensions of the reduction domain.

Some of these variables may be undefined if the reduction domain has fewer than four dimensions.

Definition at line 315 of file RDom.h.


The documentation for this class was generated from the following file: