search menu icon-carat-right cmu-wordmark

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

Software and Tools

gbtl

May 2016

gbtl is a library that provides GraphBLAS API in C++ and common graph algorithms built on top of...

read

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...

watch

GBTL-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...

read

Dynamic 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...

read

Graph 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...

read

Graph 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...

watch

Developing 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