|
ALP User Documentation 0.7.alpha
Algebraic Programming User Documentation
|
ALP/GraphBLAS enables sparse linear algebraic programming. More...
Modules | |
| Data Ingestion and Extraction | |
| Provides functions for putting user data into opaque ALP/GraphBLAS containers, provides functions for extracting data from such containers, and provides query as well resizing functionalities. | |
| Level-0 Primitives | |
| A collection of functions that let GraphBLAS operators work on zero-dimensional containers, i.e., on scalars. | |
| Level-1 Primitives | |
| A collection of functions that allow ALP/GraphBLAS operators, monoids, and semirings work on a mix of zero-dimensional and one-dimensional containers; i.e., allows various linear algebra operations on scalars and objects of type grb::Vector. | |
| Level-2 Primitives | |
| A collection of functions that allow GraphBLAS operators, monoids, and semirings work on a mix of zero-dimensional, one-dimensional, and two-dimensional containers. | |
| Level-3 Primitives | |
| A collection of functions that allow GraphBLAS semirings to work on one or more two-dimensional sparse containers (i.e, sparse matrices). | |
ALP/GraphBLAS enables sparse linear algebraic programming.
ALP/GraphBLAS is an ANSI C++11 variant of the C GraphBLAS standard with a few different choices and an emphasis on portability and auto-parallelisation. It exposes only two containers: grb::Vector and grb::Matrix. A template argument controls the type of the values contained within a container.
A container may have between \( 0 \) and \( c \) values, and each such value has a coordinate. The value \( c \) is the capacity of a container, and at most equals the size of that container. The size of a matrix is the product of its number of rows and its number of columns. Containers with fewer values than their size are considered sparse, while those with as many values as their size are considered dense. Scalars correspond to the standard C++ plain-old-data types, and, as such, have size, capacity, and number of values equal to one– scalars are always dense.
For matrices, their size can be derived from grb::nrows and grb::ncols, while for vectors their size may be immediately retrieved via grb::size. For both vectors and matrices, their capacity and current number of values may be retrieved via grb::capacity and grb::nnz, respectively. Finally, containers have a unique identifier that may be retrieved via grb::getID. These identifiers are assigned in a deterministic fashion, so that for deterministic programs executed with the same number of processes, the same containers will be assigned the same IDs.
Containers may be populated using grb::set or by using dedicated I/O routines such as grb::buildVectorUnique or grb::buildMatrixUnique. Here, unique refers to the collection of values that should be ingested having no duplicate coordinates; i.e., there are no two values that map to the same coordinate. The first argument to either function is the output container, which is followed by an iterator pair that points to a collection of values to be ingested into the output container.
ALP/GraphBLAS supports multiple user processes \( P \). If \( P > 1 \), there is a difference between grb::SEQUENTIAL and grb::PARALLEL I/O. The default I/O mode is grb::PARALLEL, which may be overridden by supplying grb::SEQUENTIAL as a fourth and final argument to the input routines. In sequential I/O, the iterator pair must point to the exact same collection of input values on each of the \( P \) user processes. In the parallel mode, however, each iterator pair points to disjoint value sets at each of the processes, while their union is what is logically ingested into the output container.
Output iteration is done using the standard STL-style iterators. ALP, however, only supports const_iterators on output. Output iterators default to sequential mode also.
Primitives perform algebraic operations on containers while using explicitly supplied algebraic structures. Primitives may be as simple as the element-wise application of a binary operator to two input vectors, generating values in a third output vector ( \( z = x \odot y \), grb::eWiseApply), or may be as rich as multiplying two matrices together whose result is to be added in-place to a third matrix ( \( C \leftarrow C + AB \), grb::mxm). The latter is typically deemed richer since it requires a semiring structure rather than a more basic binary operator.
Primitives are grouped according to their classical BLAS levels:
The "level-0" primitives operate on scalars, and in terms of arithmetic intensity match those of level-1 primitives– however, since standard BLAS need not define scalar operations this specification groups them separately. All primitives except for grb::set and grb::eWiseApply are in-place, meaning that new output values are "added" to any pre-existing contents in output containers. The operator used for addition is derived from the algebraic structure that the primitive is called with.
ALP requires that every primitive is parallelisable. Every backend that implements primitive for a specific system furthermore must specify performance semantics. Contrary to functional semantics that this reference specifies, performance semantics guarantee certain observable behaviours when it comes to the amount of work, data movement, synchronisation across parallel systems, and/or memory use.
ALP/GraphBLAS defines three types of algebra structures, namely, a
Binary operators are parametrised in two input domains and one output domain, \( D_1 \times D_2 \to D_3 \). The \( D_i \) are given as template arguments to the operator. A grb::Monoid is composed from a binary operator coupled with an identity. For example, the additive monoid is defined as
Note that passing a single domain as a template argument to a binary operator is a short-hand for an operator with \( D_{\{1,2,3\}} \) equal to the same domain.
Likewise, a grb::Semiring is composed from two monoids, where the first, the so-called additive monoid, furthermore must be commutative. The classic semiring over integers taught in elementary school, for example, reads
Monoids and semirings must comply with their regular axioms– a type system assists users by checking for incorrect operators acting as additive or multiplicative monoids. Errors are reported at compile time, through the use of algebraic type traits such as grb::is_associative.
Standard operators and identities are found in their respective namespaces, grb::operators and grb::identities, respectively. The ALP monoids and semirings are generalised from their standard mathematical definitions in that they hold multiple domains. The description of grb::Semiring details the underlying mathematical structure that nevertheless can be identified.
An example is provided within examples/sp.cpp. It demonstrates usage of this API. We now follow with some code snippets from that example. First, the example dataset:
Matrix creation (5-by-5 matrix, 10 nonzeroes):
Vector creation:
Matrix assignment:
Vector assignment:
Example semiring definition:
Example semiring use:
Example function taking arbitrary semirings:
Example use of a function taking arbitrary semirings:
Full example use case:
1.9.6