基于GPU的SpMV并行算法优化方法研究.pdf

基于GPU的SpMV并行算法优化方法研究

摘要

随着高性能处理器的不断发展和普及，并行技术的重要性在各个领域逐步显现。稀

疏矩阵向量乘法（SpMV）作为科学与工程领域中至关重要的核心操作之一，在图形处

理、科学计算、机器学习等领域都有着广泛的应用，如何高效优化稀疏矩阵向量乘法成

为当前的研究热点。由于稀疏矩阵结构的特殊性，主流的SpMV方法在一定程度上提高

了计算效率，但仍然存在以下问题：（1）部分子块间不平衡的计算量导致线程块的负载

不均衡；（2）不合理的数据存储方式导致并行阶段数据访问不连续；（3）对计算资源的

利用率较低，难以充分发挥GPU应有的性能。因此，本文设计了基于GPU的SpMV并行

优化方法，具体包括：

（1）针对并行阶段部分线程间的工作负载不均衡问题，提出了一种基于可变阈值

的行归并SpMV优化方法TEB。设计了一种启发式阈值选择算法，为稀疏矩阵提供合理

的子块划分依据，然后结合基于重排序的行归并算法将稀疏矩阵进行有效划分，保证子

块间的非零元素数量具有最大相似性。进一步提出了并行SpMV内核，采用线程块与子

块、线程与行的映射方式并行处理计算数据，使得线程具有相近的计算任务量，实现负

载均衡。实验结果表明，在佛罗里达大学公开的稀疏矩阵数据集上，TEB相比于CSR-

Scalar、CSR5、AMF-CSR和PBC方法的时间性能分别提升2.30、2.21、3.23和5.83倍，

浮点运算性能分别提升2.29、2.12、3.36和5.95倍。

（2）对于传统方法在访存连续性和资源利用率方面的局限性，在TEB方法基础上，

提出了基于动态划分合并的异构SpMV优化方法。结合稀疏矩阵结构特征和异构处理器

计算能力，设计了CPU-GPU动态异构并行框架，能够有效分配不同处理器工作量，充分

合理利用计算资源。同时，提出了适用于异构框架的数据划分和存储方法，采用以列为

基本单位的矩阵合并策略，能够有效满足向量X的数据局部性和访问连续性。进一步提

出了CPU-GPU动态异构并行内核，充分发挥CPU和GPU异构计算的优势，提高了SpMV

的计算效率。实验结果表明，CPU-GPU动态异构并行方法相较于单独使用CPU和GPU平

台，分别获得199和1.44倍的时间性能加速，相比于MKL和cuSPARSE库，分别获得1.65

和1.15倍的浮点运算性能加速。

关键词：稀疏矩阵；SpMV；负载均衡；访存连续；异构体系

基于GPU的SpMV并行算法优化方法研究

Abstract

Withthecontinuousdevelopmentandpopularizationofhigh-performanceprocessors,the

importanceofparalleltechnologyisgraduallyemerginginvariousfields.SparseMatrixVector

Multiplication(SpMV)isoneofthecrucialcoreoperationsinthefieldsofscienceand

engineering.Ithasextensiveapplicationsinfieldssuchasgraphicsprocessing,scientific

computing,andmachinelearning.Howtoefficientlyoptimizesparsematrixvector

multiplicationhasbecomeacurrentresearchhotspot.Duetotheparticularityofsparsematrix

structures,mainstreamSpMVmethodshaveimprovedcomputationalefficiencytoacertain

extent,buttherearestillthefollowingpro