disc.tex

\section{Discussion}
\label{sec:disc}

We are early in the LAGraph project.  At this point, we've defined the basic structure of the
repository and the overall goals of the project. We have built an early framework for testing
and core utility routines to support software development.  Finally, we assembled a few algorithms which we
are using to test the basic structure of the software system.

Even at this early phase of the project, we have learned a great deal about how the GraphBLAS
will interact with end-users.  The objects manipulated by the GraphBLAS are opaque.  A 
GraphBLAS implementation is given
complete freedom in how data structures underlying the GraphBLAS are implemented.  
A graph algorithm, however, uses GraphBLAS as part of a processing pipeline.  For example, data may
exist in data frames.  A subset of the data is collected and filtered to produce relationships
represented by a graph. Properties of the graph are computed and based on the result 
a new branch in the processing pipeline may be accessed.  

The key here is that graphs inside the GraphBLAS are opaque, but externally they are 
anything but opaque.  This suggests that we need to define functions to import and export 
data in standard sparse array formats into LAGraph.   The initial thinking was that this
import functionality would be part of LAGraph and not the GraphBLAS.  The only way to 
do that, however, is if we repacked the input sparse format into separate arrays for column 
indices, row indices, and values and then use \verb'GrB_Matrix_build' to construct the GraphBLAS
matrix object.  This is extremely inefficient.  We need a way to directly import arrays 
in standard sparse formats, such as CSR/CSC (Compressed Sparse Row/Column) formats,
into the GraphBLAS and since the GraphBLAS data types are
opaque, this can only be done as a GraphBLAS routine.  

Graph algorithms do not occur in isolation.   The LAGraph library, therefore, needs to 
return a handle to an opaque GraphBLAS object so it can be used without incurring copy overhead
in subsequent graph operations.  Given the nonblocking execution model, this raises interesting
design questions about how memory consistency between the library and the application is
managed.  

Graphs can be quite large.   Hence, the default mode should avoid copying 
sparse arrays input to LAGraph into a separate memory region to hold the 
opaque GraphBLAS object.  We believe it is important that the memory for the input array
be reused to hold the GraphBLAS object as much as possible. 
This means the input array is often ``destroyed''
(from the perspective of LAGraph, another external library, or the user application)
and ``realloc''ed for the GraphBLAS opaque object.
% the GraphBLAS routines will in some cases need to allocate additional memory during a 
% calculation.  
% This may require deallocating memory and reallocating a larger block of memory.
% This means we will likely encounter situations where a region of memory allocated in an application
% is deallocated inside a library routine.
In the interest of performance and efficient use of memory resources, 
the above violates the separation of concerns between application
and library code expected in well engineered software. 
There is also the question of communicating
to the library routine how the input sparse array was allocated in the first place so the right deallocator 
can be used.

A draft of SuiteSparse:GraphBLAS includes a working and fully-tested
implementation of the import/export feature, using a strategy much like the
``move constructor'' of C++.  For the export of a CSC matrix, for example,
three arrays are removed from the GraphBLAS matrix \verb'A': a pointer array
\verb'Ap' of size \verb'n+1', an index array \verb'Ai' of size \verb'e', and a
values array \verb'Ax'.  The row indices of the  \verb'j'th column of the
matrix appear as the list \verb'Ai[Ap[j]...Ap[j+1]]', and the values are in the
same locations in \verb'Ax'.  This format is identical to the simple CSC sparse
matrix data structure in CSparse \cite{Davis06book}, except that GraphBLAS
allows for many built-in types and arbitrary user-defined types.

The remains of the GraphBLAS object \verb'A' are then deleted, but all of its
content is now ``owned'' by the external library (LAGraph, say), which is then
responsible for freeing these three arrays.  Assuming that the opaque GraphBLAS
object \verb'A' is already in the CSC format, the export takes just $O(1)$
time, and no new memory is allocated.  The external library (LAGraph, in
particular) now has access to the graph.  If the GraphBLAS implementation does
not support the CSC format in its internal opaque data structure, it can
allocate these arrays, populate them, and then free \verb'A'.  The effect is
the same; only the performance differs.  Opacity is maintained, while at the
same time reducing time required for the export from $\Omega(e)$ (for
\verb'GrB_extractTuples') to as little as $O(1)$.

The import is symmetric with the export:  LAGraph (or any other external
library) passes in the three arrays \verb'Ap', \verb'Ai', and \verb'Ax', which
are then either incorporated as-is into the \verb'GrB_Matrix A' (taking $O(1)$
time), or copied and freed (taking $O(e)$ time and memory).  Either way, the
three arrays are now owned by GraphBLAS, not the external library, and would be
freed at some point no later than \verb'GrB_free(&A)'.  Since the matrix
\verb'A' is opaque, the GraphBLAS library can select whatever method it chooses
to take ownership of \verb'Ap', \verb'Ai', and \verb'Ax': a copy (in $O(e)$
time, or a move construction in $O(1)$ time.  It may choose later to
\verb'realloc' these arrays if the number of entries needs to grow.

After an export of \verb'A', and then an import of the same arrays, the
GraphBLAS matrix \verb'A' is perfectly reconstructed, ideally in a total of
$O(1)$ time.  SuiteSparse:GraphBLAS supports the import/export of all four of
its formats: CSR, CSC, and their hypersparse variants.

A \verb'malloc' of these \verb'Ap', \verb'Ai', and \verb'Ax' arrays by an
external library followed by freeing the same space inside GraphBLAS with
\verb'GrB_free(&A)' requires both libraries to agree on using the same
\verb'malloc/free' routines.  To do this, the GraphBLAS API would need to be
augmented to allow an external library to select which \verb'malloc/free'
routines should be used.  This is essential for a MATLAB interface,
since a MATLAB \verb'mexFunction' must use \verb'mxMalloc' and \verb'mxFree'.
With the import/export feature, sparse matrices can be passed between MATLAB
and GraphBLAS in $O(1)$ time, unless typecasting is required. MATLAB supports
all of the built-in types of GraphBLAS, plus \verb'double complex', but only
for dense matrices.  For sparse matrices in MATLAB, only \verb'double' and
\verb'double complex' are available.  A MATLAB interface to the GraphBLAS is in
progress.  If the import/export feature is added to the GraphBLAS C API (as is
being considered), this MATLAB interface would interoperate with any GraphBLAS
library that is compliant with the spec.

The point of these issues is that in designing an effective library, there are a host of 
complicated issues to resolve.  A major part of the research contribution of this project will
be how we solve these issues.