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

Learn More

Design and Implementation of the GraphBLAS Template Library (GBTL)

Design and Implementation of the GraphBLAS Template Library (GBTL)

July 11, 2016 Presentation
Scott McMillanSamantha MisurdaMarcin Zalewski (Indiana University)

The design of the GraphBLAS Template Library separates graph algorithm development from performance tuning for heterogeneous high-performance computing architectures.

read
GBTL-CUDA: Graph Algorithms and Primitives for GPUs

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)

In this paper we present our initial implementation of GraphBLAS primitives for graphics processing unit (GPU) systems called GraphBLAS Template Library (GBTL).

read
Dynamic Parallelism for Simple and Efficient GPU Graph Algorithms

Dynamic Parallelism for Simple and Efficient GPU Graph Algorithms

December 09, 2015 Conference Paper
Eric Holk (Indiana University)Scott McMillanAndrew Lumsdaine (Indiana University)

Presented at the 2015 Supercomputing Conference, this paper shows that dynamic parallelism enables relatively high-performance graph algorithms for GPUs.

read
Graph Algorithms on Future Architectures Poster (SEI 2015 Research Review)

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 concern

read
Graph Algorithms on Future Architectures

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 concern

read
Developing a Software Library for Graph Analytics

Developing a Software Library for Graph Analytics

February 09, 2015 Blog Post
Scott McMillan

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