Abstract: Sparse Matrix-Vector Multiplication (SpMV) is an important numerical linear algebra operation. Existing optimizations for SpMV suffer from issues such as incomplete consideration of preprocessing and communication time, lack of universality in storage structures. To address these challenges, an adaptive optimization scheme for sparse matrix-vector multiplication on heterogeneous platforms was proposed. Pearson correlation coefficients are utilized to determine highly correlated feature parameters. Two algorithms, eXtreme Gradient Boosting (XGBoost) and Light Gradient Boosting Machine (LightGBM), based on Gradient Boosting Decision Trees (GBDT), were employed to train predictive models to determine the optimal storage format for a given sparse matrix. Grid search was used to determine the optimal hyperparameters during model training, achieving an accuracy of over 85% for both algorithms in selecting the most suitable storage structure. Furthermore, for sparse matrices with the hybrid (HYB) storage format, the ELLPACK (ELL) format was computed on the GPU, while the Coordinate format was computed on the CPU, establishing a CPU+GPU parallel hybrid computing mode. Additionally, for sparse matrices with small data sizes, hardware platform selection was performed to improve computational speed. Experimental results demonstrate that the adaptive computational optimization achieves an average speedup of 1.4 times compared to the Compressed Sparse Row (CSR) storage format in the cuSPARSE library, and average speedups of 2.1 times and 2.6 times compared to the HYB and ELL formats, respectively.

Key words: Keywords: Sparse Matrix-Vector Multiplication (SpMV), adaptive optimization, Pearson correlation coefficient, eXtreme Gradient Boosting (XGBoost), Light Gradient Boosting Machine (LightGBM) 

摘要： 稀疏矩阵向量乘(SpMV)是一种重要的数值线性代数运算，现有的稀疏矩阵向量乘优化存在预处理及通信时间考虑不全面、存储结构不具有普适性等问题。为了解决这些问题，提出异构平台下稀疏矩阵向量乘的自适应优化方案，通过利用皮尔逊相关系数确定相关度高的特征参数，并分别使用基于梯度提升决策树(GBDT)的极端梯度提升(XGBoost)和轻量级梯度提升(LightGBM)两种算法进行预测模型的训练以确定某一稀疏矩阵更优的存储格式。利用网格搜索确定模型训练时更优的模型超参数，使两种算法对选择更适合的存储结构的准确率都达到了85%以上。其次，对于预测存储结构为混合(HYB)格式的稀疏矩阵，在GPU上计算其中的等长列(ELL)存储格式部分，在CPU上计算坐标(COO)存储格式部分，建立基于CPU+GPU的并行混合计算模式；同时为小数据量的稀疏矩阵选择硬件平台，提高运算速度。实验结果表明，自适应计算优化相较于cuSPARSE库中的压缩稀疏行(CSR)存储格式计算的平均加速比可以达到1.4，相较于按照混合和等长列存储格式计算的平均加速比则可以达到2.1和2.6。

关键词: 稀疏矩阵向量乘, 自适应优化, 皮尔逊相关系数, 极端梯度提升, 轻量级梯度提升机器学习