论文阅读笔记系列（一）SMAT: An Input Adaptive Auto-Tuner for Sparse Matrix-Vector Multiplication
前言
最近一直觉得自己只是在看书，看文献，但是没有尝试动手写一些总结，写一些笔记，导致看书的效率实在太低。因此想做一个论文笔记系列，把自己读的论文简单地总结一下。同时也借此将看过的文献分享给大家，如果有看过相关文献的可以互相讨论一下。
第一期我就简单说一说我最近看的一篇论文，SMAT: An Input Adaptive Auto-Tuner for Sparse Matrix-Vector Multiplication，计算所谭老师在13年发的一篇文章，内容主要是实现稀疏矩阵乘法的自动优化。
问题的提出
稀疏矩阵乘法（Sparse Matrix Vector multiplication (SpMV)）是科学计算中最常见的运算，现在已经有很多库实现了稀疏矩阵乘法。然而稀疏矩阵乘法是可以根据应用的特性和运行平台架构的特性来进行优化的。如果每一个乘法都要根据应用特性和架构特性来进行手动优化的话，优化方法的通用性不足，用户体验也不好，因为并不是每个使用SpMV的人都熟悉和了解应用特性和架构特性。因此，有必要开发一个通用的自动优化方法，它能够根据具体的应用特性和平台架构特性对SpMV做优化，提高运算性能。
优化的切入口主要有两个：
- 稀疏矩阵的存储格式：常见的存储格式有CSR, COO, DIA, ELL等。每种存储格式适用于不同的矩阵结构，而且不同的存储格式对于计算的方法会有性能的影响。所以必须根据待运算的矩阵的特性选择合适的存储格式。
- 运算方法：不同的存储格式有不同的高效算法。所以得根据矩阵的存储格式和运算平台架构的特性选择高效的运算方法实现。
本文的主要贡献
- 使用包含2000多个实际应用中的稀疏矩阵的数据集来训练一个学习模型。
- 提供一个统一的接口给用户使用，根据用户输入的稀疏矩阵自动选择合适的稀疏矩阵存储格式。
- 开发了一个灵活可扩展的自动优化框架，用户可以添加新的存储格式以及实现运算的方法，增加更多的特征以及更多的数据集。
实现自动优化的方法
主要是借助一个SpMV自动优化框架（SpMV Auto-Tuner (SMAT)）实现，如下图：
图中黑色箭头就是离线的操作，也就是预先执行的操作，用来构建SMAT的各个功能部件。而红色箭头是在线的操作，就是用户输入一个新的矩阵到SMAT后，SMAT利用离线构造好的各个功能部件对这个矩阵进行预测，选择合适的存储格式。
构建决策树选择稀疏矩阵最优存储格式
左边主要负责对运行平台架构以及矩阵进行特征提取，提取出能够代表特定平台和特定矩阵的特征。矩阵特征的选择如下：
接着将特征存入特征数据库中，借助特征数据库使用数据挖掘的方法（C5.0决策树）来构建一个学习模型，也就是一棵决策树。接着每输入一个矩阵，对它和平台架构提取特征，作为输入值放入决策树中，利用决策树选择一个合适的矩阵存储格式。实际上就是一个分类问题。这一部分对面图中的下面的learning model部分。
使用查找算法找到具体矩阵存储方式对应的最优算法实现
上面那一部分optimal kernel主要是搜索最合适的kernel，也就是最好的运算实现。这一部分是使用计分板算法Scoreboard Algorithm和一张得分表来实现。这一部分我不太懂，就直接将文中的某一段进行翻译：
使用性能记录表和计分板算法进行内核（kernel）搜索。我们运行所有可能的实现（implements）(在当前SMAT系统中最多24个)，并在表中记录相应的性能。在这个表中，实现（implements）是按照特定的顺序排列的，记录中的每个性能编号都可以通过它使用的所有优化策略建立索引。根据性能表，创建一个记分牌，根据目标体系结构上的SpMV行为找到最有效的策略。从单个优化方法的实现开始，如果与基本实现相比出现性能增益，则相应的优化方法在记分牌上标记为1，否则标记为-1。当两个实现之间的性能差异小于0.01时，我们认为这种优化策略对该体系结构没有影响，并且默认忽略了它。这样，具有多个优化策略的实现应该将其性能与那些只少一个优化策略的实现进行比较。这样，我们最终得到了每个优化策略的得分，然后通过对其中使用的策略的得分求和，计算出每个实现的得分。通过这两种算法，最高分数的实现被认为是架构上相应格式的最优实现。当数据挖掘方法构建学习模型并运行执行度量模块时，将调用最优内核。
总之，这一部分就是找到具体某一运行架构和存储格式下的最优算法实现。
矩阵样例输入SMAT后的处理过程
接着分析红色箭头，即在线处理的部分。用户输入一个新的矩阵到SMAT后，SMAT利用离线构造好的各个功能部件对这个矩阵进行预测，选择合适的存储格式。具体的在线处理操作可以看下图。实际上是根据输入矩阵的特征，利用决策树来确定该矩阵的高效存储格式。决策树会对这个矩阵进行置信度分析，得到四种存储格式对应的置信度。置信度最高的，并且大于置信度阈值的存储格式就是最优的存储格式。而如果四种存储格式的置信度均不大于阈值，则需要进一步进行性能测试。使用上面得到每一个存储格式对应的最优算法实现，对每一个存储格式进行性能测试，得到性能最好的存储格式。
结果
这一部分我就简单上两张图，总的来说肯定是效果不错，性能提升的效果可观。