CGA: Accelerating BFS Through an Sparsity-Aware Adaptive Framework on Heterogeneous Platforms

doi:10.1109/TPDS.2025.3624289

CSpace

	CGA: Accelerating BFS Through an Sparsity-Aware Adaptive Framework on Heterogeneous Platforms
	Xu, Lei 1,2; Jia, Haipeng 1; Zhang, Yunquan 1
	2026
发表期刊	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
ISSN	1045-9219
卷号	37 期号:1 页码:45-59
摘要	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.
关键词	Graphics processing units Kernel Vectors Sparse matrices Optimization Machine learning algorithms Throughput Adaptation models Multicore processing Data transfer Sparse matrix-sparse vector multiplication (SpMSpV) sparse matrix-dense vector multiplication (SpMV) multi-core CPU GPU adaptive performance optimization machine learning
DOI	10.1109/TPDS.2025.3624289
收录类别	SCI
语种	英语
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Theory & Methods ; Engineering, Electrical & Electronic
WOS记录号	WOS:001620721300002
出版者	IEEE COMPUTER SOC
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/43082
专题	中国科学院计算技术研究所
通讯作者	Jia, Haipeng
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China
推荐引用方式 GB/T 7714	Xu, Lei,Jia, Haipeng,Zhang, Yunquan. CGA: Accelerating BFS Through an Sparsity-Aware Adaptive Framework on Heterogeneous Platforms[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,2026,37(1):45-59.
APA	Xu, Lei,Jia, Haipeng,&Zhang, Yunquan.(2026).CGA: Accelerating BFS Through an Sparsity-Aware Adaptive Framework on Heterogeneous Platforms.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,37(1),45-59.
MLA	Xu, Lei,et al."CGA: Accelerating BFS Through an Sparsity-Aware Adaptive Framework on Heterogeneous Platforms".IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 37.1(2026):45-59.