Loading…
CppCon 2021 has ended
Back To Schedule
Monday, October 25 • 3:15pm - 4:15pm
GraphBLAS: Building a C++ Matrix API for Graph Algorithms

Log in to save this to your schedule, view media, leave feedback and see who's attending!

Feedback form is now closed.
One of the most challenging issues in high-performance graph algorithms is dealing with bespoke graph data structures and algorithms, which can be difficult to optimize and maintain. The GraphBLAS is a mathematical and C API specification that allow programmers to implement graph algorithms using the language of linear algebra. Programmers implement their graph algorithms using high-level matrix and vector operations, such as generalized matrix and vector multiply. Their code can then be executed using matrix algorithms, such as sparse matrix multiply, that have been finely tuned, taking advantage of decades of research in optimizing sparse linear algebra for CPU, GPU, and distributed platforms.

In this talk, we discuss our efforts and experience building and implementing a C++ GraphBLAS API. We define a number of data structures, such as our GraphBLAS matrix type, which has a similar interface to `unordered_map`, but with a 2-D `key_type`, a fixed dimension, and possibly different backend storage data structures, depending on a collection of compile-time hints. We also define a collection of structs to represent various binary operators, monoids, and semirings used in graph algorithms. These are similar to the arithmetic operations defined in the STL's `functional`, but with extra type information to store a monoid's identity, and to promote pre-existing binary operators (such as STL's arithmetic ops) to monoids. We also discuss matrix views, the divorce of a specific arithmetic from the data structure (monoids and semirings being specifically associated with an operation, not a data structure, as a data structure may be used in multiple operations with different arithmetics), and generalized element-wise operations.

ALL TALK SESSIONS CAN BE ACCESSED FROM THE MAIN LOBBY: https://cppcon.digital-medium.co.uk/

Speakers
avatar for Benjamin Brock

Benjamin Brock

PhD Student, UC Berkeley
Ben Brock is a PhD student at UC Berkeley, where he works on building libraries, tools, and algorithms for high-performance computing. His main work focuses on building a cross-platform library of data structures for distributed applications, with a focus on sparse linear algebra... Read More →
avatar for Scott McMillan

Scott McMillan

Principal research engineer, Carnegie Mellon University
GraphBLAS: graph algorithms in the language of linear algebra


Monday October 25, 2021 3:15pm - 4:15pm MDT
C) Summit 7