Array Building Blocks Types, Operators, and Functions

Array Building Blocks defines several data-types on which various overloaded operations and functions may be applied. Array Building Blocks provides data safety by default through isolation and deterministic patterns of parallelism. Array Building Blocks operates in a data space that is isolated from the native (C/C++) data space. Explicit operators are required to move data between native types and Array Building Blocks types. Array Building Blocks operators and types only affect the Array Building Blocks data space. This isolation allows Array Building Blocks to have full control over the allocation of its data.

Data races within Array Building Blocks are prevented through the use of deterministic patterns of computation such as map and reduce. General programs can be constructed by composing these deterministic patterns, a form of structured parallel programming. The resulting deterministic programs are much easier to maintain since data races and deadlocks are prevented by construction. In addition, the results computed by each of these patterns are consistent with a specific serial ordering, so one can reason about and debug a program specified with Array Building Blocks as if it executed serially. Of course it actually executes programs in parallel, and in fact can target both multiple cores and vector units simultaneously.

Array Building Blocks Types

Array Building Blocks primarily offers two kinds of built-in types: scalar types and containers. Developers can define other types based on these using C++'s class mechanism as usual. Common user-defined types such as small homogeneous arrays are provided by Array Building Blocks out of the box. Array Building Blocks also supports nested data parallelism, an advanced support of data parallelism that can support irregular computation, and is especially relevant to the construction of data structures. These nested parallel computations can transform seemingly irregular computations into regular and vectorizable computations.

To specify a computation using Array Building Blocks, it is necessary to express that computation over either scalar or container types provided by the system. The Array Building Blocks scalar types support integer (8/16/32/64 bits), floating-point (32/64 bits), and boolean values. Architecture-dependent integral types are also provided to store sizes, offsets, and similar values.

i32 aScalar;
f32 aFloatScalar;
i16 aSmallScalar;

Containers are also provided, and parallel operations are typically defined over entire containers using either direct expressions over entire containers or per-element functions. The most basic container is the dense array, which can be 1, 2, or 3 dimensional. The dimension and element type are given as template parameters. The element type can be any Array Building Blocks base type or a derived type, such as a struct, using such types as elements:

dense<ElementType, Dimensionality> aDenseContainer;

Specifying the dimensionality of a dense container can be omitted, which then results to a 1-dimensional dense container. Containers are managed and garbage collected by the Array Building Blocks runtime. In the following we give some examples using pseudo-code expressions of the following form:

dense<i8> foo = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

Nested containers are also supported, and are a generalization of the above that supports segments. The length of segments may be irregular, as follows:

nested<i32> nested_foo = {{0, 1, 2}, {3, 4}, {5, 6, 7, 8}, {9}};

Nested containers can be used to support various semi-regular applications such as graph data structures and sparse matrices.

Array Building Blocks types work naturally with other C++ types, such as user-defined classes or structs. It is possible to instantiate a dense container containing elements of a user-defined type, and even to overload operators on such types. Such types have a few restrictions: most notably, all scalars declared in such derived types must be Array Building Blocks types rather than the usual C++ scalar types. Functions (both member and free functions, including operator overloads) can be automatically made to work on containers of such types. The following snippet shows an example:

struct Point {
   f32 coordinates[3];
};
struct LineSegment {
    Point origin, end;
    boolean intersect(LineSegment s) const {
         // ...
    }
};
ARBB_ELTWISE_METHOD_1(boolean, const LineSegment, intersect, LineSegment); // ...
dense<LineSegment> A, B;
dense<boolean> results = intersect(A, B);

Here, the ARBB_ELTWISE_METHOD_1 macro registers a class method (member function) with Array Building Blocks so it can be applied to entire containers (working on single instances of the class still works as usual). This mechanism is only required when introducing a new function. When overloading an existing function, including all operator overloads, it is not needed.

Array Building Blocks also provides an arbb::array class template based on the C++ TR1 array class template. This type allows the simple construction of fixed-size, homogeneous arrays. In addition to the standard operations provided by the TR1 array type, Array Building Blocks arrays additionally provide element-wise, horizontal, and other useful operations:

arbb::array<f32, 3> a, b;
arbb::array<f32, 3> delta = b - a;
f32 distance = sqrt(sum(delta * delta));

Note that the second argument of the template is the length of the arbb::array type, and must be a compile-time constant.

Array Building Blocks also specializes the std::complex class to work naturally on Array Building Blocks's scalar types:

std::complex<f32> a, b, c;
c = a * b;
f32 d = abs(c);

Both the array type and the complex type are integrated into Array Building Blocks in the same way as user-defined types.

Array Building Blocks Operators

Array Building Blocks provides a rich and expressive set of operations for performing parallel computation over containers. Broadly, these operations fall into five categories.

• Element-wise operations provide basic element-by-element parallel operations on containers. Shown below is an example for addition of two containers:

      dense<f32> A = B + C; // add B and C, put result in A

• Collective operations provide a set of commonly used patterns for operating on entire containers. For example, an add_reduce operation can be used to return the sum of all the elements of a container, collapsing it by one dimension at a time. A prefix-sum (also known as a "scan") performs a similar operation as a reduction but retains partial reductions each element of the sequence. Both inclusive and exclusive scans are supported: in an inclusive scan, the current element is included in the reduction. Below are some examples, given in pseudocode, acting on a nested collection:

      add_scan({{1, 2, 3}, {4, 5}, {6}}) 
        => {6, 9, 6}
      add_scan({{1, 2, 3}, {4, 5}, {6}}) 
        => {{0, 1, 3}, {0, 4}, {0}}
      add_iscan({{1, 2, 3}, {4, 5}, {6}}) 
        => {{1, 3, 6}, {4, 9}, {6}}

• Permutation operations provide a mechanism for reordering (and replicating) the values in a container. For example, gather will create a new vector out of a vector of values using an index vector to specify the location of a set of parallel read operations.
• Facilities operations provide manipulation, creation, copying and concatenation mechanisms for containers. For example, the cat operation takes two containers and returns a new container that is a concatenation of both.
• Data access operations create an association between C/C++ variables and Array Building Blocks variables. Containers provide functions to obtain non-Array Building Blocks iterators (using a range interface) over their data that can be used directly in C++ code. Array Building Blocks containers can also be associated with existing C++ data using bind functions.

      float data [N];
      dense<f32> mapped(N);
      dense<f32>::iterator I = mapped.read_write_range().begin();
      std::copy(data, data + N, I);
      dense<f32> bound;
	bind(bound, data, N);