基于机器学习的稀疏矩阵向量乘法加速模型WISE

329×→WISE：用机器学习SerifYesil伊利诺伊大学香槟分校syesil2@illinois.edu亚当·莫里森 特拉 维 夫 大 学mad@cs.tau.ac.il摘要稀疏矩阵向量乘法（SpMV）是一种重要的稀疏核。已经开发了许多方法来加速SpMV。然而，没有一种方法在广泛的矩阵中始终提供最高的性能。因此，需要一个性能预测模型来预测给定稀疏矩阵的最佳SpMV方法不幸的是，预测SpMV在这项工作中，我们开发了一个名为WISE的机器学习框架，该框架可以准确预测不同SpMV方法在给定稀疏矩阵的基线方法上的加速幅度。WISE依赖于一个新的特征集，该特征集总结了矩阵然后WISE可以为每个特定基质选择最佳SpMV方法通过一组近1，500个矩阵，我们表明在24核服务器中使用WISE比使用英特尔的MKL平均加速2.4CCS概念：·计算方法共享内存算法。关键词：稀疏矩阵，SpMV，机器学习1介绍稀疏矩阵向量乘法（SpMV）是最常用的内核之一 它用于处理稀疏线性系统以及各种图形（例如，[7，18，在Nvidia工作。 他可以在syesil@nvidia.com上找到每个人。[2]现在在苹果公司。允许制作本作品的全部或部分数字或硬拷贝供个人或课堂使用，无需付费，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页上带有此通知和完整的引用。版权的组成部分，这项工作所拥有的其他人比ACM必须尊重。允许用信用进行提取复制，或重新发布，张贴在服务器上或重新分发到列表，需要事先特定的许可和/或费用。 请求权限请发邮件至permissions@acm.org。PPoPP©2023计算机协会。ACM ISBN 979-8-4007-0015-6/23/02。- 是的- 是的十五块https://doi.org/10.1145/3572848.3577506Azin Heidarshenas伊利诺伊大学香槟分校heidars2@illinois.edu何塞普·托雷利亚斯伊利诺伊大学香槟分校torrella@illinois.edu20、36]）。示例包括图形算法，如Pager-ank [7]和HITS[20]。此外，许多使用SpMV内核的应用程序是迭代的，使用相同的稀疏输入矩阵执行SpMV多次。因此，SpMV通常会消耗大量的执行周期，这使得它成为一个重要的优化目标。对于来自不同域的各种稀疏输入矩阵，有效地执行SpMV具有挑战性。原因是矩阵可能具有不同的特性，有时会导致SpMV发出低局部内存访问模式。此外，某些访问的数据依赖行为使其难以预测和优化。因此，已经发明了许多SpMV方法来加速SpMV（例如，[21、24、28、32、38、40]）。每种方法都以不同的方式表示矩阵，以克服不规则性挑战并受益于矢量（即，SIMD）指令。不幸的是，由于稀疏矩阵的不同特性，没有一种方法能够始终如一地为所有稀疏矩阵提供最佳性能。因此，我们需要一种机制来识别给定矩阵的最佳SpMV方法，然后选择它。传统上，自动调谐器已通过创建简化的分析模型（例如，[9，17]）。然而，这种模型依赖于一小部分矩阵特征，如行数、列数和非零值，面对现有矩阵的丰富空间，原因在于，SpMV方法可以完全不同地表现取决于矩阵的非零的偏斜和局部性特征此外，自动调谐器会增加大量开销执行死刑在本文中，我们解决这个问题。我们提出了WISE，一个SpMV性能预测器。WISE使用机器学习（ML）来估计不同SpMV方法相对于给定矩阵的基线方法的加速幅度然后，WISE选择最快的方法。WISE使用一组精心设计的功能来总结矩阵此外，WISE使用了一组具有代表性的矩阵训练集，并且易于扩展。为了展示WISE，我们考虑了几种优化，例如用于矢量化的零填充最小化，用于提高局部性的列重新PPoPPSerif Yesil，Azin Heidarshenas，Adam Morrison，and JosepTorrellas330.−元素的计算公式为：对于0≤≤-，=���·，���������������×××···缓存（LLC）位置。这些优化用于流行的方法，如SELLPACK[28]、Sell-c-BACK[21]和LAV[40]。我们对许多稀疏矩阵和几种流行的SpMV方法进行了详细的分析。我们的分析揭示了一个成功的ML为基础的性能预测的要求。基于此分析，我们开发了一个ML模型来预测SpMV方法的加速比然后，我们使用它来选择性能最高的SpMV方法。我们的ML模型依赖于一组新颖的矩阵特征，这些特征表征了稀疏矩阵为了总结偏斜属性，WISE使用一般统计数据，例如行和列的非零分布的均值、标准差、基尼指数和p比。 为了识别矩阵局部特征，WISE使用矩阵的2D平铺版本中非零分布的统计数据。此外，WISE还使用了额外的统计数据来总结图块的结构。我们分析了一组近1,500矩阵的不同的地方性和倾斜行为。我们表明，使用WISE，我们达到了2.4的平均加速比使用英特尔 为了将这个数字放在透视图中，为每个矩阵选择最快方法的Oracle方法获得了2.5的平均加速比。此外，WISE实现了1.14的平均加速比更先进的英特尔MKL检查器执行器，其预处理开销不到50%。由于WISE的用户透明方法，WISE可以成为现有数学库的有效扩展。本文的贡献是：预测SpMV性能的挑战分析。一组矩阵特征，用于表征稀疏矩阵基于ML的框架WISE，为给定的稀疏矩阵选择高性能的SpMV方法• 大量矩阵的WISE的评估2&SpMV优化空间SpMV计算���=������，其中���是稀疏矩阵，���和���分别是密集输出和输入向量。每���1���=01，其中，λ是λ的维数，λ是λ的维数。- 是的在本节中，我们将讨论使用压缩稀疏行（CSR）格式的SpMV的基本实现，以及一些流行的优化SpMV方法。2.1CSR格式和使用CSR的SpMV实现CSR使用三个数组来存储稀疏矩阵：值，列ID和行指针[14]。values数组连续存储所有矩阵行的非零元素。列id中的每个条目对应于值中的一个条目，并存储该元素行指针数组存储每行的第一个非零元素的索引具有CSR的SpMV迭代矩阵行并计算行和输入向量的点积它可以在行上并行化在并行实现中，有不同的方法可以将行调度到线程我们考虑三种方式：动态（Dyn），静态（St）和静态连续（StCont）。 Dyn和St一次将行分配���给线程-动态地或静态地循环。StCont将行除以线程数，并将结果中的连续行组静态分配给线程。2.2使用矢量化实现SpMV我们考虑向量化的SpMV实现，其中线程使用向量指令来同时计算多行。 我们的目标是评估一系列矢量化优化。我们考虑三种类型的优化。 第一个是零填充最小化[21]，它减少了由零引入的不必要的计算和内存开销。当具有不同数量的非零的多个行与向量指令一起处理时，通常会出现这种零第二个优化是列重新排序[40]，它将具有大量非零元素的列移到目标是将频繁访问的输入向量元素放在同一个缓存行中，增加局部性并减少不规则内存访问的影响。第三个优化是分段[40]，它一次处理多组列。 目标是将输入向量的频繁访问部分拟合到LLC中，从而改善LLC局部性。为了对这些优化的不同级别进行建模，我们选择了三种有效的向量化方法，即SELLPACK [28]，Sell-c-���[21]和LAV [40]。此外，我们还使用特殊版本的Sell-c-���和LAV。我们接下来描述所有在我们的讨论中，我们使用图1a所示的示例稀疏矩阵。切片ELLPACK（SELLPACK）。 SELLPACK将���稀疏矩阵的连续行分组为块，将相邻行的非零值打包���在一起。块中的所有行都使用相同的向量指令一起处理因此，如果块中的行具有不同数量的非零值，则将它们填充为相同的长度。 图1b显示了=2的示例矩阵的SELLPACK格式���。SELLPACK可以引入许多零，由于填充，特别是当输入矩阵具有跨行非零的不平衡分布时。 块大小通常由机器的向量单元的宽度给出，并确定填充的程度。对于SELLPACK，我们使用StCont和Dyn调度，因为它们通常是最快的。卖���... Sell-c-���减少SELLPACK的零填充。它首先考虑矩阵的两个连续行的组���然后，它根据非零值的数量以降序对每个组中的行进行重新排序。 通过此操作，每个结果组的���连续行可能具有类似数量的非零行。因此，当应用向量化时，填充量将是WISE：用机器学习预测SpMV的性能PPoPP331c0 c3 c2 c1 c4 c5 c6 c7一CeGHLB DFJKnMOQp r西友≥r0r1r2r3r4r5r6r7(a) 初始矩阵r0r1r2r3r4r5r6r7(b) 销售包装r6r7r5r4(c) 卖...LAV 如果矩阵很大，则输入向量元素在被重新使用之前从LLC中被逐出。因此，完整的LAV算法[40]在CFS之后获取矩阵，并将其划分为称为分段的连续列组。然后，将Sell-c-R变换应用于每个段。段应该足够小，使得与段相对应的输入向量元素适合LLC并得到重用。在实践中，LAV通常只需要将矩阵划分为两个部分。第一段r0r0R6OT=0.7Qp r0包括非零值的���一小部分，其中最佳值为r1r6r2r3R3R7r4r2R5R5r6r1r7r4R0一R3HR5nR7SR1eR2GR4Lcjmy致密节段r2r3r6r7稀疏段一般为0.7。它被称为密集段，因为它具有矩阵中填充最多的列。第二段称为稀疏段。当处理段时，对应的输入向量元素被加载到LLC中并被重用。由于两LAV-1 Seg和LAV使用RFS，我们只考虑Dyn调度，(d) CFS后的初始矩阵(e) LAV-1段(f) LAV就像Sell-C-R图1f显示了LAV的结果矩阵。图1.不同格式的示例稀疏矩阵。更小。图1c显示���了���=4和���=2的示例矩阵的Sell-c格式。需要为每个矩阵调整带宽 的最佳值���取决于非零值在矩阵各行中的分布。 如果大多数行都有类似数量的零，���则可以很小，并且可以接受填充。但是，如果非零的数量高度不平衡，则保持填充可容忍需要较大的Numbers值。在这种情况下，许多行被重新排序，这通常会导致输入向量的空间和时间局部性的损失，因为附近的行往往具 有 类 似 的非 零 模 式 。 对 于 Sell-c-Cable ， 我 们 使 用StCont和Dyn调度，因为它们通常是最快的。Sell-c-R.Sell-c-R将矩阵中的行数设为n。���这种方法对于非零元素在行中的分布非常不平衡的矩阵是有益的对于这些矩阵，Sell-c-R以输入向量的不良缓存局部性为代价来减少填充 我们将所有行的这种重新排序称为行频率排序（RFS）[40]。Sell-c-R使用Dyn调度，因为块之间的非零差异很大，会导致静态调度的负载不平衡。LAV-1段在幂律图的矩阵[22，27]中，行和列中的零的数量是高度不平衡的。因此，输入向量具有较差的时间和空间局部性，并且遭受频繁的LLC未命中。 为了解决这个问题，LAV-1 Seg（对于具有一个分段的LAV [40]）根据非零的数量递减对列进行排序-一种称为列频率排序（CFS）的技术[40]。然后，应用Sell-c-R变换。使用CFS，具有类似非零分布的列通常在时间上连续处理，重用输入向量元素。图1d显示了执行CFS后的初始矩阵然后，LAV-1 Seg应用RFS。结果如图1e所示。因为我们选择T=0.7，所以密集段包括列0、3和2。我们在每个部分执行RFS。表1显示了所用SpMV方法的总结表1.使用SpMV方法。SCH是scheduling的方法Params描述CSRSchDyn、St和StCont的性能取决于矩阵的偏斜特性销售包装SCH，���这会影响填充量，并取决于SIMD宽度和对矩阵结构的影响销售SCH，你好，������控制行顺序。它被调整到最小化在不伤害局部的情况下填充Sell-c-R���专门的Sell-c-版本，其中=。LAV-1段���单节LAVLAV���，矩阵中的非零偏斜越高，选择的最大值应该更高。虽然这五种矢量化方法的矩阵格式不同，但我们设计了一个统一的矩阵格式，然后使用它来实现SpMV。我们在附录A中描述了格式3挑战预测SpMV性能我们的目标是开发一种实用的方法来选择方法和参数，以提供最快的SpMV执行，每个输入矩阵。为此，我们描述了SpMV执行与不同的方法和参数的第2节在广泛的矩阵。 我们使用SuiteSparse 矩阵 集合[15]中的136个大矩阵和 使 用RMAT图形生成器[11]创建的408个大矩阵。SuiteS-parse包含了大部分的科学矩阵，尽管它也有一些社会和网络图。RMAT被广泛使用（例如，在Graph500基准[29]和GAP [5]基准套件中），并且可以生成更广泛的矩阵类型。 我们用它来创建更多的矩阵，如社交网络和网络网络图。 我们在第5节讨论矩阵的细节。为了确保矩阵足够大以获得代表性结果，我们使用具有1-67百万行和列的矩阵但是，我们限制了c0 c1 c2 c3 c4 c5 c6 c7一BeFHC dGJKOSLMnpQyRuR0一BCdr3HJKR2FGR1eC=2σ=4C=2σ=4C=2一BCDeFGHJKLMnOpQRSyuOpQRSyuMnL一CBDOQpRHJKSyuGFC=2nMeLBDFKRuPPoPPSerif Yesil，Azin Heidarshenas，Adam Morrison，and JosepTorrellas332MKLSELLPACKSell-c-σSell-c-RLAV-1Seg LAV1计数××2. 01. 51. 00。50。0矩阵图2. 不同的矢量化SpMV方法和MKL在CSR实现上的加速，为每个特定的SparseSuite矩阵提供最佳调度策略。矩阵按最快的SpMV方法分组在情节上，越高越好。1. 00。80。60。40。2矩阵图3.对于SparseSuite矩阵，使用不同调度算法和MKL的CSR比最佳CSR的加速。非零到20亿，以确保矩阵适合单个共享内存服务器的内存。我们将在第5节中讨论我们的平台和基于OpenMP的并行化策略。我们的分析提供了几个见解：最快的方法因矩阵而异。图4显示了136个SuiteSparse矩阵的SpMV最佳性能方法的分布。我们看到，不同的方法对不同的矩阵更快。例如，这些矩阵中只有34个使用CSR实现了最佳性能，CSR是许多BLAS和图形框架的默认格式。另一方面，Sell-c-Difference是66矩阵的最快方法我们还运行了MKL，并观察到MKL不会为任何矩阵产生最佳性能2 在一种方法中，MKL[13]，它也使用CSR表示。 矩阵按其最佳方法在X轴上分组。该图显示了几个矩阵的名称。考虑SELLPACK，它是25个连续放置的矩阵中最快的。在这些矩阵中，其加速比范围从1.05到1.31。另一方面，Sell-c-decomposition对于66个矩阵是最快的，并且对于这些矩阵，加速比范围从1.00到1.76。预测加速的幅度可以帮助我们在以后考虑方法的预处理成本时选择最佳的SpMV3为一种方法选择正确的参数会显著影响加速比例如，即使是简单的调度选择也会显著影响加速比。 图3显示了CSR实现的性能，60的大小对CSR的加速不同。40即使方法20是最快的矩阵，其实际0与CSR相比的加速变化很大。图2方法使用Dyn、St和StCont调度。对于136个SuiteS- parse矩阵中的每一个，该图显示了它们在最佳调度下相对于CSR的加速比（总是等于或小于1） 我们看到，像调度选择这样的简单参数会显著影响性能，有时会导致10倍的速度下降。Dyn、St和StCont分别在28、16和92个矩阵上获得最佳性能。Dyn是最快的网络和显示，对于套房-解析矩阵，每个方法在图4. SuiteSparse矩阵中SpMV的最快方法。社交网络，而St和StCont在科学矩阵中表现最好该图还显示了MKL图4矩阵大小、局部-CSR实施，并为此采用最佳调度策略矩阵在图中，1.0处的水平线对应于CSR实施。我们还报告了度和偏斜确定最佳方法。 瞥见这三个参数之间的相互作用如何决定最快的方法，我们考虑两个实验，MKLCSR-动CSR-StContCSR-St加速（标准。最佳CSR）加速（标准。最佳CSR）WISE：用机器学习预测SpMV的性能PPoPP3335≥）（−PRRMAT生成的矩阵。它们分别显示了非零偏斜和非零局部性的影响。在第一个实验中，我们分析了稀疏矩阵的偏斜特性我们考虑非零分布的稀疏矩阵行的偏斜 我们使用100个高偏斜（HighSkew）和100个低偏斜（LowSkew）矩阵。在第二个实验中，我们使用100个具有高非零局部性的矩阵（ 即 ， 大 多 数 非 零 在 接 近 矩 阵 对 角 线 的 区 域 中 ）（HighLoc）和具有低局部性的100（即，非零分布在整个矩阵上）（LowLoc）。第4.5节描述了所使用的RMAT参数在每一个100矩阵集合中，我们改变行的数量并平均每行的非零值来模拟不同的特征。对于每行平均非零值较低的大型矩阵，加速比很小。图6显示了LowLoc组（图6a和6b）和HighLoc组（图6c和6d ） 的 相 同 数 据 Sell-c-Rounding 是 高 局 部 性 矩 阵（HighLoc）的最快方法对于LowLoc，Sell-c-���通常是最好的，除了每行具有大量平均非零值的矩阵。 在这种情况下，LAV是最好的，因为它提供了分割。虽然地方是有限的，LAV创建一个部分，可以适合在有限责任公司。对于HighLoc，这是不必要的，因为缓存在没有分段的情况下有效地工作。最后，HighLoc的Sell-c-���加速比幅度高于LowLoc。我们首先考虑偏斜的影响 我们测量了第2节中的每个SpMV方法在LowSkew和HighSkew集上的执行时间。图5a和5 b显示，对于LowSkew，最快的方法及其在最佳CSR上的加速，re-crossing。矩阵的特征在于行数（X轴）和 每 行 非 零 的 平 均 数 （ Y 轴 ） 。 图 5c 和 5d 显 示 了HighSkew的相同数据12811296806448321642 20 2 21 2 22 2 23224225226行数1281129680644832241684220221222223224225226行数1. 81. 61. 41. 21. 0矩阵(a) LowLoc：最快的方法(b) LowLoc：比CSR更1281129680644832164 2202 212 222 2322422522612811296806448322416842202212222232242252261.81.61.41.21.012811296806448321642202 212 222 23224225226行数1281129680644832241684220221222223224225226行数1. 81. 61. 41. 21. 0行数行数(c) HighLoc：最快的方法(d) HighLoc：比CSR更(a) LowSkew：最快的方法(b) LowSkew：比CSR更图6.不同局部性矩阵的性质。12811296806448321642202 212 222 23224225226行数1281129680644832241684220221222223224225226行数1.81.61.41.21.0SuiteSparse矩阵没有许多不同的因子。 图4显示Spars-eSuite矩阵中最快的方法通常是Sell-c-���。然而，我们对图5中的RMAT生成矩阵的实验表明，LAV和LAV-1Seg通常是最快的。出现这种差异是因为SuiteSparse矩阵主要来自(c) HighSkew：最快的方法(d) HighSkew：CSR科学领域或从图，如道路图;不是很多来自幂律图。图5.具有不同偏斜的矩阵的行为。从图5a和图5c中，我们可以看到LAV、LAV-1 Seg和Sell-c-R在大多数情况下提供最高的加速比。 当输入矩阵大于LLC大小（即，行数为22），每行的平均非零数很高（>16）。 LAV的加速取决于矩阵的偏斜;它对于HighSkew矩阵是最高的（图5d）。对于行数较少的矩阵，每行的非零平均数较高，我 们 可 以 通 过 绘 制SuiteSparse矩阵中每行非零的p比率的直方图来看到p比率为1.0%表示行的1.0%具有1������矩阵中的非零元素的分数423020100图7. SuiteSparse中每行的nonze- ros的LAV-1 Seg通常提供最高的性能。这是因为一个片段就足够了当矩阵每行的非零平均数较低，行数较少，特别是偏斜较低时，Sell-c-R通常是最快的方法。这是因为输入向量适合LLC，并且不需要更高级的LAV和LAV-1 Seg格式。图 7 显 示 了 非 零 p 比 的 分 布 。 我 们 看 到 大 多 数SuiteSparse矩阵的p比都大于0.4。这意味着许多矩阵的行中非零分布均衡。这一事实使得SELLPACK和Sell-c-���方法有效。此外，SuiteS-解析矩阵通常具有较少的列数。CSRSellpackSell-c-σSell-c-RLAV-1Seg LAVCSRSellpackSell-c-σSell-c-RLAV-1Seg LAVAve. # nnz/行Ave. # nnz/行Ave. # nnz/行Ave. # nnz/行Ave. # nnz/行Ave. # nnz/行Mtx数量Ave. # nnz/行Ave. # nnz/行PPoPPSerif Yesil，Azin Heidarshenas，Adam Morrison，and JosepTorrellas3342性能模型1特征提取输入矩阵：-大小属性-偏斜特性- 局部性性能类3方法、参数>对方法选择启发式LAV模型LAV-1段模型Sell-c-R模型Sell-c-σ模型销售包装模型CSR模型//第四章转变5选择CSR：无需优化SpMV执行选择的其他方法：根据需要应用CFS、RFS和分段它们中的大多数都少于5M列，允许输入向量适合LLC并减少对LAV的需求。总的来说，SuiteSparse更倾向于使用Sell-c-parse的SELLPACK。如果我们想用一组有代表性的矩阵来训练我们的预测模型，我们需要用更广泛的矩阵来增强SuiteSparse。4WISE：选择最佳SpMV方法鉴于为给定的输入矩阵选择最佳SpMV方法是多么具有挑战性，我们建议利用机器学习（ML）。我们开发了WISE，一个基于ML的框架，为给定的稀疏矩阵选择一个高性能的SpMV方法我们设想WISE可以集成到Graph-BLAS/BLAS框架中，例如IntelWISE的设计对程序员来说是透明的，并且很容易集成到现有的系统中。4.1整体WISE设计WISE由一个新的稀疏矩阵特征集，一组基于ML的性能预测模型，和一个启发式选择最好的SpMV方法考虑的性能预测模型的输出。图8.WISE操作。为了表征每个分布，我们使用平均值（λ）、标准差（λ）、方差（λ2）、最小值 、 最 大 值 、 基 尼 系 数（λ）和p比（λ）。������和n/K行-块nR/K图8显示了WISE的操作。首先，WISE从输入矩阵（1）中提取某些特征的值特征集包括用于识别稀疏矩阵大小以及分布的偏斜和局部特征的特征计算出了(or[22]在一个不平等的分布在最大不平衡分布（即，C座K瓷砖图9.平铺矩阵。非零的。在第二步中，这些特征被传递给一组ML性能模型，这些模型预测这些方法在最佳CSR上的加速（2）.WISE具有针对方法和参数值的每个组合的性能预测模型。接下来，WISE挑选方法和参数值，预测在包括预处理成本的同时提供最高的加速比（3）。然后，它将CSR的矩阵布局转换为所选方法和参数对的布局（4）。如果WISE选择CSR，则不需要转换最后，我们使用选定的方法、参数和矩阵布局运行SpMV（5）。4.2稀疏矩阵特征在第3节中，我们观察到稀疏矩阵基于这些见解和以前的分析[22]，我们选择特征来构建基于ML的性能模型。我们首先将矩阵按逻辑分解为102个具有102行的图块，���������每个切片���的列数，其中，列数和列数是数字矩阵的行和列。我们挑选���基于稀疏矩阵的大小和L2缓存大小，我们将平铺的行和列分别称为行块和列块（图9）。然后，我们考虑非零在行（R）、列（C）、瓦片（T）、行块（RB）和列块（CB）上的分布所有非零值都在一个桶中），则返回值接近1，���接近0。一个完美平衡的分布有一个α=0，���=0.5。此外，我们还记录不为零的桶的数量（������）-即，有一些非零值的桶的数量。我们使用统计数据的命名约定，其中统计数据的名称为汇总统计数据，分布名称为分布名称（R、C、T、RB和CB）。������������������������������������接下来，我们将描述如何使用这些汇总统计数据和其他统计数据为基于ML的性能预测器创建稀疏矩阵特征。表2显示了WISE从输入矩阵中提取的特征，分为矩阵大小、非零偏斜和非零局部性属性。(1) 矩阵大小属性：WISE测量行数（���行数）、列数（列数）和非零值（非零值）。输入向量给出了有关输入向量大小的信息，而输入向量给出了有关要完成的工作量的���(2) 非零偏度属性：WISE使用的功能可以测量跨行（���）和跨列（���）的非零分布的偏度。所收集的统计数字列于表2。分布的特征���决定了用于矢量化的行调度和填充。的特征随机分布决定了对输入向量的存储器访问的不规则性因此，它们可以指示CFS在LAV-1 Seg和LAV中的有效性。(3) 非零局部性属性：WISE使用“”、“”和“”分布来捕捉非零局部性特征K瓷砖列-CSR-StContCSR-动力CSR-StWISE：用机器学习预测SpMV的性能PPoPP335{}{}∞{}{}表2.我们的WISE性能模型中使用的矩阵功能。财产分布度量他们所决定矩阵大小你好，你好，你好������非零偏斜（R）������,������,���2,������,������,������������,������������,������������...2，用于向量化的Cols（C）������ ������ ������ ������ ������ ������������ ���������������������输入向量的内存访问模式非零局部性瓷砖（T）������,������,������2,������,������,������������,������������,���������...2 .........跨切片的RowBlocks（RB）��������� ��������� ��������� ��������� ��������� ��������������� ���������������������������，，2.........L1和L2高速缓存中的存储器访问局部性ColBlocks（CB）��������� ��������� ��������� ��������� ��������� ��������������� ������������������������������������������,���������������,���������_���������������,���������_���������������你知道吗， ���������������������������,���������_���������������������������,���������_���������������������������最后一级高速缓存（LLC）中的存储器访问局部性一个稀疏矩阵。这些特征如表2所示。例如，分布中的低p比���表明非零集中在少数瓦片中。因此，SpMV的存储器访问具有相对高的局部性。WISE还收集每个图块内部非零布局的其他信息。具体来说，对于平铺���，������������������和������������������分别是包含非零的唯一行和唯一列的数量。 如果许多nonze-ros位于同一行或列中，则访问很可能利用局部性。此外，由于数据被布置在高速缓存行中，如果非零在附近，则它们可以共享高速缓存行并进一步增强局部性。因此，WISE还测量������������������������������������独特的瓷砖装饰用的__行和唯一列，非零值被分组为X个相邻行（或列）的组。例如，如果=16，则16个相邻列（或行）将计为单个ID。WISE使用4、 8、 16、 32、 64个值作为“最小值”。要理解它们的用法，请考虑64字节的缓存行。在这种情况下，一条线可能适合四个128位元素（我们感兴趣的是X=4）或八个64位元素（我们感兴趣的是X=8）。如果高速缓存行的多个元素以紧密的时间顺序被访问，则可以获得高速缓存命中WISE得到了、、_���������������、_���������������������������������������������对于每一个瓷砖。然后，它将所有瓦片上的值相加，并将结果除以矩阵中非零的数量。结果值，我们称之为“最后的结果”，���������_���������������,and���������_���������������, are used as matrix features.最后，WISE为每行���测量 其中该行 至少有一个非零（������������������������������）的切片的数量。它还为每个列测量一个类似的指标（）。��� 如果这些指标很高，则LLC中存在数据重用的可能性，因为数据在图块之间重用。此外，WISE还测量每组������连续行中至少有一个非零（���������_������������������������������）的区块数。对于每组������连续列，它还测量一个类似的度量 ， 称 为 ���������_������������������������������ 。 最 后 ， WISE 对 所 有 行（���������������������������）、所有列（���������������������������）、所有���连续行组（���������_���������������������������）和所有���连续列组（���������_���������������������������）取这些测量值的平均值。这些平均值用作矩阵特征（表2）。请注意，100、100、100���、100和100分布不是用于训练我们基于ML的性能预测模型的������相反，我们使用从分布计算的汇总统计量4.3性能预测模型WISE具有用于方法及其参数值的每个组合的性能预测模型我们将决策树用于这些性能模型，这可以被视为创建从数据特征推断的简单决策规则。使用决策树的原因是每个特征使用不同的值范围，因此很难将所有特征标准化为相同的范围。例如，行和列的数量可以以百万为单位，而基尼指数是0和1之间的数字。基于表1的方法和参数，我们有以下WISE模型。CSR有三种模型，分别对应于Dyn、St和StCont调度方法。SELLPACK有尽可能多的模型，所考虑的优先级值和调度机制（StContDyn）。Sell-c-ESTA具有尽可能多的模型，包括ESTA值、ESTA值和所考虑的调度机制（StCont和Dyn）的组合Sell-c-R和LAV-1 Seg的模型数量与Dyn值一样多，因为它们只使用���值。最后，LAV的型号与以下型号的组合一样多：因为它使用了Dyn调度，所以它使用了Dyn值和Dyn值我们挑选n=4， 8，因为这些是被评估机器中向量指令的宽度我们选择k=29， 212， 214来覆盖一系列行为：29和214大致对应于输入向量分别在L1缓存和L2缓存最后，我们选择���= 0。七，零。八，零。9以覆盖不同级别的非零偏斜。最后，我们总共有29个决策树模型的所有SpMV方法和参数考虑。决策树可能会遇到过拟合问题。因此，我们采用了修剪技术。首先，我们将树的最大深度限制为15，以避免创建只有几个样本的分支。其次，我们启用最小成本复杂度修剪，阈值为0.005。这个树的最大深度和这个修剪阈值是使用网格搜索实验性地选择的（6.5节）。此外，我们的决策树使用基尼系数作为分割标准。加速类：每个模型预测方法和参数值组合相对于最快CSR方法的执行时间。具体地，模型可以输出七个类别（C0-C6）中的一个，对应于相对执行时间这些范围是，从较高的（即，较慢的执行）到较低（即，更快的执行）：C 0 =（- 1.05]，C1 =（ 1.05 - 0.95] ， C2 = （ 0.95 - 0.85] ， C3 = （ 0.85 -0.75]，PPoPPSerif Yesil，Azin Heidarshenas，Adam Morrison，and JosepTorrellas336≈ × ≈ ×，≈ ≈≈值小于1的类表示加速。degree/（ #rows#），C4 =（0.75 - 0.65]、C5 =（0.65 - 0.55]和C6 =（0.55 -0]。到创建类C1-C5时，我们创建了加速值1和2之间步长为0.1的类别C0包括所有使用给定方法减速的矩阵，C6包括所有加速比超过2倍的矩阵。的除 了 RMAT 图 ， 我 们 还 包 括 随 机 几 何 图 （ RGG ）[16]。RGG是无向空间图。通过在二维单元网格中随机均匀放置n个顶点来生成RGG。 如果顶点在2D网格中的距离低于给定的距离，则边连接顶点。4.4选择SpMV方法WISE选择提供最高加速比的{方法，参数}对。如果不同方法之间存在加速比，WISE选择预处理成本最小的方法。对于此成本，我们使用以下顺序（从低成本到高成本 ） ： CSR 、 SELLPACK 、 Sell-c-BACK 、 Sell-c-R 、LAV-1 Seg和LAV。此外，为了打破方法的不同参数之间的联系，我们将方法的参数我们根据经验观察到，较小的参数提供较低的预处理时间。例如，���对于LAV，顺序为���= 70%、80%和90%。4.5创建代表性训练集ML模型需要一个有代表性的训练集来执行预测。然而，我们在第3节中的分析表明，SuiteSparse中的矩阵没有太多不同的行为。因此，为了获得代表性的训练集，我们使用RMAT [11] 随 机 图 生 成 器 生 成 的 一 组 矩 阵 来 增 强SuiteSparse。 我们使用精心选择的参数来模拟SuiteSparse中没有很好表示的方面。RMAT生成器有3个参数：（1）节点数，（2）平均节点度，以及（3）������������边落入四个象限中的每一个象限的概率（���������+���=1）。 为了放置边缘，根据概率选取矩阵的四分之一。 所选象限再次被划分为四个象限，并且重复该过程，直到在单个矩阵单元处结束。为了获得偏态矩阵，我们从Graph500 [29]参数������������开始，即=0.57，= 0.19，= 0.19，=0.05（高偏态）。它们生成一个幂律图。然后，我们���在增加���的���同时减小参数，���并且在创建社区结构的同时具有较小的偏斜（���>���）。我们分析了两种图形类型，参数分别为：=0.46，=0.22，=0.22，���=0.10（MedSkew）������������，对于HighSkew、MedSkew和LowSkew图，行的非零分布的p比率分别为0.1、0.2、为了获得具有不同位置的矩阵，我们从������������其中，非零值均匀分布在所有列和行上。我们得到的矩阵与非零聚集在对角线上相等地增加的参数和减少，ing与相同数量的������使用MedLoc（λ=λ=0.35，������������������=起来 对于L