SURF: Direction-Optimizing Breadth-First Search Using Workload State on GPUs.

Area of Science:

• Computer Science
• Graph Algorithms
• High-Performance Computing

Background:

• Graph data structures are vital in scientific and social networks, requiring efficient analysis via graph algorithms.
• Breadth-First Search (BFS) is a fundamental algorithm for large-scale graph processing, often implemented in specialized libraries.
• Optimizing BFS performance on Graphics Processing Units (GPUs) is critical for handling complex graph workloads.

Purpose of the Study:

• To propose SURF (Selecting directions Upon Recent workload of Frontiers), a novel direction selection method for enhancing BFS performance on GPUs.
• To address the limitations of existing direction selection methods that rely on static thresholds.
• To improve the efficiency of BFS by dynamically adapting to varying workload frontiers.

Main Methods:

• Defined and analyzed metrics characterizing the workload state of graph frontiers.
• Developed a deep neural network model that uses these metrics as input features for direction selection.
• Implemented the SURF method and compared its performance against state-of-the-art BFS optimization techniques.

Main Results:

• SURF demonstrates higher direction prediction accuracy compared to existing methods.
• The proposed method significantly reduces BFS execution time on GPUs.
• SURF achieved speedups of up to 5.62x over Gunrock and 3.15x over Enterprise.

Conclusions:

• SURF offers a more effective approach to direction optimization in BFS by considering dynamic workload metrics.
• The deep neural network-based approach provides accurate direction selection for improved BFS performance.
• SURF represents a significant advancement in efficient large-scale graph processing on GPUs.