本文介绍了一项关于稀疏矩阵-向量乘法（Sparse Matrix-Vector Multiplication, SpMV）优化的研究，主要针对对角稀疏矩阵（diagonal sparse matrices）提出了一种新的存储格式——压缩行段对角模式（Compressed Row Segment with Diagonal-pattern, CRSD）。该研究由Xiangzheng Sun、Yunquan Zhang、Ting Wang、Guoping Long、Xianyi Zhang和Yan Li等作者共同完成，他们来自中国科学院软件研究所并行软件与计算科学实验室以及中国科学院研究生院。该论文发表于2011年的Euro-Par 2011会议，并收录在Springer的Lecture Notes in Computer Science系列中。
稀疏矩阵-向量乘法（SpMV）是科学计算中的核心计算任务之一，广泛应用于数值模拟、机器学习等领域。然而，SpMV的性能高度依赖于稀疏矩阵的非零元素分布。传统的压缩稀疏行（Compressed Sparse Row, CSR）格式在现代计算机系统上表现不佳，尤其是在非零元素分布不均匀的情况下。对角稀疏矩阵是一类特殊的稀疏矩阵，其非零元素主要分布在矩阵的对角线上。这类矩阵在有限差分法（Finite Difference Method, FDM）等数值方法中非常常见。然而，现有的对角格式（Diagonal Format, DIA）在处理长零段（idle section）时效率较低，因为需要填充大量零元素。
为了应对这一问题，本文提出了CRSD存储格式，旨在通过自动调优（auto-tuning）技术，针对特定应用中的对角稀疏矩阵进行优化，从而提高SpMV的计算效率。
CRSD存储格式的核心思想是通过对角模式（diagonal pattern）来描述矩阵中非零元素的分布。对角模式将矩阵的对角线分为相邻组（adjacent group, AD）和非相邻组（nonadjacent group, NAD），并通过这些组的组合来描述矩阵的非零分布。对于特定应用中的矩阵，其对角模式在不同问题规模下通常保持不变，因此可以通过采样一个矩阵来获取这些不变的对角模式，并自动生成最优的SpMV代码片段（codelets）。
研究的主要流程包括以下几个步骤： 1. 采样矩阵：从特定应用中选择一个样本矩阵，分析其对角模式，提取出不变的对角模式。 2. 自动生成代码片段：根据提取的对角模式，自动生成最优的SpMV代码片段。 3. 组合代码片段：将生成的代码片段组合成最终的SpMV实现。 4. 并行化优化：利用自动调优过程中收集的信息，进行并行化优化，以实现负载均衡。
在自动调优过程中，研究团队还使用了SSE指令集和显式预取（explicit prefetching）等技术来进一步优化代码性能。SSE指令集允许同时对多个双精度浮点数进行操作，而显式预取则通过调整预取距离和预取局部性（prefetch locality）来优化内存访问。
研究团队在两个主流的多核平台上（AMD Phenom II X4 940和Intel Xeon X5550）对13个矩阵进行了测试，结果表明CRSD格式在SpMV计算中表现优异。与DIA格式相比，CRSD的加速比最高可达2.37倍（平均1.70倍）；与CSR格式相比，加速比最高可达4.60倍（平均2.10倍）。特别是在处理具有大量长零段的矩阵时，CRSD表现出了显著的优势。
此外，研究还发现，预取局部性（prefetch locality）对SpMV性能的影响比预取距离（prefetch distance）更为显著。通过自动调优，CRSD的并行实现也表现出了良好的负载均衡性，进一步提升了计算效率。
本文提出的CRSD存储格式为对角稀疏矩阵的SpMV计算提供了一种高效的解决方案。通过自动调优技术，CRSD能够根据特定应用中的矩阵特性生成最优的SpMV实现，从而显著提升计算性能。该研究不仅具有重要的科学价值，还为实际应用中的大规模数值计算提供了有力的工具支持。
研究团队计划将CRSD格式移植到GPU平台上，并进一步研究其他类型的非零分布模式，以优化SpMV在不同硬件架构上的性能。