稀疏矩阵计算性能预测

面向硬件体系结构的性能预测方法依赖于分析建模技术。AM将有关不同参数如何影响性能的现有理解编码到数学模型中。这要求开发人员必须全面理解硬件和代码之间的交互，针对不同的硬件平台，考虑不同的硬件规格，比如每个SM的核心数量、线程块的数量。

Choi等人提出了一个模型驱动的框架，可以在GPU上实现对SpMV的自动性能调优。基于传统的CSR格式，该框架提出了一种变体BCSR（Blocked CSR），对col_index数组进行了压缩。Wrap中的每个线程处理一个block，将block装入向量中提高带宽利用率。基于BCSR的SpMV实现优于CSR格式下的SpMV，但是NVIDIA下其他稀疏矩阵格式的最佳实现性能仍然优于BCSR。于是Bell等人采用了一种ELLPACK的变体，BELLPACK（Blocked ELLPACK），这种新的格式结合了BCSR对数据的压缩和ELLPACK对向量友好的优点。BELLPACK在单精度下实现了1.3～1.8的加速比，在双精度下实现了1.1～1.5的加速比，实现了接近峰值测量带宽的利用率。为了在 GPU 上实现BELLPACK的最好性能，需要仔细地调节block大小相关的参数，这些参数与矩阵有关，通过性能模型确定。为了对GPU上SpMV运行时间建模，需要对硬件平台做一些简化的假设，比如假设所有的SM是完全同步的，还需要了解硬件平台的相关信息，如SM上的线程块数等。这种框架下选择的调优参数相对于穷举搜索的中值误差小于15%。(www.xing528.com)

Guo等人提出了一个用于GPU上SpMV性能建模和优化分析的工具。建模过程分为两个阶段。首先在第一个阶段中首先计算strip的大小，strip是使一次迭代中线程块满载的子矩阵大小；其次根据GPU架构生成基准矩阵，由基准矩阵得到的运行时间等属性将作为模型建立的输入；然后测试基准矩阵的运行时间；最后计算用于模型测试的目标矩阵的strip数和每一行的非零元数。在第二个阶段中用基准矩阵得到的实验结果实例化模型参数，预测SpMV对目标矩阵的执行时间。该模型在目标矩阵数据集上的预测时间和测量的运行时间相比差异在 10%以内。对于CSR、ELL、COO和HYB四种格式在基于CUDA的SpMV下平均差异分为6.3%、4.4%、2.2%和4.7%。该模型可用于基于CUDA的SpMV内核和基于OpenCL的SpMV内核。对于不同的GPU架构需要重新生成基准矩阵。优化分析工具利用性能模型，搜索目标矩阵的所有可能的存储格式（划分或不划分），判断将矩阵整体按某一格式存储的性能，以及将矩阵划分后每一块按不同格式存储的性能的优劣，报告最优的执行方案。与NVIDA的CSR、COO、HYB格式下的CUDA内核相比，分析工具提供的最优解决方案可以分别带来平均41.1%、49.8%和37.9%的性能提升。