本文由Xiangzheng Sun、Yunquan Zhang、Ting Wang、Xianyi Zhang、Liang Yuan和Li Rao共同撰写，他们来自中国科学院软件研究所并行软件与计算科学实验室、中国科学院计算机科学国家重点实验室以及中国科学院研究生院。该研究发表于2011年的国际并行处理会议（International Conference on Parallel Processing, ICPP），题为《Optimizing SPMV for Diagonal Sparse Matrices on GPU》。

研究背景

稀疏矩阵-向量乘法（Sparse Matrix-Vector Multiplication, SPMV）是科学计算中的核心计算任务之一，其性能高度依赖于稀疏矩阵中非零元素的分布。现有的稀疏矩阵存储格式（如CSR、BCSR、DIA、ELL等）各有优劣，但尚未有一种通用的最优解决方案适用于所有非零分布情况。特别是对于对角线稀疏矩阵（Diagonal Sparse Matrices），现有的DIA格式在处理长零段（idle sections）时效率较低，因为需要填充大量零值以维持对角线结构，这会导致额外的计算和内存资源消耗。

为了解决这一问题，本文提出了一种新的存储格式——压缩行段对角线模式（Compressed Row Segment with Diagonal-pattern, CRSD）。该格式通过设计对角线模式（diagonal pattern）来表示对角线分布，并利用GPU的强大计算能力，结合OpenCL编程框架，实现了高效的SPMV计算。

研究流程

1. CRSD存储格式的设计：

   • 对角线模式将矩阵的对角线分为相邻组（AD组）和非相邻组（NAD组），并通过分组方式减少零值的填充。
   • 矩阵被划分为行段（row segments），每个行段内的非零元素被连续存储，并作为操作单元。
   • 散点（scatter points）在行段内被检测并单独存储，以减少零值填充。

2. SPMV在GPU上的实现：

   • 使用OpenCL编程框架，设计了一个代码生成器，根据对角线模式生成SPMV内核（kernel）。
   • 生成的代码片段（codelet）已经包含了非零元素的索引信息，减少了SPMV操作中的内存压力。
   • 代码生成器还利用了GPU的内存架构和线程调度特性，进一步优化了性能。

3. 实验评估：

   • 在23个矩阵上进行了性能评估，选择了四种现有的存储格式（DIA、ELL、CSR和HYB）作为对比。
   • 实验结果表明，CRSD格式在双精度和单精度计算中的加速比分别达到了1.52和1.94，显著优于其他格式。
   • 在双路四核Intel Xeon系统上，CRSD格式的加速比分别达到了11.93和12.79。

主要结果

1. CRSD格式的性能优势：

   • 在GPU上，CRSD格式在处理对角线稀疏矩阵时表现出色，尤其是在非零元素分布较为分散的矩阵上，显著优于DIA和ELL格式。
   • 在CPU上，CRSD格式的加速比也达到了11.93（双精度）和12.79（单精度），远高于CSR格式。

2. 内存优化：

   • CRSD格式通过减少零值填充和优化内存访问模式，显著降低了内存带宽的压力。
   • 在GPU上，CRSD格式利用局部内存（local memory）重用相邻组的元素，进一步提高了性能。

结论

本文提出的CRSD格式为对角线稀疏矩阵的存储和计算提供了一种高效的解决方案。通过设计对角线模式和优化GPU上的SPMV实现，CRSD格式在处理长零段和散点时表现出色，显著提升了计算性能。该研究不仅具有重要的科学价值，还为科学计算中的稀疏矩阵处理提供了新的思路。

研究亮点

1. 新颖的存储格式：CRSD格式通过引入对角线模式，有效减少了零值填充，优化了内存访问模式。
2. 高效的GPU实现：结合OpenCL编程框架，设计了代码生成器，充分利用了GPU的计算资源和内存架构。
3. 显著的性能提升：在多个矩阵上的实验结果表明，CRSD格式在GPU和CPU上均表现出色，显著优于现有的存储格式。

其他有价值的内容

本文还探讨了CRSD格式在不同平台上的适用性，并提出了未来在Cell和AMD设备上进行更多评估的计划。此外，作者还计划研究更多类型的非零分布，以进一步扩展CRSD格式的应用范围。

致谢

本文得到了国家863计划、中国国家天文台和中国科学院计算机网络信息中心的支持。