GraphBLAS: A Programming Specification for Graph Analysis
Created September 2017
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
Learn More
Design and Implementation of the GraphBLAS Template Library (GBTL)
July 11, 2016 Presentation
Scott McMillan, Samantha Misurda, Marcin 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...
watchGBTL-CUDA: Graph Algorithms and Primitives for GPUs
May 23, 2016 Conference Paper
Peter Zhang (Indiana University), Marcin Zalewski (Indiana University), Andrew Lumsdaine (Indiana University), Samantha Misurda, Scott McMillan
In this paper, we present our initial implementation of GraphBLAS primitives for graphics processing unit (GPU) systems called GraphBLAS Template Library...
readDynamic Parallelism for Simple and Efficient GPU Graph Algorithms
December 09, 2015 Conference Paper
Peter Zhang (Indiana University), Eric Holk (Indiana University), John Matty, Samantha Misurda, Marcin Zalewski (Indiana University), Jonathan Chu, Scott McMillan, Andrew Lumsdaine (Indiana University)
Presented at the 2015 Supercomputing Conference, this paper shows that dynamic parallelism enables relatively high-performance graph algorithms for...
readGraph Algorithms on Future Architectures Poster (SEI 2015 Research Review)
October 22, 2015 Poster
Scott McMillan
Delves into whether primitives and operations can be defined to separate graph analytic application development and complexity of underlying hardware...
readGraph Algorithms on Future Architectures
October 16, 2015 Presentation
Scott McMillan
Delves into whether primitives and operations can be defined to separate graph analytic application development and complexity of underlying hardware...
watchDeveloping a Software Library for Graph Analytics
February 08, 2015 Blog Post
Scott McMillan, Eric Werner
Discover the SEI's efforts to create an open-source software library of graph algorithms for heterogeneous architectures in this SEI Blog...
read