GPU上的稀疏矩阵向量乘法性能分析与优化

"本文探讨了在GPU上执行稀疏矩阵向量乘法(SpMV)的性能分析和优化方法。文章提出了一种独特的概率建模方法，适用于不同类型的稀疏矩阵，与现有针对特定稀疏矩阵的优化方法不同，并且无需额外的基准测试来获取优化参数。" 在GPU计算中，SpMV是一个关键操作，广泛应用于科学计算、机器学习和图形处理等多个领域。由于稀疏矩阵的特性，其计算效率受到非零元素分布、存储结构以及并行策略等因素的影响。传统的优化方法通常针对特定类型的稀疏矩阵（如CSR、CSC或ELL格式）进行优化，但这种方法并不通用。 本研究中，作者提出了一种基于概率建模的新方法，通过分析稀疏矩阵非零元素出现的概率分布来直接计算优化参数。这种方法的优势在于，它可以自适应各种稀疏矩阵结构，而不需要为每种情况都进行耗时的基准测试。此外，该方法还考虑了GPU的并行特性，以最大化数据并行性和计算效率。 在论文中，作者首先构建了一个异构集群系统上的随机任务调度模型，其中任务处理时间和任务间通信时间被视为遵循特定概率分布的随机变量。他们证明了，随机任务的预期完成时间至少等于将所有处理时间和通信时间替换为其期望值后的确定性任务的完成时间。这意味着处理不确定性是优化的关键挑战。 为了解决这个问题，作者提出了一个名为随机动态级别调度(Stochastic Dynamic Level Scheduling, SDLS)的算法。该算法基于随机底层和随机动态层的概念，旨在有效地处理优先级约束的随机任务。通过模拟和实验结果，SDLS算法在减少预期完成时间（即 makespan）、提高加速比和减小 makespan 的标准差方面表现出显著的优越性，对比现有的调度算法，它提供了更好的性能。 这篇论文为GPU上的SpMV操作提供了新的性能分析和优化工具，同时对异构集群中的随机任务调度问题提出了有效的解决方案。这一工作对于理解和改进大规模并行计算环境中的稀疏矩阵运算具有重要意义，并可能推动GPU计算在各种领域的进一步应用。