Linear Algebra Is the Right Way to Think About Graphs

Student: Carl Yang (University of California, Davis; Lawrence Berkeley National Laboratory)
Advisor: John D. Owens (University of California, Davis), Aydin Buluc (Lawrence Berkeley National Laboratory; University of California, Berkeley)

Abstract: Graph algorithms are challenging to implement on new accelerators such as GPUs. To address this problem, GraphBLAS is an innovative on-going effort by the graph analytics community to formulate graph algorithms as sparse linear algebra, so that they can be expressed in a performant, succinct and in a backend-agnostic manner. Initial research efforts in implementing GraphBLAS on GPUs for graph processing and analytics have been promising, but challenges such as feature-incompleteness and poor performance still exist compared to their vertex-centric ("think like a vertex") graph framework counterparts. For our thesis, we propose a multi-language graph framework aiming to simplify the development of graph algorithms, which 1) provides a multi-language GraphBLAS interface for the end-users to express, develop, and refine graph algorithms more succinctly than existing distributed graph frameworks; 2) abstracts away from the end-users performance-tuning decisions; 3) utilizes the advantages of existing low-level GPU computing primitives to maintain high performance.

Summary: pdf
Thesis Canvas: pdf

Presentation: pdf



Back to Doctoral Showcase Archive Listing