Abstract: Sparse matrix-vector multiplication (SpMV) is a crucial computing process in the field of science and engineering. CSR (compressed sparse row) format is one of the most commonly used storage formats for sparse matrix. In the process of implementing parallel SpMV on the graphics processing unit (GPU), it only stores non-zero elements of sparse matrix, avoiding computational redundancy caused by zero element filling, and saving storage space. But there is a problem of load imbalance, which wastes computing resources. To address the aforementioned issues, storage formats with good performance in recent years have been studied, and a row by row decomposition and reorganization storage format—TEB (threshold-exchangeorder block) format has been proposed. The format first uses a heuristic threshold selection algorithm to determine the appropriate segmentation threshold, and combines the row merging algorithm based on reordering to reconstruct and decompose the sparse matrix, so that the number of non-zero elements between blocks is as close as possible. Furthermore, combined with CUDA (computer unified device architecture) thread technology, a parallel SpMV algorithm between sub blocks based on TEB storage format is proposed, which can reasonably allocate computing resources and solve the problem of load imbalance, thus improving the parallel computing efficiency of SpMV. In order to verify the effectiveness of the TEB storage format, experiments are conducted on the NVIDIA Tesla V100 platform. The results show that compared to PBC (partition-block-CSR), AMF-CSR (adaptive multi-row folding of CSR), CSR-Scalar (compressed sparse row-scalar), and CSR5 (compressed sparse row 5) storage formats, TEB can improve SpMV time performance by an average of 3.23×, 5.83×, 2.33×, and 2.21×. In terms of floating-point computing performance, the average improvement can be 3.36×, 5.95×, 2.29×, and 2.13×

Key words: sparse matrix-vector multiplication (SpMV), reorder, compressed sparse row (CSR) format, load balancing, storage format, graphics processing unit (GPU)

摘要： 稀疏矩阵向量乘法（SpMV）是科学与工程领域中一个至关重要的计算过程，CSR（compressed sparse row）格式是最常用的稀疏矩阵存储格式之一，在图形处理器（GPU）平台上实现并行SpMV的过程中，其只存储稀疏矩阵的非零元，避免零元素填充所带来的计算冗余，节约存储空间，但存在着负载不均衡的问题，浪费了计算资源。针对上述问题，对近年来效果良好的存储格式进行了研究，提出了一种逐行分解重组存储格式——TEB（threshold-exchangeorder block）格式。该格式采用启发式阈值选择算法确定合适分割阈值，并结合基于重排序的行归并算法，对稀疏矩阵进行重构分解，使得块与块之间非零元个数尽可能得相近，其次结合CUDA（computer unified device architecture）线程技术，提出了基于TEB存储格式的子块间并行SpMV算法，能够合理分配计算资源，解决负载不均衡问题，从而提高SpMV并行计算效率。为了验证TEB存储格式的有效性，在NVIDIA Tesla V100平台上进行实验，结果表明TEB相较于PBC（partition-block-CSR）、AMF-CSR（adaptive multi-row folding of CSR）、CSR-Scalar（compressed sparse row-scalar）和CSR5（compressed sparse row 5）存储格式，在SpMV的时间性能方面平均可提升3.23、5.83、2.33和2.21倍；在浮点计算性能方面，平均可提高3.36、5.95、2.29和2.13倍。

关键词: 稀疏矩阵向量乘法（SpMV）, 重新排序, CSR格式, 负载均衡, 存储格式, 图形处理器（GPU）