本文介绍了一项关于在GPU上加速稀疏矩阵-向量乘法（Sparse Matrix-Vector Multiplication, SpMV）数据加载的研究，题为《FastLoad: Speeding Up Data Loading of Both Sparse Matrix and Vector for SpMV on GPUs》。该研究由Jinyu Hu、Huizhang Luo、Hong Jiang、Guoqing Xiao和Kenli Li共同完成，发表在2024年12月的《IEEE Transactions on Parallel and Distributed Systems》期刊上。
SpMV是许多现代应用中的核心操作，如深度学习、稀疏迭代求解器和图处理问题等。然而，由于稀疏矩阵的非零元素分布不规则，SpMV在GPU上的性能往往受到数据加载效率低下的限制。尽管已有研究通过合并内存访问（coalesced memory access）来提高数据加载效率，但这些方法仍未充分发挥现代GPU的潜力。因此，本文提出了一种名为FastLoad的高效算法，旨在通过优化稀疏矩阵和输入向量的数据加载来提升SpMV的整体性能。
FastLoad算法的核心思想是通过对稀疏矩阵的列和输入向量的元素进行排序，并组织非零元素为块（block），以实现合并内存访问并避免线程分歧（thread divergence）。具体流程分为以下几个步骤：
排序与分块：首先，根据稀疏矩阵每列中非零元素的数量对列进行排序，并对输入向量的相应元素进行排序。然后，将非零元素划分为多个块，每个块的长度固定为32（与GPU的warp大小一致），高度则根据列中非零元素的数量动态调整。
数据加载与计算：在数据加载阶段，FastLoad通过合并内存访问来高效加载稀疏矩阵和输入向量的数据。每个块被分配给一个warp，线程在warp内并行计算乘法操作。为了保持负载均衡，FastLoad采用分段和（segment sum）和前缀和（prefix sum）技术来优化加法操作，减少原子操作（atomicadd）的使用。
实验结果：研究团队使用Suitesparse矩阵集合中的2757个矩阵作为测试数据集，在NVIDIA RTX 3090 Ti GPU上进行了实验。结果表明，FastLoad在大多数矩阵上的性能优于现有的SpMV算法，如CSC-based SpMV、cuSPARSE、CSR5和TileSpMV，几何平均加速比分别为2.12倍、2.98倍、2.88倍和1.22倍。
FastLoad的主要贡献在于： 1. 高效的数据加载：通过合并内存访问，FastLoad显著提高了稀疏矩阵和输入向量的数据加载效率。 2. 负载均衡：通过分块和排序技术，FastLoad实现了线程和warp之间的负载均衡，避免了线程分歧。 3. 优化加法操作：通过引入分段和与前缀和技术，FastLoad减少了原子操作的使用，进一步提升了加法操作的效率。
FastLoad不仅在理论上提出了新的优化思路，还在实际应用中展示了显著的性能提升。该算法为GPU上的SpMV操作提供了新的解决方案，尤其适用于处理大规模稀疏矩阵的应用场景，如深度学习、科学计算和图分析等。此外，FastLoad的设计思路也为其他不规则应用的优化提供了参考。
未来的研究可以进一步探索FastLoad与其他稀疏矩阵格式的结合，例如与TileSpMV的集成，以评估其在更广泛应用场景中的性能表现。此外，还可以研究如何通过机器学习技术自动选择最适合的稀疏矩阵格式，以进一步提升SpMV的性能。
FastLoad通过优化数据加载和负载均衡，显著提升了SpMV在GPU上的性能。该研究不仅为稀疏矩阵计算提供了新的解决方案，还为GPU上的高性能计算应用开辟了新的优化方向。