CGA: Accelerating BFS Through an Sparsity-Aware Adaptive Framework on Heterogeneous Platforms
- 22 October 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 37 (1) , 45-59
Abstract
Direction optimization determines whether to use Sparse Matrix-Sparse Vector Multiplication (SpMSpV) or Sparse Matrix-Dense Vector Multiplication (SpMV) based on the input vector’s sparsity at each iteration of Breadth-First Search (BFS), aiming to achieve the fastest graph traversal. Although prior work on direction optimization has achieved state-of-the-art performance on either CPUs or GPUs, it has not fully leveraged the capabilities of modern heterogeneous platforms. This is because SpMSpV/SpMV execution times on GPUs do not consistently outperform those on CPUs, particularly for SpMSpV. In response, this paper introduces CGA, a machine learning-based adaptive framework for BFS that optimally selects between CPU and GPU kernels, effectively Adapting to diverse real-world graphs, vectors, and computing platforms. Our contributions include a novel set of bucket-based SpMSpV algorithms that significantly enhance kernel performance in high-sparsity scenarios, along with a low-overhead decision tree model and reduced CPU-GPU data transfers. Experimental results show that our framework outperforms previous state-of-the-art methods, achieving up to a 4.91x speedup over CPU-only baseline and 3.27x speedup over GPU-only baseline.Keywords
Funding Information
- National Key Research (2023YFB3001700)
- National Natural Science Foundation of China (62372432, 61972376, 62072431, 62032023)
- Shanxi Province Science and Technology Major Special Project (202201010101004)
This publication has 51 references indexed in Scilit:
- A scalable adaptive-matrix SPMV for heterogeneous architectures2022
- SpV8: Pursuing Optimal Vectorization and Regular Computation Pattern in SpMV2021
- TileSpMV: A Tiled Algorithm for Sparse Matrix-Vector Multiplication on GPUs2021
- Overhead-Conscious Format Selection for SpMV-Based Applications2018
- A Work-Efficient Parallel Sparse Matrix-Sparse Vector Multiplication Algorithm2017
- Sparse Matrix Format Selection with Multiclass SVM for SpMV on GPU2016
- GraphPad: Optimized Graph Primitives for Parallel and Distributed Platforms2016
- The Benchmark Suite2008
- Classification and Regression Trees, Bagging, and Boosting2005
- Random Geometric Graphs2003