【调研】GPU矩阵乘法的性能预测——Machine Learning Approach for Predicting The Performance of SpMV on GPU

目录

 01 研究背景

 02 技术背景

 03 实验方法

 04 工作启迪

 附录 GPU底层结构与执行流程

        不管是解方程还是机器学习，最后在数值上，都是矩阵的计算。

        对于非常大的矩阵，需要消耗大量的内存，并且拖慢计算速度。

        通常，矩阵的大部分值都是零，因此在矩阵中，将数值为0的元素的数目远远大于非0的元素的数目，并且非0元素分布无规律时，称为稀疏矩阵；反之，则称为稠密矩阵。

        稀疏矩阵是内存高效的数据结构，使我们能够存储具有极少非零元素的大型矩阵。

        可以用稀疏度来表示矩阵的稀疏程度。

        稀疏矩阵向量乘法，就是稀疏矩阵与向量之间的乘法计算。

        大型的稀疏矩阵在做乘法时，由于大量零值的存在，不仅浪费了内存，还拖慢了计算的效率。因此，在许多科学研究中， SpMV在计算成本上占主导地位。

        一种可行的优化方法是将矩阵压缩，转为不同的格式进行存储，主要思想是如何高效地记录下非零值。

        矩阵向量乘法的性能跟矩阵的稀疏性和硬件有关，作者从这两个方面出发，在两种不同的GPU上，分别使用支持向量回归和多层感知机算法，来预测几种稀疏格式的SpMV性能。

        这个性能我看了下，指的其实就是执行一次矩阵乘法的耗时。

        他的数据集使用的是佛罗里达大学的公开稀疏矩阵集。

        第一种是基于坐标的存储形式，也是最基本、最常见的一种格式。

        他使用3个一维的数组来标识稀疏矩阵，分别是非零元素、元素行坐标和列坐标。

        这种格式的优点是性能与稀疏矩阵的结构无关，也就是说，不管值如何分布，他的存储都是一样。

        但由于它存储的内容比较多，因此存储效率比较低。

        一般主要用来创建矩阵，然后转为其他格式。

        按行对矩阵进行压缩的CSR格式也采用3个一维数组来标识矩阵，分别为非零元素、元素列坐标以及前几行非零元素的数量。

        第3个数组不是很好理解，可以把它跟前两个数组分开来看，xxxxx。

        与COO相比，虽然同样采用了3个数组来表示，但CSR存的内容更少，因此内存效率相对较高。

        但它会存在非合并访问内存的问题，大概就是说，如果矩阵非常大，导致分段存储在不同的内存块上，访问时就需要内存切换。

        常用于读入数据后进行稀疏矩阵计算。

        在CSR标量中，每一行分配一个线程用于SpMV操作。每个线程将计算乘积并对每一行的乘积求和。然而，由于工作负载不平衡和非合并的内存访问，CSR标量的性能很差。CSR向量是对CSR标量的改进，在CSR标量中，将warp(32个线程)分配给一行来执行SpMV。但是，每行非零元素数量的差异会导致空闲线程，从而导致负载不平衡，从而导致性能较差。

第三种是ELL格式，他采用了2个二维数组来表示矩阵。第一个矩阵用来存非零元素，他更像是原矩阵的缩小版，结构很像，但去除了大部分零值，列数由一行中非零元素的最大值决定，其余位置补零。第二个矩阵用来存非零元素的列索引。

        可以看到，由于他存在零填充原则，因此可能会需要很大的内存空间。

        第四种格式HYB，结合了ELL和COO两种方式。使用ELL存储密集部分、COO存储稀疏部分。

        首先计算行大小的直方图以确定阈值k，每列左侧k个为ELL，其余右侧为COO。

        虽然结合了两者的优点，但同时也引入了两者的缺点。

        作者使用了两种算法来进行SpMV性能的预测，第一种是支持向量回归SVR，他是在高维特征空间中计算回归函数，实际就是基于SVM的回归算法。

        通过选择不同的核函数，可以拟合不同的超平面。在论文中，作者选择了径向基函数 （RBF） 作为核函数。

        第二个是使用了多层感知器神经网络来预测性能。

        感知器是一个单层神经网络。它由四个主要部分组成，包括输入值、权重和偏差、净和以及激活函数。

        作为神经网络的简化形式，特别是单层神经网络，感知器在二元分类中起着重要作用。

        多层感知器可以用于逼近线性和非线性问题，因此适用于当前高维特征的回归问题。

        作者的实验思路为以下4步，比较常规。

        首先他使用的是佛罗里达的稀疏矩阵数据集，大概2800+个。

        然后使用cusp库对每个矩阵计算其特征和SpMV平均运算时间，其中，特征用于训练，时间用作标签。

        然后使用前面的两种算法分别在两个GPU上训练和测试验证。

        由于数据集中的矩阵分布广泛，作者进行筛选剔除了一些不符合要求的矩阵。

        首先将COO格式下占用了超过80%GPU的去掉，然后根据前面ELL的零填充规则，去除了零填充比>3或元素数量超过100w的矩阵。

        最后剩下了1128个。

作者选择了以下属性作为训练的特征。

        N表示稀疏矩阵行数，也就是要计算的输出向量的元素数。

        Nnz是矩阵中非零元素的数量，与计算输出向量所需的运算(乘法和加法)的数量成正比。

        Dis表示每一行中每对连续非零元素之间的平均距离。该指标提供了一种简单的方法来描述由对乘向量的随机访问所导致的缓存错过级别。它也被用于作为稀疏矩阵非零元素弥散程度的有效指标。

        mu和sd分别表示每行非零元素的数量和每行非零元素的标准差，用于表征CSR格式下的SpMV核(向量核)的性能对矩阵行大小的敏感度。因为它为矩阵的每一行使用一个线程向量(在我们的实验中是32个线程)。

        由于ELL格式中的行大小(在零填充之后)等于每行非零元素的最大数量(max)。作者发现，在特征集中包含n X max可以提高预测的准确性，因为它表征了ELL格式引入的零填充后矩阵元素的总数。

        在右图中，将所有数据集按照nnz值递增的顺序排序后，绘制出每个特征。可以观察到，数据集涵盖了所有这些特性的广泛范围。此外，除了n和n x max总体上随nnz值的增加而增加外，所使用的特征之间没有很强的相关性。

1)对于COO格式:由于该格式的性能不依赖于输入矩阵的稀疏性，所以只使用:

        矩阵的行数(n)，也就是要计算的输出向量的元素数。

        矩阵中非零元素的数量(nnz)，与计算输出向量所需的运算(乘法和加法)的数量成正比。

        每一行中每对连续非零元素之间的平均距离(dis)，描述了对乘向量的随机访问。该指标提供了一种简单的方法来描述由对乘向量的随机访问所导致的缓存错过级别。它也被用于作为稀疏矩阵非零元素弥散程度的有效指标。

2) CSR格式:

        出于与COO格式相同的原因，我们使用n。

        CSR格式下的SpMV核(向量核)的性能对矩阵行大小很敏感，因为它为矩阵的每一行使用一个线程向量(在我们的实验中是32个线程)。为了表征这种灵敏度，我们使用每行非零元素的数量(mu)和每行非零元素的标准差(sd)。

3)对于ELL格式:

        出于与COO和CSR格式相同的原因，我们使用n、nnz和dis。

        ELL内核对输入矩阵的每一行使用一个线程。如第二节所示，ELL格式中的行大小(在零填充之后)等于每行非零元素的最大数量(max)。我们发现，在特征集中包含n X max可以提高预测的准确性，因为它表征了ELL格式引入的零填充后矩阵元素的总数。

4)对于HYB格式:每个稀疏矩阵被视为两个子矩阵，COO子矩阵和ELL子矩阵。然后使用之前的COO和ELL特征来描述每个部分。

计算所得的特征和时间如图所示。

        然后作者简单粗暴的直接用sklearn库中的MLPRegressor和SVR方法，按照表中的参数进行预测。

        作者对预测值计算其RME误差，并绘制了两种GPU下不同算法对不同存储格式的误差表和分布图。

        并据此，作者得出结论，由于SVR模型在RME小于5%的测试用例中所占的百分比最高，因此SVR模型在RME方面比MLP模型更准确。

        作者在上面发现的基础上，使用SVR模型进行了进一步的实验。

        作者使用著名的通常用于测试SpMV在GPU上性能的14个非结构化稀疏矩阵作为测试集，其他的均作为训练集。

        实验发现，对于Maxwell GPU, COO、ELL、CSR和HYB内核的平均RME值分别为5.01%、6.14%、7.94%和8.45%。对于Fermi GPU，分别是9.40%、6.33%、8.91%和12%。

 ​​​​​​​       以上就是作者的全部工作内容。看完可能感觉作者内容没有很复杂，但他将稀疏矩阵存储格式与深度学习联系起来，给了我们一点启迪。

        由于电路中的每个节点通常只与少数几个节点有连接关系，因此电路方程矩阵通常是稀疏度很高的稀疏矩阵。

        如何在GPU环境下加速矩阵运算，在很大程度上控制着EDA技术的并行化性能。

        因此，基于这个思想，通过结合GPU与人工智能技术，优化稀疏矩阵，可能可以实现加速EDA电路网表的仿真计算。

​​​​​​​