稀疏矩阵向量乘的存储访问复杂度及自动性能优化技术应用研究

在科学计算中，稀疏矩阵向量乘（SpMV, y=Ax）是一个十分重要的，且经常被大量调用的计算内核，广泛应用在科学计算、信息检索、气象、航天、油藏模拟、天体物理、数据挖掘等科学计算和实际应用中。在实际工程应用中，重复调用稀疏矩阵向量乘内核的次数常常会达到成千上万次。但在现代基于Cache存储层次的计算平台上，稀疏矩阵向量乘的性能很低。如果能够提高稀疏矩阵向量乘的运算速度，整个工程计算的运行效率将会得到很大的改善，计算时间也会大幅度的减少。因此优化稀疏矩阵向量乘的性能成为提高工程效率的关键，在实际应用中有着十分重要的意义。 SpMV的传统算法实现形式运行效率很低，主要原因是浮点计算操作和存储访问操作比率非常低，且稀疏矩阵非零元分布的不规则性使得存储访问模式非常复杂。寄存器分块算法和启发式选择分块算法,通过自适应选择性能最佳的分块大小，然后将稀疏矩阵分成小的稠密分块，所有的非零子块顺序计算，达到重用保存在寄存器中向量x元素的目的，减少存储访问次数和时间，从而提高这一重要内核的性能。我们在Pentium IV、Alpha EV6和AMD Athlon三个平台上，分别测试了十个矩阵下的两种不同算法形式(压缩行存储算法和寄存器分块算法)的性能，平均加速比分别达到1.69、1.90和 1.48。同时也测试了不同次数调用SpMV两种算法所用的时间，发现在实际的迭代算法应用过程中，若想采用启发式-寄存器分块算法达到性能提高的目的，一般情况下，迭代次数需要达到上百次才能有加速效果。 DRAM(h)模型是基于存储层次的并行计算模型，指出算法的复杂性包括计算复杂性和存储访问复杂性，具有近乎相同时间和空间复杂性的同一算法的不同实现形式，会有不同的存储访问复杂度，导致程序实际运行性能的差异；利用DRAM(h)模型进行分析并比较不同算法实现形式的存储访问复杂度，可以判断两种算法形式的优劣，从而为选取性能更高的实现形式提供指导。但利用DRAM(h)模型分析SpMV存储访问复杂度的工作以前没有人做过，并且SpMV的计算性能和存储访问行为跟具体的稀疏矩阵有关，只有到程序运行的时候才能知道。本文中，我们提出模板法和动态统计分析法两种分析SpMV存储访问复杂度的方法。在Pentium IV和Alpha EV6平台上，用RAM(h) 模型分析和计算了稀疏矩阵向量乘两种算法实现形式（即压缩行存储算法和寄存器分块算法）的存储访问复杂度，通过分析和计算在SpMV过程中需要访问的所有数据的存储访问复杂度，可知存储访问行为对整体程序的实际性能有直接影响。我们还在Pentium IV平台上，测试了七个稀疏矩阵的SpMV性能，并统计了两种算法中L1, L2,和TLB的缺失率，实验结果与模型分析的结果一致。