Sparse Diagonal Matrix Adaptive SpMV Optimization Method for GPU

doi:10.19678/j.issn.1000-3428.0069807

Abstract

Abstract:

Sparse Matrix-Vector multiplication (SpMV) is the computational core and bottleneck of sparse linear systems, and its computational efficiency affects the overall performance of iterative solvers. Its optimization has long been a research hotspot in the fields of scientific computing and engineering applications. The discretization of partial differential equations produces sparse diagonal matrices, and because of their diverse distributions of nonzero elements, no single method can achieve optimal time performance across all matrices. To solve these problems, a Graphics Processing Unit (GPU)-based sparse diagonal matrix adaptive SpMV optimization method called Adaptive SpMV Tuning (AST) is proposed. This method designs a feature space and constructs a feature extractor to extract fine-grained features of the matrix structure. By analyzing the correlation between these features and SpMV methods, it establishes a scalable set of candidate methods and forms a mapping relationship between the features and optimal methods. Subsequently, a performance prediction tool is built to efficiently predict the optimal method for the matrix. The experimental results show that AST can achieve a prediction accuracy of 85.8%, with an average time performance loss of 0.09. Compared to Diagonal (DIA), Hacked DIA (HDIA), Hybrid of DIA and Compressed Sparse Row (HDC), DIA-Adaptive, and Divide-Rearrange and Merge (DRM), AST can achieve an average speedup in kernel runtime of 20.19, 1.86, 3.06, 3.72, and 1.53 times, respectively, and a speedup in floating-point performance of 1.05, 1.28, 12.45, 1.94, and 0.97 times, respectively.

Key words: Sparse Matrix-Vector multiplication (SpMV), sparse diagonal matrix, Graphics Processing Unit (GPU), adaptive optimization method, matrix structural feature

摘要：

稀疏矩阵向量乘(SpMV)是稀疏线性系统的计算核心和瓶颈, 其运算效率会影响迭代求解器的整体性能, 其优化研究一直是科学计算和工程应用领域中的研究热点之一。偏微分方程的离散化会产生稀疏对角矩阵, 由于其多样的非零元分布, 导致没有一种方法能够在所有矩阵中取得最优时间性能。针对上述问题, 提出一种面向图形处理单元(GPU)的稀疏对角矩阵自适应SpMV优化方法AST(Adaptive SpMV Tuning)。该方法通过设计特征空间, 构建特征提取器, 提取矩阵结构精细特征, 通过深入分析特征和SpMV方法的相关性, 建立可扩展的候选方法集合, 形成特征和最优方法的映射关系, 构建性能预测工具, 实现矩阵最优方法的高效预测。实验结果表明, AST能够取得85.8%的预测准确率, 平均时间性能损失为0.09, 相比于DIA(Diagonal)、HDIA(Hacked DIA)、HDC(Hybrid of DIA and Compressed Sparse Row)、DIA-Adaptive和DRM(Divide-Rearrange and Merge), 能够获得平均20.19、1.86、3.06、3.72和1.53倍的内核运行时间加速和1.05、1.28、12.45、1.94和0.97倍的浮点运算性能加速。

关键词: 稀疏矩阵向量乘, 稀疏对角矩阵, 图形处理单元, 自适应优化方法, 矩阵结构特征

WANG Yuhua, HE Junfei, ZHANG Yuqi, LAN Haiyan, CAO Linlin. Sparse Diagonal Matrix Adaptive SpMV Optimization Method for GPU[J]. Computer Engineering, 2026, 52(3): 332-345.

王宇华, 何俊飞, 张宇琪, 兰海燕, 曹林琳. 面向GPU的稀疏对角矩阵自适应SpMV优化方法[J]. 计算机工程, 2026, 52(3): 332-345.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0069807

https://www.ecice06.com/EN/Y2026/V52/I3/332

Figures/Tables 18

Fig.1 Examples of sparse diagonal matrices

Fig.2 Comparison of kernel running time of five SpMV methods

Fig.3 Framework of adaptive optimization method

Fig.4 Distribution of five SpMV methods over N_Ndiags and R_{ER_DIA}

Fig.5 Distribution of five SpMV methods over N_{var_diags_nnz} and N_{avg_diags_nnz}

Fig.6 Distribution of five SpMV methods over N_{max_offset} and N_splashes

Fig.7 Comparison of the average time performance loss of six SpMV methods

Fig.8 Comparison of total kernel running time of six SpMV methods on twenty matrices

Fig.9 Comparison of kernel running time of six SpMV methods

Fig.10 Comparison of total GFLOPs of six SpMV methods on twenty matrices

Fig.11 Comparison of GFLOPs of six SpMV methods

Fig.12 GFLOPs speedup ratio of AST method compared to the other five methods

References 26

1	BORRELL R , DOSIMONT D , GARCIA-GASULLA M , et al. Heterogeneous CPU/GPU co-execution of CFD simulations on the POWER9 architecture: application to airplane aerodynamics. Future Generation Computer Systems, 2020, 107 (6): 31- 48.
2	INA T, IDOMURA Y, IMAMURA T, et al. Iterative methods with mixed-precision preconditioning for ill-conditioned linear systems in multiphase CFD simulations[C]//Proceedings of the 12th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA). Saint Louis, USA: IEEE Press, 2021: 1-8.
3	XING L Y , WANG Z S , DING Z Z , et al. An efficient sparse stiffness matrix vector multiplication using compressed sparse row storage format on AMD GPU. Concurrency and Computation: Practice and Experience, 2022, 34 (23): e7186.1- e7186.12.
4	O'HEARN K A, ALPEREN A, AKTULGA H M. Performance optimization of reactive molecular dynamics simulations with dynamic charge distribution models on distributed memory platforms[C]//Proceedings of the ACM International Conference on Supercomputing. New York, USA: ACM Press, 2019: 150-159.
5	杜臻, 谭光明, 孙凝晖. 高性能稀疏矩阵向量乘的程序设计综述. 高技术通讯, 2024, 34 (8): 807- 823. doi: 10.3772/j.issn.1002-0470.2024.08.003
	DU Z , TAN G M , SUN N H . A survey of high-performance sparse matrix-vector multiplication programming. Chinese High Technology Letters, 2024, 34 (8): 807- 823. doi: 10.3772/j.issn.1002-0470.2024.08.003
6	ASANOVIC K, BODIK R, CATANZARO B C, et al. The landscape of parallel computing research: a view from Berkeley: UCB/EECS-2006-183[R]. Berkeley, USA: University of California at Berkeley, 2006: 1-56.
7	BELL N, GARLAND M. Efficient sparse matrix-vector multiplication on CUDA: NVR-2008-004[R]. Santa Clara, USA: Nvidia Corporation, 2008: 1-32.
8	BELL N, GARLAND M. Implementing sparse matrix-vector multiplication on throughput-oriented processors[C]//Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis. New York, USA: ACM Press, 2009: 1-11.
9	YESIL S, HEIDARSHENAS A, MORRISON A, et al. WISE: predicting the performance of sparse matrix vector multiplication with machine learning[C]//Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. New York, USA: ACM Press, 2023: 329-341.
10	CUI H Y , HAN Q L , WANG N B , et al. An adaptive approach for compression format based on bagging algorithm. International Journal of Parallel, Emergent and Distributed Systems, 2023, 38 (5): 401- 423. doi: 10.1080/17445760.2023.2231291
11	TAN G M , LIU J H , LI J J . Design and implementation of adaptive SpMV library for multicore and many-core architecture. ACM Transactions on Mathematical Software, 2018, 44 (4): 1- 25. doi: 10.1145/3218823
12	NISA I, SIEGEL C, RAJAM A S, et al. Effective machine learning based format selection and performance modeling for SpMV on GPUs[C]//Proceedings of 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). Vancouver, Canada: IEEE Press, 2018: 1056-1065.
13	MOHAMMED T , ALBESHRI A , KATIB I , et al. DIESEL: a novel deep learning-based tool for SpMV computations and solving sparse linear equation systems. The Journal of Supercomputing, 2021, 77 (6): 6313- 6355. doi: 10.1007/s11227-020-03489-3
14	NIU Y Y, LU Z Y, DONG M C, et al. TileSpMV: a tiled algorithm for sparse matrix-vector multiplication on GPUs[C]//Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS). Portland, USA: IEEE Press, 2021: 68-78.
15	DU Z, LI J J, WANG Y S, et al. AlphaSparse: generating high performance SpMV codes directly from sparse matrices[C]//Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. Dallas, USA: IEEE Press, 2022: 1-15.
16	BARBIERI D, CARDELLINI V, FANFARILLO A, et al. Three storage formats for sparse matrices on GPGPUs: RR-15.06[R]. Rome, Italy: University di Roma Tor Vergata, 2015: 1-32.
17	YANG W D , LI K L , LIU Y , et al. Optimization of quasi-diagonal matrix-vector multiplication on GPU. The International Journal of High Performance Computing Applications, 2014, 28 (2): 183- 195. doi: 10.1177/1094342013501126
18	阳王东, 李肯立, 石林. 一种准对角矩阵的混合压缩算法及其与向量相乘在GPU上的实现. 计算机科学, 2014, 41 (7): 290- 296. doi: 10.11896/j.issn.1002-137X.2014.07.060
	YANG W D , LI K L , SHI L . Quasi-diagonal matrix hybrid compression algorithm and implementation for SpMV on GPU. Computer Science, 2014, 41 (7): 290- 296. doi: 10.11896/j.issn.1002-137X.2014.07.060
19	GAO J Q , XIA Y F , YIN R J , et al. Adaptive diagonal sparse matrix-vector multiplication on GPU. Journal of Parallel and Distributed Computing, 2021, 157, 287- 302. doi: 10.1016/j.jpdc.2021.07.007
20	夏羿飞. 面向GPU的并行稀疏对角矩阵矢量乘算法研究及应用[D]. 南京: 南京师范大学, 2019.
	XIA Y F. Research and application of parallel sparse diagonal matrix-vector multiplication algorithm on GPU[D]. Nanjing: Nanjing Normal University, 2019. (in Chinese)
21	王宇华, 何俊飞, 张宇琪, 等. DRM: 基于迭代归并策略的GPU并行SpMV存储格式. 计算机工程与科学, 2024, 46 (3): 381- 394. doi: 10.3969/j.issn.1007-130X.2024.03.001
	WANG Y H , HE J F , ZHANG Y Q , et al. DRM: A GPU-parallel SpMV storage format based on iterative merge strategy. Computer Engineering & Science, 2024, 46 (03): 381- 394. doi: 10.3969/j.issn.1007-130X.2024.03.001
22	SONG Y Y , LU Y . Decision tree methods: applications for classification and prediction. Shanghai Archives of Psychiatry, 2015, 27 (2): 130- 135. doi: 10.11919/j.issn.1002-0829.215044
23	CERVANTES J , GARCIA-LAMONT F , RODRÍGUEZ-MAZAHUA L , et al. A comprehensive survey on support vector machine classification: applications, challenges and trends. Neurocomputing, 2020, 408, 189- 215. doi: 10.1016/j.neucom.2019.10.118
24	CHEN T Q, GUESTRIN C. XGBoost: a scalable tree boosting system[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM Press, 2016: 785-794.
25	DAVIS T A , HU Y F . The university of Florida sparse matrix collection. ACM Transactions on Mathematical Software, 2011, 38 (1): 1- 25.
26	RIGATTI S J . Random forest. Journal of Insurance Medicine, 2017, 47 (1): 31- 39. doi: 10.17849/insm-47-01-31-39.1

[1]	ZHANG Lei, ZHAO Guangyue, XIAO Chaoen, WANG Jianxin. GPU Parallel Optimal Design and Implementation of Key Tree Generation Components for Falcon Post-Quantum Algorithms [J]. Computer Engineering, 2024, 50(9): 208-215.
[2]	CHENG Kai,TIAN Jin,MA Ruilin. Study on Efficient Storage Format of Sparse Matrix Based on GPU [J]. Computer Engineering, 2018, 44(8): 54-60.
[3]	LI Yafeng, QIN Kaihuai. A Binocular Stereo Vision Algorithm on GPU [J]. Computer Engineering, 2006, 32(10): 210-211,236.

Please choose a citation manager

Content to export