DASH Concepts

Definitions

From the boost documentation:

Concept, Model, Refinement
A concept is a set of requirements consisting of valid expressions, associated types, invariants, and complexity guarantees.
A type that satisfies the requirements is said to model the concept. A concept can extend the requirements of another concept, which is called refinement.
Invariants
Run-time characteristics of the objects that must always be true, that is, the functions involving the objects must preserve these characteristics. The invariants often take the form of pre-conditions and post-conditions.
Traits

A traits class provides a way of associating information with a compile-time entity (a type, integral constant, or address). For example, the class template std::iterator_traits<T> looks something like this:

template <class Iterator>
struct iterator_traits {
  typedef ... iterator_category;
  typedef ... value_type;
  typedef ... difference_type;
  typedef ... pointer;
  typedef ... reference;
};
Policy Classes

A policy class is a template parameter used to transmit behavior. An example from the standard library is std::allocator, which supplies memory management behaviors to standard containers.
Policy classes have been explored in detail by Andrei Alexandrescu in this chapter of his book, Modern C++ Design.
He writes:

In brief, policy-based class design fosters assembling a class with complex behavior out of many little classes (called policies), each of which takes care of only one behavioral or structural aspect. As the name suggests, a policy establishes an interface pertaining to a specific issue. You can implement policies in various ways as long as you respect the policy interface.
Because you can mix and match policies, you can achieve a combinatorial set of behaviors by using a small core of elementary components.

System diagram illustrating interaction of concept types in dereferenciation of global container elements

System diagram illustrating interaction of concept types in dereferenciation of global container elements

References

  • Elements of Programming (Stepanov and McJones, 2009)

DASH Concept Definitions

Formal (as in: category theory) definitions are in the making, motivated by the need for a multidimensional range concept.

DASH Concepts (Interface Summary)

Dimensional

Value of a specific (possibly non-scalar) type in \(d\) dimensions. Does not define a space.

Method Signature Description Used in
Value operator[](dim_t d) Access to value in dimension \(d\), not range checked
Value dim(dim_t d) Access to value in dimension \(d\), range checked
dim_t ndim() Number of dimensions

DistributionSpec : Dimensional

Distribution types in \(d\) dimensions. Specialization of Dimensional for value type Distribution.

Method Signature Description Used in
bool is_tiled() Whether the DistributionSpec is tiled

CartesianSpace = SizeSpec

Extent of discrete cartesian space in \(d\) dimensions

Method Signature Description Used in
size_type extent(dim_t d) Extent in dimension \(d\)
void resize(size_type[d] extents) Resize cartesian space to given extents
size_type rank() The number of dimensions in the cartesian space with extent > 1
size_type num_dimensions() Number of dimensions \(d\)
size_type[d] extents() Extents of the cartesian space, ordered by dimension

CartesianIndexSpace : CartesianSpace

Cartesian space with canonical (row- or column-major) index

Method Signature Description Used in
size_type at(OffsetType[d] p) Linear canonical index of point \(p\)
index_type[d] coords(index_type i) Cartesian coordinates of linear canonical index \(i\), inverse of at

TeamSpec : CartesianSpace

Canonical indexed arrangement of units in \(d\)-dimensional cartesian space.
Redefines constructors of CartesianIndexSpace.

Pattern (TilePattern, BlockPattern)

Distribute a \(d\)-dimensional cartesian index space to units organized in a \(d\)-dimensional team spec.

Type name Description
index_type Integer denoting an offset in cartesian index space
size_type Integer denoting an extent in cartesian index space
Return Method Parameters Description
index_type at index[d] gp Linear offset of the global point \(gp\) in local memory
index_type local_at index[d] lp Linear local offset of the local point \(gp\) in local memory
dart_unit_t unit_at index[d] gp Unit id mapped to the element at global point \(p\)

global to local
{unit,index} local index gi Unit and linear local offset at the global index \(gi\)
{unit,index[d]} local index[d] gp Unit and local coordinates at the global point \(gp\)
{unit,index} local_index index[d] gp Unit and local linear offset at the global point \(gp\)
point[d] local_coords index[d] gp Local coordinates at the global point \(gp\)

local to global
index[d] global unit u, index[d] lp Local coordinates \(lp\) of unit \(u\) to global coordinates
index global_index unit u, index[d] lp Local coordinates \(lp\) of unit \(u\) to global index
index[d] global index[d] lp Local coordinates \(lp\) of active unit to global coordinates
index global unit u, index li Local offset \(li\) of unit \(u\) to global index
index global index li Local offset \(li\) of active unit to global index

blocks
viewspec block index gbi Offset and extent in global cartesian space of block at global block index \(gbi\)
viewspec local_block index lbi Offset and extent in global cartesian space of block at local block index \(lbi\)
viewspec local_block_local index lbi Offset and extent in local cartesian space of block at local block index \(lbi\)
bool is_local index gi, unit u Whether the global index \(gi\) is mapped to unit \(u\)
bool is_local dim d, index o, unit u Whether any element in dimension \(d\) at global offset \(o\) is local to unit \(u\)

size
size capacity Maximum number of elements in the pattern in total
size local_capacity Maximum number of elements assigned to a single unit
size size Number of elements indexed in the pattern
size local_size Number of elements local to the calling unit
size extent dim d Number of elements in the pattern in dimension \(d\)
size[d] local_extents unit u Number of elements local to the given unit, by dimension
size local_extent dim d) Number of elements local to the calling unit in dimension \(d\)

Pattern Iterator

Iterator on a pattern instance that returns the pattern coordinates when dereferenced. Pattern iterators advance to next linear position in global coordinate space.

Method Signature Description
pit_type ++operator Prefix increment
pit_type --operator Prefix decrement
pit_type operator++ Postfix increment
pit_type operator-- Postfix decrement
pit_type operator+= Offset increment
pit_type operator-= Offset decrement
pit_type operator[] Subscript operator
pos_proxy operator* Returns a proxy object providing members global(), local() and local_index
index[d] operator->global() Global coordinates at current position
index[d] operator->local() Local coordinates at given position
index operator->local_index() Local offset at given position

Pattern Block Iterator

Container

Distributed container.

Type name Description
index_type Integer denoting an offset in cartesian index space
size_type Integer denoting an extent in cartesian index space
local_type Proxy to local range of the container, must allow range-based iteration
pattern_type Pattern type used to distribute container elements, implements Pattern concept
Method Signature Description Used in
const pattern_type & pattern() Pattern used to distribute container elements Algorithms
local_type local Local range of the container, allows range-based iteration for (auto l : c.local)
GlobIter<Value> begin() Global iterator referencing the initial container element
GlobIter<Value> end() Global iterator referencing past the final container element
Value * lbegin() Native pointer to the initial local container element
Value * lend() Native pointer past the final local container element

Global Iterator / Pointer

Iterator on distributed container elements.

Conversions

Type Operator / Method Result type
GlobIter [] GlobRef
GlobIter * GlobRef
GlobIter (GlobPtr) GlobPtr
GlobPtr [] GlobRef
GlobPtr * GlobRef
GlobPtr (dart_gptr_t) dart_gptr_t
GlobRef gptr() GlobPtr
Type name Description
git_type Self-type of the concrete global iterator class
grf_type Global reference on element associated with global iterator object
Method Signature Description
git_type ++operator Prefix increment
git_type --operator Prefix decrement
git_type operator++ Postfix increment
git_type operator-- Postfix decrement
git_type operator+= Value increment
git_type operator-= Value decrement
git_type operator[] Subscript operator
grf_type operator* Dereference operator
bool is_local() Whether the referenced element is located in local memory

Global Asynchronous Reference

Global reference on an element that is fetched / put using non-blocking communication. An asynchronous reference is similar to the std::future concept but without a respective std::promise from the target side.

Method Signature Description