基于GPU的稀疏矩阵压缩存储格式研究
电子技术应用
陈闽昊，边浩东
青海大学 计算机技术与应用学院
摘要： 稀疏矩阵向量乘法（Sparse Matrix-Vector Multiplication，SpMV）是矩阵数值计算领域重要的线性代数子程序。通过对SpMV算法的负载均衡以及访存频度这两个关键性能瓶颈的研究，提出了一种VCSR（Vectorized Compressed Sparse Row）稀疏矩阵压缩存储格式。该格式根据各行非零元素分布的统计特性调整各个线程的数据负载来防止线程发散的问题，并且基于快速分段求和的策略以及使用矢量化的方法来提高SpMV流程的计算性能。通过使用佛罗里达大学的稀疏矩阵作为测试集，在GPU上进行性能测试，获得了相较CSR5（Compressed Sparse Row 5）格式平均10%到30%，最高50%的性能提升。
中图分类号：TP312 文献标志码：A DOI: 10.16157/j.issn.0258-7998.245825
中文引用格式： 陈闽昊，边浩东. 基于GPU的稀疏矩阵压缩存储格式研究[J]. 电子技术应用，2024，50(11)：1-8.
英文引用格式： Chen Minhao，Bian Haodong. Sparse matrix compressed storage format based on GPU[J]. Application of Electronic Technique，2024，50(11)：1-8.
中文引用格式： 陈闽昊，边浩东. 基于GPU的稀疏矩阵压缩存储格式研究[J]. 电子技术应用，2024，50(11)：1-8.
英文引用格式： Chen Minhao，Bian Haodong. Sparse matrix compressed storage format based on GPU[J]. Application of Electronic Technique，2024，50(11)：1-8.
Sparse matrix compressed storage format based on GPU
Chen Minhao，Bian Haodong
School of Computer Technology and Application， Qinghai University
Abstract： Sparse Matrix-Vector Multiplication (SpMV) is an important linear algebraic subroutine in Matrix numerical computation. Vectorized Compressed Sparse Row (VCSR) sparse matrix compression format is proposed by studying the load balancing and memory access frequency of SpMV algorithm. This format adjusts the data load of each thread according to the statistical characteristics of the distribution of each line of non-zero elements to prevent the problem of thread divergence, and improves the computational performance of SpMV flow based on the strategy of fast segmented summation and the vectorization method. By using the Sparse matrix of the University of Florida as the test set, the performance of the GPU is tested, and the average performance improvement is 10% to 30%, and the maximum performance is 50% compared to the CSR5 (Compressed Sparse Row 5) format.
Key words : SpMV；load balancing；storage format；segmented sum methods；floating-point calculation；vectorization；GPU
引言
在过去的很长一段时间中，SpMV都是科学计算和工程应用领域中大规模稀疏性系统问题求解的常用方法，也因此其实现和优化一直是高性能领域研究中的重点。SpMV计算简化为一个大小为m×n的稀疏矩阵A与长度为n的密集向量x相乘，从而得到一个长度为m的向量y。
随着稀疏矩阵规模的扩大，同时又因为其数据具有着分布稀疏无规则的问题，普通的顺序计算和简单的并行优化无法满足现阶段科学计算和工程应用领域的要求，所以人们尝试使用更快速的并行优化算法以及提出更优质的压缩存储格式来加速大规模的SpMV计算。根据稀疏矩阵稀疏性、不规则性的特点，加速SpMV算法的难点主要集中在解决以下几个问题上：（1）并行单元上负载不均衡导致的线程发散；（2）数据存储不规则导致的频繁访存所产生的额外开销；（3）低效矢量化产生的内存访问冲突和数据依赖性。现阶段许多的压缩存储格式也从这几个方面入手加速大规模SpMV运算，例如BELLPACK、CVR、BCCOO、ACSR、CSR5[1-4]等。
本文也从这上述几个方面入手，提出了一种新的格式名为VCSR，VCSR格式以CSR格式作为基础，根据各行非零元素分布的统计特性，将数据以负载均衡的方式分发给各个线程。在这个过程中，将行作为数据分配的基础单元，保证了线程与线程之间数据处理的相互独立，不会产生数据依赖以及访问冲突。最后，在每个并行单元中，使用快速分段求和的策略和矢量化的方式来加速SpMV内核程序的计算性能。
本文详细内容请下载：
https://www.chinaaet.com/resource/share/2000006202
作者信息：
陈闽昊，边浩东
（青海大学 计算机技术与应用学院，青海 西宁 810016）
此内容为AET网站原创，未经授权禁止转载。