The Einsum-Enabled Design Space for Graph Algorithms: A BFS Case Study
Data Structures and Algorithms
Summary
The authors present a structured way to analyze different graph algorithms by breaking down their complexity into four parts: algebra, mapping, format, and implementation. They use a special notation called EDGE and focus on breadth-first search (BFS) as an example. By testing over 90 variations on GPU implementations, they not only represent known BFS techniques but also find new versions that improve performance by 1.2 to 1.7 times compared to existing best methods for certain types of graphs. Their method helps understand and optimize graph algorithms systematically.
Authors
Toluwanimi O. Odemuyiwa, Serban D. Porumbescu, Muhammad Osama, Joel S. Emer, John D. Owens
Abstract
We propose a principled approach to reasoning about various graph algorithm implementations. We leverage the extended general Einsum notation (EDGE) which allows us to factor complexity along four axes: algebraic manipulation, mapping, format, and low-level implementations. Using breadth-first search (BFS) as a driving example and case study, we apply our methodology to explore over 90 variations across 26 categories of optimization choices for our GPU-based implementations. In addition to showing that our approach is general enough to represent previously discovered algorithmic techniques such as the pull variant of BFS, we discover novel variants that lead to geomean performance benefits ranging from 1.2x to 1.7x over the best Gunrock baseline variation for graphs with mid- to high- normalized degree variance.