本文介绍了一项由西安交通大学电子科学与工程学院的研究团队（Chenyang Li, Tian Xia, Wenzhe Zhao, Nanning Zheng, Pengju Ren）在2021年ACM/IEEE设计自动化会议（DAC）上发表的研究成果。该研究提出了一种名为SPV8的新型稀疏矩阵-向量乘法（Sparse Matrix-Vector Multiplication, SpMV）优化方法，旨在解决现有SpMV算法在向量化效率和计算模式不规则性之间的权衡问题。

研究背景与动机

稀疏矩阵-向量乘法（SpMV）是科学计算和工业应用中的核心操作，广泛应用于结构力学、图分析和深度学习等领域。然而，由于稀疏矩阵的非零元素分布极不规则且密度极低（通常小于10^-4），SpMV的计算效率在现代CPU/GPU平台上往往受到低向量化、低数据局部性和高分支预测错误的严重影响。尽管许多研究致力于通过定制数据格式和复杂计算模式来优化向量化和数据局部性，但这些方法通常伴随着显著的计算不规则性，导致额外的开销。例如，Intel数学核心库（MKL）中的SpMV例程中，近40%的CPU周期因分支预测错误而浪费。

研究方法与流程

SPV8的核心思想是通过分析不同矩阵和行面板的数据分布，选择最优的计算模式，以实现最大化的向量化效率，同时保持计算模式的规则性。具体来说，SPV8的设计包括以下几个关键步骤：

1. 向量化策略分析：SPV8研究了两种基本的向量化策略——行内并行（in-row parallel）和跨行并行（cross-row parallel）。行内并行适用于长行，而跨行并行适用于相邻行长度相近的情况。SPV8通过将矩阵行按长度分组，并根据SIMD宽度重新排列行，选择最适合的计算模式。

2. 内核设计：SPV8内核摒弃了部分向量操作和向量掩码，简化了计算模式。对于无法向量化的非零元素，SPV8使用简单的标量操作进行计算。此外，SPV8通过限制结果的生成方式，避免了不规则的计算模式，从而最小化了条件分支的数量。

3. 矩阵分区：为了减少内存访问的局部性损失，SPV8将原始矩阵划分为多个分区，并在每个分区上独立应用SPV8内核。分区的规模选择在内存访问开销和向量化效率之间进行了权衡，实验表明，对于不同类型的矩阵，选择合适的分区规模可以显著提高性能。

4. 多核实现：SPV8通过将每个线程分配给多个独立的分区，实现了多核并行计算。为了保持负载均衡，SPV8根据非零元素的数量创建分区，并使用调度器动态分配分区给空闲线程。

实验结果

研究团队在Intel Xeon Skylake CPU上对SPV8进行了评估，并与多种现有的SpMV算法（如CVR、CSR5、ESB等）进行了对比。实验使用了71个来自SuiteSparse集合的稀疏矩阵，涵盖了多种应用领域。实验结果表明，SPV8在向量化效率和计算规则性方面均表现出色：

• 向量化效率：SPV8在大多数矩阵上实现了接近100%的向量化效率，且分支预测错误率极低（接近0%）。
• 性能提升：与标准的MKL SpMV例程相比，SPV8在单线程和多线程情况下分别实现了最高10倍和2.8倍的速度提升。与现有最佳方法相比，SPV8也分别实现了最高2.4倍和1.4倍的速度提升。
• 预处理开销：SPV8的预处理开销极低，仅为基线运行时间的8倍，远低于其他优化方法（如MKL Opt的30倍）。

结论与意义

SPV8通过优化向量化效率和计算模式的规则性，显著提升了SpMV的计算性能。其低预处理开销和高适用性使其在现实世界的SpMV应用中具有广泛的应用前景。该研究的创新之处在于其独特的向量化策略和规则化计算模式设计，为稀疏矩阵计算领域提供了新的思路和方法。

研究亮点

1. 高性能：SPV8在多种稀疏矩阵上实现了显著的性能提升，尤其是在大规模稀疏矩阵上的表现尤为突出。
2. 低开销：SPV8的预处理开销极低，适用于需要多次迭代的SpMV应用。
3. 规则化计算模式：通过摒弃复杂的控制流和向量掩码，SPV8实现了高度规则化的计算模式，减少了分支预测错误和非必要指令的开销。

其他有价值的内容

SPV8的开源代码已公开发布在GitHub上（https://github.com/monkey2000/spv8-public），供研究者和开发者进一步研究和应用。此外，该研究得到了广东省重点领域研发计划和国家自然科学基金的支持。

通过这项研究，SPV8为稀疏矩阵-向量乘法的优化提供了新的解决方案，有望在科学计算和工业应用中发挥重要作用。