suitesparse.tex

\subsection{SuiteSparse:GraphBLAS}

SuiteSparse:GraphBLAS is the first full implementation of the GraphBLAS
standard, first released in November of 2017.
It is available at \url{http://suitesparse.com} \cite{Davis19}.

The design of a GraphBLAS library is flexible, because its data structures are
opaque to the user.  SuiteSparse:GraphBLAS uses a compressed-sparse vector
data structure, in four different forms.  A matrix can be stored in
row-major order (CSR), or column-major order (CSC).  Each sparse vector
consists of a sorted list of indices, and the corresponding numerical values.
The sparse vectors are packed together into two arrays, and another ``pointer
array'' (of size equal to the dimension of the matrix, say $n$) keeps track of
where each row (or column) starts.  The memory taken is $O(n+e)$ for a CSR
matrix with $n$ rows or a CSC matrix with $n$ columns, and with $e$ entries.
Most graphs have $e=O(n)$ entries, but some graphs (and in particular,
subgraphs) can be {\em hypersparse} \cite{BulucGilbert08}, with $e \ll n$.  In
the hypersparse form, the pointer array itself becomes sparse, and empty
vectors take no space at all.  The space is reduced to $O(e)$, so that
matrices with enormous dimensions can be created, as long as $e \ll n$.
SuiteSparse:GraphBLAS exploits hypersparsity automatically, and all
methods can operate on all four matrix formats in any combination.

The ability to incrementally modify a graph is critical in many applications.
GraphBLAS includes two operations that can make small incremental changes to a
graph/matrix:  namely \verb'GrB_setElement' and \verb'GrB_assign'.  It would be
exceedingly slow to insert or delete a single entry in a CSR or CSC format,
taking $O(n+e)$ time {\bf per entry} inserted or deleted.  Instead, the
non-blocking aspect of GraphBLAS is exploited.  Fast deletion of entries is
handled by creating {\em zombies}, which are entries tagged for later deletion.
Fast insertion is handled with {\em pending tuples}, which is a separate
unordered list of $(i,j,a_{ij})$ for each new entry.  When a matrix operation
occurs (such as matrix multiply), all zombies are killed and all pending tuples
are assembled, in a single $O(n+ e + p \log p)$ step (for $p$ pending tuples),
or $O(e +p \log p)$ in the hypersparse case.  As a result, it is just as fast
to use a sequence of $e$ \verb'GrB_Matrix_setElement' operations to build a matrix, as
it is to create an array of $e$ tuples and use \verb'GrB_Matrix_build'.  Internally,
SuiteSparse:GraphBLAS is building the list itself, for the user, and then does
a \verb'GrB_Matrix_build' when the matrix is completed.

To enable high-performance matrix-matrix multiply, a code generation mechanism
is used to build functions for each semiring that can be created with built-in
operators.  The functions can rely on Gustavson's method \cite{Gustavson78}, a
dot product method, and a heap-based method \cite{sisc3dspgemm}, all with
masked variants.  With this code generation mechanism, 6 functions
containing 2 versions of Gustavson's method (no mask / with mask),
three versions of the dot product (no mask / with mask / with complemented
mask) and one version of the heap method, automatically expand into the 960
unique semirings supported by the built-in operators in GraphBLAS
SuiteSparse:GraphBLAS adds a few extensions to the set of operators;
Using the  built-in types and operators from the GraphBLAS C API,
600 unique semirings can be constructed.  All of them are as fast, or much
faster, than \verb'C=A*B' in MATLAB.  Submatrix assignment (\verb'C(I,J)=A')
can be 100$\times$ faster than in MATLAB, even when non-blocking mode is not exploited.

A current prototype of the package adds an early exit
mechanism for the MIN, MAX, OR, and AND monoids, where a dot product can
terminate as soon as a terminal value is found in the result (\verb'true' for
OR, for example).  This will enable a fast direction-optimizing BFS
\cite{Beamer:2012:DOB} to be written in GraphBLAS.  The ``pull'' is a dot
product, and the ``push'' a saxpy-based operation (Gustavson's or the heap
method).

Since its creation was commissioned as the GraphBLAS reference implementation,
testing is a vital component to the package.  In SuiteSparse:GraphBLAS, each
GraphBLAS operation was written twice: once in high-performance algorithms in
C, and again in a very simple and short MATLAB script, using dense matrices
with the required type.  The pattern in the MATLAB version is held as a
separate Boolean matrix.  For example, \verb'GrB_assign' requires about 3,908
lines of C (not counting comments), but only 161 lines in MATLAB. Of those 161
lines, 33 are for error-checking that do not need to be considered when
determining conformance to the spec.  The MATLAB functions are not intended to
be fast.  Instead, they exactly mimic the GraphBLAS API Specification, line by
line, so they can be visually inspected for conformance to the spec.  For
example, matrix multiply is written with a brute-force triply-nested \verb'for'
loop.  Then, to test the package, each computation is done both in
SuiteSparse:GraphBLAS (via a MATLAB interface) and in the MATLAB mimic.  The
tests pass only if the results are identical in both value and pattern (even
with identical floating-point roundoff error, in most cases).

The package is extremely robust and production-ready.  It is fully compliant
with the GraphBLAS C API.  Excluding SuiteSparse-specific extensions and beta
releases, there have been only 3 bugs in the entire package since its first
release, two of which would be triggered in only rare cases.  All three bugs
are fixed, and the current version has no known bugs in any part of the code.

The current release is single-threaded, but an OpenMP implementation is in
progress.  SuiteSparse:GraphBLAS appears in Debian and Ubuntu Linux distros,
and has been released as part of the RedisGraph database module of the Redis
database systems, by RedisLabs, Inc. \cite{redisgraph}.