GraphBLAS: A Programming Specification for Graph Analysis
Graph algorithms are in wide use in DoD software applications, including intelligence analysis, autonomous systems, cyber intelligence and security, and logistics optimizations. These algorithms make it possible to detect subtle patterns in massive graphs. The GraphBLAS Forum is a world-wide consortium of researchers—across government, research centers, academia, and industry—working to develop an application programming interface (API) specification for graph analysis that will simplify development of these algorithms. GraphBLAS stands for Graph Basic Linear Algebra Subprograms.
Facing the Challenge of Cost and Complexity
Despite their utility and wide use, graph algorithms are difficult and costly to implement efficiently on hardware systems. The implementations are hardware-dependent; different hardware requires different approaches. As the size of graphs and the pace at which new hardware is being developed increase, the complexity of developing high-performance graph libraries becomes a prohibitive barrier to the work of analyzing the deluge of information.
A Broad Collaboration
The effort encompasses work by other federally funded research and development centers, including MIT Lincoln Labs, Lawrence Berkley National Laboratory, Pacific Northwest National Laboratory, and Sandia National Laboratory; industry partners such as IBM and Intel; and academia, including the University of California at Santa Barbara, Berkley, and Davis, Indiana University, and others.
Finding a Solution Through GraphBLAS
To address this problem, we are working with leading graph analytics experts and high-performance computing experts in the GraphBLAS Forum to derive an “interface” that represents a separation of concerns between low-level tuning of implementations for specific hardware and high-level development of algorithms for graph analytics.
By treating graphs as matrices and identifying a standard set of building blocks—“primitives”—in terms of operations on these matrices, our approach is similar to what the scientific computing community accomplished with the National Institute of Standards and Technology (NIST) Basic Linear Algebra Subprograms (BLAS) specification.
The SEI is a member of the GraphBLAS Forum and its C API specification committee. We’ve also implemented a C++ library—GraphBLAS Template Library (open-source)—developed with our collaborators at Indiana University.
For more information about graph algorithms and GraphBLAS, see
July 11, 2016 Presentation
Scott McMillanSamantha MisurdaMarcin Zalewski (Indiana University)Peter Zhang (Indiana University)Andrew Lumsdaine (Indiana University)
The design of the GraphBLAS Template Library separates graph algorithm development from performance tuning for heterogeneous high-performance computing architectures.watch
May 23, 2016 Conference Paper
Peter Zhang (Indiana University)Marcin Zalewski (Indiana University)Andrew Lumsdaine (Indiana University)Samantha MisurdaScott McMillan
In this paper we present our initial implementation of GraphBLAS primitives for graphics processing unit (GPU) systems called GraphBLAS Template Library (GBTL).read
December 09, 2015 Conference Paper
Peter Zhang (Indiana University)Eric Holk (Indiana University)Jonathan ChuScott McMillanAndrew Lumsdaine (Indiana University)John MattySamantha MisurdaMarcin Zalewski (Indiana University)
Presented at the 2015 Supercomputing Conference, this paper shows that dynamic parallelism enables relatively high-performance graph algorithms for GPUs.read
October 22, 2015 Poster
Delves into whether primitives and operations can be defined to separate graph analytic application development and complexity of underlying hardware concernread
February 09, 2015 Blog Post
This blog post was co-authored by Eric Werner. Graph algorithms are in wide use in Department of Defense (DoD) software applications, including intelligence analysis, autonomous systems, cyber intelligence and security, and logistics optimizations. In late 2013, several luminaries from the...read