本文介绍了一项关于在GPU上加速稀疏矩阵-向量乘法（Sparse Matrix-Vector Multiplication, SpMV）的研究，题为《tilespmv: a tiled algorithm for sparse matrix-vector multiplication on gpus》。该研究由中国石油大学（北京）超级科学软件实验室和中国科学院计算技术研究所计算机体系结构国家重点实验室的研究团队完成，主要作者包括Yuyao Niu、Zhengyang Lu、Meichen Dong、Zhou Jin、Weifeng Liu和Guangming Tan。该论文于2021年发表在IEEE国际并行与分布式处理研讨会（IPDPS）上。

研究背景与动机

稀疏矩阵-向量乘法（SpMV）是许多科学计算和工程应用中的核心操作，尤其在稀疏迭代求解器（如共轭梯度法）和图处理框架（如GraphBLAS）中具有重要作用。然而，SpMV操作通常具有不规则性和内存带宽限制，因此难以优化。尽管过去几十年中，研究者提出了多种优化技术，如减少内存占用、提高数据局部性、利用宽向量单元、改善负载平衡等，但在现代GPU上，SpMV仍然面临诸多挑战。特别是，现有的SpMV方法未能充分利用稀疏矩阵的二维空间结构。

研究方法与流程

本文提出了一种名为tilespmv的分块算法，旨在通过利用稀疏矩阵的二维空间结构来优化GPU上的SpMV性能。具体来说，研究团队首先将稀疏矩阵划分为大小相同的稀疏块（tile），并实现了七种不同的warp级SpMV方法，用于计算存储在不同格式中的稀疏块。然后，设计了一种选择方法，为每个稀疏块找到最佳的存储格式和SpMV实现。此外，研究还提出了一种自适应方法，将非常稀疏的块中的非零元素提取到一个单独的矩阵中，以最大化整体性能。

研究的主要流程包括以下几个步骤： 1. 稀疏矩阵分块：将输入矩阵划分为大小相同的稀疏块（16x16），并将每个稀疏块作为基本工作单元。 2. 存储结构设计：设计了双层存储结构，第一层存储稀疏块的全局信息，第二层存储每个稀疏块内部的非零元素及其索引。 3. SpMV算法实现：针对七种不同的存储格式（CSR、COO、ELL、HYB、Dense、Dense Row、Dense Column），分别实现了对应的warp级SpMV算法。 4. 格式选择方法：设计了一种自适应选择方法，根据每个稀疏块的稀疏结构选择最佳的存储格式和SpMV算法。 5. 负载平衡优化：通过将非常稀疏的块提取到单独的矩阵中，进一步优化了负载平衡。

实验结果

研究团队在NVIDIA A100（Ampere架构）和Titan RTX（Turing架构）GPU上进行了实验，测试了2757个来自SuiteSparse矩阵集合的稀疏矩阵。实验结果表明，tilespmv方法在大多数矩阵上的性能优于现有的SpMV方法（如merge-spmv、CSR5和BSR），分别实现了最高2.61倍、3.96倍和426.59倍的加速比。特别是在处理具有明显二维稀疏结构的矩阵时，tilespmv表现出显著的优势。

研究贡献与意义

本文的主要贡献包括： 1. 提出了一种高效的tilespmv算法，用于在GPU上并行计算SpMV。 2. 实现了针对小稀疏矩阵的高度优化的warp级SpMV内核。 3. 开发了一种自适应选择方法，为每个稀疏块找到最佳的存储格式和内核。 4. 在最新的GPU上实现了显著的性能提升，超越了现有的SpMV方法。

该研究的科学价值在于通过利用稀疏矩阵的二维空间结构，显著提升了SpMV在GPU上的计算效率。其应用价值体现在为科学计算、图处理等领域提供了更高效的稀疏矩阵计算工具。

研究亮点

1. 新颖的分块算法：tilespmv通过将稀疏矩阵划分为稀疏块，并针对每个块选择最佳存储格式和算法，显著提升了SpMV的性能。
2. 自适应选择方法：研究提出的自适应选择方法能够根据每个稀疏块的稀疏结构动态选择最佳格式，进一步优化了计算效率。
3. 广泛的实验验证：研究在2757个稀疏矩阵上进行了全面的实验验证，证明了tilespmv在大多数情况下的优越性能。

结论

本文提出的tilespmv算法通过利用稀疏矩阵的二维空间结构，显著提升了GPU上SpMV的计算效率。实验结果表明，该方法在大多数情况下优于现有的SpMV方法，并为稀疏矩阵计算提供了新的优化思路。未来的研究可以进一步探索如何将该方法应用于更广泛的稀疏矩阵计算任务中。