中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
CGA: Accelerating BFS Through an Sparsity-Aware Adaptive Framework on Heterogeneous Platforms

文献类型：期刊论文

作者Xu, Lei1,2; Jia, Haipeng1; Zhang, Yunquan1
刊名IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
出版日期2026
卷号37期号:1页码:45-59
关键词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
ISSN号1045-9219
DOI10.1109/TPDS.2025.3624289
英文摘要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.
资助项目National Key Research & Development Program of China[2023YFB3001700] ; National Natural Science Foundation of China[62372432] ; National Natural Science Foundation of China[61972376] ; National Natural Science Foundation of China[62072431] ; National Natural Science Foundation of China[62032023] ; Shanxi Province Science and Technology Major Special Project[202201010101004]
WOS研究方向Computer Science ; Engineering
语种英语
WOS记录号WOS:001620721300002
出版者IEEE COMPUTER SOC
源URL[http://119.78.100.204/handle/2XEOYT63/43081]  
专题中国科学院计算技术研究所
通讯作者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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。