This shows you the differences between two versions of the page.

Link to this comparison view

seminars:delta-stepping_sssp_-_from_vertices_and_edges_to_graphblas_implementations [2019/04/26 11:27] (current)
bschwedo created
Line 1: Line 1:
 +====== 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.