Delta-stepping SSSP: from Vertices and Edges to GraphBLAS Implementations

Tuesday April 30, 2019
Location: CIC Panther Hollow
Time: 4:30PM-5:30PM

GraphBLAS is an interface for implementing graph algorithms. Algorithms implemented using the GraphBLAS interface are cast in terms of linear algebra-like operations. However, many graph algorithms are canonically described in terms of operations on vertices and/or edges. Despite the known duality between these two representations, the differences in the way algorithms are described using the two approaches can pose considerable difficulties in the adoption of the GraphBLAS as standard interface for development. This paper investigates a systematic approach for translating a graph algorithm described in the canonical vertex and edge representation into an implementation that leverages the GraphBLAS interface. We present a two-step approach to this problem. First, we express common vertex- and edge-centric design patterns using a linear algebraic language. Second, we map this intermediate representation to the GraphBLAS interface. We illustrate our approach by translating the delta-stepping single source shortest path algorithm from its canonical description to a GraphBLAS implementation, and highlight lessons learned when implementing using GraphBLAS.

Mark Blanco is a second-year PhD student advised by Professor Tze Meng Low. His research focuses on graph processing algorithms and analytical models for graph processing to enable efficient implementations across architectures and compute platforms.