提出基于哈希的稀疏矩阵加速方法，显著提升GPU上稀疏矩阵乘向量效率。
A Nonlinear Hash-based Optimization Method for SpMV on GPUs
- 用哈希分组技术优化稀疏矩阵重排，降低预处理开销。
- 预处理阶段比排序法快3.53倍，比动态规划法快3.67倍。
- 适用于大规模科学计算与AI场景，尤其适合GPU部署。
稀疏矩阵-向量乘法（SpMV）是科学计算和人工智能中的基础操作，但其大规模与稀疏特性常导致性能瓶颈。本文提出一种轻量级的哈希分组（HBP）格式，利用哈希变换将相似元素分组，保留二维分区方法的优势，同时加速稀疏矩阵重排的预处理阶段。通过竞争性策略实现矩阵块间的并行负载均衡。实验在Nvidia Jetson AGX Orin和RTX 4090上进行，结果表明：预处理阶段相较排序方法提速3.53倍，较Regu2D中动态规划方法提速3.67倍；在SpMV运算中，相较于大学佛罗里达稀疏矩阵集（University of Florida Sparse Matrix Collection）的CSR格式，在Orin上最高提速3.32倍，RTX4090上最高提速3.01倍。
原文摘要 · Abstract (English)
Sparse matrix-vector multiplication (SpMV) is a fundamental operation with a wide range of applications in scientific computing and artificial intelligence. However, the large scale and sparsity of sparse matrix often make it a performance bottleneck. In this paper, we highlight the effectiveness of hash-based techniques in optimizing sparse matrix reordering, introducing the Hash-based Partition (HBP) format, a lightweight SpMV approach. HBP retains the performance benefits of the 2D-partitioning method while leveraging the hash transformation's ability to group similar elements, thereby accelerating the pre-processing phase of sparse matrix reordering. Additionally, we achieve parallel load balancing across matrix blocks through a competitive method. Our experiments, conducted on both Nvidia Jetson AGX Orin and Nvidia RTX 4090, show that in the pre-processing step, our method offers an average speedup of 3.53 times compared to the sorting approach and 3.67 times compared to the dynamic programming method employed in Regu2D. Furthermore, in SpMV, our method achieves a maximum speedup of 3.32 times on Orin and 3.01 times on RTX4090 against the CSR format in sparse matrices from the University of Florida Sparse Matrix Collection.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。