GBTL.tex

\subsection{GBTL: GraphBLAS Template Library}
 
The first version of the GraphBLAS Template Library (GBTL) was written in C++ 
when the GraphBLAS C API project was just beginning.  It was used, in part, 
to study early ideas under discussion in the specification process and was released as a proof of concept 
prior to the finalization of the GraphBLAS API Specification \cite{gbtl-cuda16, McMillan2016}. With the 
release of the GraphBLAS C API Specification~\cite{cspec} in 2017, GBTL was updated to conform to 
the mathematical behavior defined by the specification and released as version 2.0~\cite{gbtl-github}.  
Unlike the C API Specification, GBTL is written in C++ and makes judicious use of templates to 
make the generic aspects of the GraphBLAS specification easier to implement and 
more natural for the C++ programming language. When the GraphBLAS language committee
starts its work on the C++ language binding to the GraphBLAS, GBTL will be submitted as a 
proposed starting point for the discussion.

 
Central to GBTL's design is the concept of a separation of concerns between 
implementation of algorithms written in terms of the GraphBLAS primitives  
and the implementation of those primitives on a targeted hardware platform.   
This separation of concerns is defined by the GraphBLAS API Specification as
illustrated in Figure~\ref{fig:overview}.  
Above this API, GBTL has developed and includes a collection of graph algorithms 
written against its C++ API and has already been shown to be easily translated to 
the C API (compare Figures~\ref{code:pyGB}(c) and~\ref{code:pyGB}(d)).  Below the separation/API, different implementations of the GraphBLAS 
library can be supported for different hardware architectures (referred to as 
``backends'').  In this way we verify that algorithms written once against the API 
can run on different targeted hardware.  One backend that is provided with Version 
2.0 of GBTL implements a mathematically correct version of the C API 
specification and serves as a reference implementation for verifying correctness.  It runs 
in a single thread on a CPU (an earlier version of GBTL also had a GPU 
implementation).  Other backend implementations are currently under development 
to optimize performance, use multiple threads, and to target specialized 
computer architectures.

\subsection{PyGB: python DSL for GraphBLAS}

Another development effort closely related to GBTL is a DSL (domain-specific language) in Python called PyGB~\cite{Chamberlin2016}.  
The goal for PyGB is to closely resemble the GraphBLAS mathematical notation found in the GraphBLAS math spec~\cite{mathgraphblas16}.  
PyGB is a framework designed and implemented to dispatch dynamically generated and compiled templated 
classes that make calls into native GBTL code.  It demonstrates how Python's syntax and dynamic execution provides 
a high-level abstraction with minimal performance penalty.  While we leave a detailed discussion of PyGB to elsewhere~\cite{Chamberlin2016}
we provide a level-BFS function using PyGB in Figure~\ref{code:pyGB}.

\begin{figure}

\begin{subfigure}{\columnwidth}
  \begin{cplus}
Input: graph, frontier, levels
depth |$\leftarrow$| 0
while nvals(frontier) > 0:
  depth |$\leftarrow$| depth + 1
  levels[frontier] |$\leftarrow$| depth
  frontier<|$\neg$|levels,replace> |$\leftarrow$| graph|$^T$| |$\oplus . \otimes$| frontier
    where |$\oplus . \otimes = \mathbf{\bigoplus} . \mathbf{\bigotimes}($|LogicalSemiring|$)$|
  \end{cplus}
%, |$\oplus  = \mathbf{\bigoplus}($|LogicalSemiring|$)$|
  \caption{Pseudocode}
  \label{subfig:pseudo}
\end{subfigure}\\[1ex]

\vspace{-0.6ex}

\begin{subfigure}{\columnwidth}
  \begin{python}
def bfs(graph, frontier, levels):
  depth = 0
  while frontier.nvals > 0:
    depth += 1
    levels[frontier][:] = depth
    with gb.LogicalSemiring, gb.Replace:
      frontier[~levels] = graph.T @ frontier
  \end{python}
 \caption{PyGB}
\end{subfigure}\\[1ex]

\begin{subfigure}{\columnwidth}
  \begin{cplus}
template<class Mat, class Frontier, class Levels>
void bfs(Mat &graph, Frontier frontier, Levels &levels)
{
  GrB::IndexType depth = 0;
  while (frontier.nvals() > 0) {
    ++depth;
    GrB::assign(levels, frontier, GrB::NoAccumulate(),
                depth, GrB::AllIndices(), false);
    GrB::mxv(frontier, GrB::complement(levels),
             GrB::NoAccumulate(),
             GrB::LogicalSemiring<GrB::IndexType>(),
             GrB::transpose(graph), frontier, true);
  }
}
\end{cplus}
\caption{GBTL \cpp}
\end{subfigure}

\begin{subfigure}{\columnwidth}
  \begin{cplus}
void bfs(GrB_Matrix  graph,
         GrB_Vector  frontier,
         GrB_Vector *levels)
{
  GrB_Index n, nvals;
  GrB_Matrix_nrows(&n, graph);
  GrB_Vector_nvals(&nvals, frontier);
  GrB_Semiring LogicalSemiring;
  GrB_Descriptor Desc_TranA_ScmpM_Replace;
  //...
  GrB_Index depth = 0;
  while (nvals > 0) {
    ++depth;
    GrB_assign(*levels, frontier, GrB_NULL,
               depth, GrB_ALL, n, GrB_NULL);
    GrB_mxv(frontier, *levels, GrB_NULL,
            LogicalSemiring, graph, frontier
            Desc_TranA_ScmpM_Replace);
    GrB_Vector_nvals(&nvals, frontier);
  }
}
\end{cplus}
\caption{GraphBLAS C API}
\end{subfigure}

\caption{Level-based BFS traversal in math pseudocode, PyGB, GBTL \cpp, and using the GraphBLAS C API.\label{code:pyGB}}
\end{figure}


Notice how the meaning of the code
is straightforward since the DSL closely tracks the notation from the GraphBLAS math spec.  We believe in the long run, the 
future of graph algorithms will depend heavily on such DSLs.

%\begin{CodeExample}
%{\textbf{Level-BFS function in pyGB}}
%{code:pyGB}
%\begin{lstlisting}
%def bfs(graph, frontier, levels):
%    level = 0
%    while frontier.nvals > 0:
%        level += 1
%        levels[front][:] = level
%        with gb.LogicalSemiring, gb.Replace:
%            frontier[~levels] = graph.T @ frontier 
%\end{lstlisting}
%\end{CodeExample}