TurboBFS: GPU Based Breadth-First Search (BFS) Algorithms in the Language of Linear Algebra

Area of Science:

• Computer Science
• Graph Theory
• High-Performance Computing

Background:

• Large-scale graphs are crucial for modeling complex systems like brain networks and social interactions.
• Manual analysis of these vast graphs is infeasible.
• The Breadth-First Search (BFS) algorithm is fundamental for graph analysis but computationally expensive for large datasets.

Purpose of the Study:

• To develop an efficient GPU-based implementation of BFS for large-scale graph analysis.
• To address the computational challenges and memory limitations of using GPUs for graph processing.
• To present a linear-algebraic approach for BFS acceleration.

Main Methods:

• Developed TurboBFS, a GPU-based linear-algebraic formulation of BFS.
• Implemented and tested TurboBFS on unweighted, undirected, and directed sparse graphs of arbitrary structure.
• Evaluated performance against state-of-the-art algorithms on various libraries.

Main Results:

• TurboBFS demonstrates excellent scalability for large graph analysis.
• Achieved up to 40 Giga Traversed Edges Per Second (GTEPs).
• Outperformed existing algorithms by 15.7x (SuiteSparse:GraphBLAS), 5.8x (GraphBLAST), and 1.8x (gunrock) on average.

Conclusions:

• TurboBFS provides a highly efficient and scalable solution for BFS on GPUs.
• The linear-algebraic approach effectively overcomes GPU memory and irregular graph structure challenges.
• This method significantly advances the analysis of massive graphs in various scientific domains.