@misc{yzelman20,
 author = "Yzelman, A. N. and Di Nardo, D. and Nash, J. M. and Suijlen, W. J.",
 title = "A {C++} {GraphBLAS}: specification, implementation, parallelisation, and evaluation",
 year = "2020",
 keywords = "graph algorithms",
 keywords = "linear algebra",
 keywords = "C++",
 keywords = "data-centric",
 keywords = "auto-parallelisation",
 keywords = "auto-vectorisation",
 keywords = "high-performance computing",
 keywords = "shared-memory",
 keywords = "distributed-memory",
 keywords = "cost modelling",
 abstract = "The {GraphBLAS} is a programming model that expresses graph algorithms in linear algebraic terms. It takes an easy-to-use, data-centric view where algebraic operations execute over sparse or dense vectors and sparse matrices, parametrised in the algebra the computation should proceed with. We present a {C++ GraphBLAS} interface designed with both shared- and distributed-memory systems in mind. Our specification employs {STL}-compatible generic programming principles. Templates and type traits allow for enhanced compile-time error handling and optimisation, even for user-defined types and operators. Our specification guides algorithm designers towards writing performant code by attaching performance semantics to each operation.

We detail a reference implementation that auto-vectorises and auto-parallelises user programs for sequential as well as shared- and distributed-memory parallel machines. We demonstrate the use of our {API} via two canonical graph algorithms, the k-nearest neighbourhood and {PageRank}. Weak and strong scaling experiments using real-world datasets with up to 42 billion edges show that the defined performance semantics are achievable in practice and capture key performance characteristics of the two selected algorithms. Microbenchmarks and throughput estimates from the PageRank algorithm on real-world graphs furthermore show that our reference implementation can extract near peak performance on different architectures.",
 url = "\url{http://albert-jan.yzelman.net/PDFs/yzelman20.pdf}"
}