一种双重约化的矩阵乘法的分块参数空间优化方法

摘要

本发明涉及一种双重约化的矩阵乘法的分块参数空间优化方法，属于计算机数值计算领域，该方法包括以下步骤：S1：输入矩阵乘法算子；S2：获取相关的信息，选取DNMM变换；S3：定义优化Schedule；S4：计算参数空间；S5：计算缓存复杂度约束和向量化约束；S6：对参数空间进行过滤；S7：从候选参数空间中选取优化参数，结合DNMM变换和Schedule，计算矩阵乘法。本发明能够过滤掉那些由缓存和并行理论指导下的无法提供最佳性能的候选参数组合，用以解决将矩阵乘法的分块和并行计算扩展到多维度问题，能够提高矩阵乘法的计算效率。

说明书

技术领域

本发明涉及一种双重约化的矩阵乘法的分块参数空间优化方法，属于计算机数值计算领域，尤其适用 于基于数组打包的矩阵乘法的分块参数空间优化。

背景技术

深度学习的发展对各个科学领域产生了深远的影响，在自然语言处理(NLP)和计算机视觉(CV)等 人工智能领域有显著的价值。随着卷积神经网络(CNN)、递归神经网络(RNN)、长短时记忆(LSTM) 和生成性对抗性网络(GAN)等多功能深度学习模型的出现，为了实现其广泛部署和应用于各种硬件终端 设备上，尤其是边缘设备和移动终端等，必须将神经网络模型优化到极致。

在工业界和学术界，为了加速各种深度学习(Deep Learning，DL)芯片上的DL模型，将计算映射到 DL高效的芯片是非常重要的。在通用芯片上，高度优化的线性代数库——如基本线性代数子程序(BLAS) 库(如MKL和cuBLAS)——是有效计算DL模型的基础。以卷积操作为例，DL框架将卷积转换为矩阵 乘法，然后调用BLAS库中的通用矩阵乘法(General Matrix Multiplication，GEMM)函数。然而，依赖 于上述库和工具在不同的DL芯片上映射DL模型的缺点是它们通常落后于DL模型的快速发展，因而不 能有效地利用DL芯片。

为了解决DL库和工具的缺陷，以及减轻手动优化每个DL芯片上的DL模型的负担，DL社区求助于 领域特定的编译器技术来拯救。以陈天奇的TVM为例，DL编译器将DL框架中描述的模型定义作为输入， 并在各种DL芯片上生成有效的代码实现作为输出。其中由算子操作和优化参数空间定义共同构成的调优 空间决定了性能的上限，且往往这个空间是巨大的，其中造成优化参数组合爆炸的主要是多维度多层次的 候选分块的参数空间过大，这又和矩阵的大小以及选择的分块策略密切相关。一种分块策略是选择2的幂 次，在许多关于GEMM优化的建议中，常常假设矩阵的大小是2的幂次，这是不现实的。例如，在深层 神经网络中，卷积是通过将其转化为GEMM问题来实现的，其中矩阵的大小不是2的幂次方；另一种策 略则是使用因子，例如陈天奇在2018年的研究“Learning to Optimize TensorPrograms”中使用矩阵大小因 子作为分块大小，这样做的一个好处是避免在代码中生成条件测试带来的开销。然而，当矩阵大小的因素 较少时，在外部情况下，矩阵大小是一个素数，如此狭窄的候选分片大小范围不能保证覆盖最佳的分块大 小。

Sato，Yukinori在2019年的研究“An Autotuning Framework for ScalableExecution of Tiled Code via Iterative Polyhedral Compilation”中提出应该在分块程度和并行负载之间找到最佳的平衡点，以适应缓存 内存的复杂性能行为。但其方法仅考虑了单一并行维度且未能利用缓存复杂度等静态分析手段分析所使用 算子用例的缓存行为特征。

发明内容

有鉴于此，本发明提供一种双重约化的矩阵乘法的分块参数空间优化方法，通过对矩阵乘法循环程序 进行分块参数的优化，过滤掉那些由缓存和并行理论指导下的无法提供最佳性能的候选参数组合，用以解 决将矩阵乘法的分块和并行计算扩展到多维度问题，提高矩阵乘法的计算效率。

为达到上述目的，本发明提供如下技术方案：

一种双重约化的矩阵乘法的分块参数空间优化方法，包括以下步骤：

S1：根据工程系统问题，建立数学模型，提取其中矩阵乘法算子作为输入；

S2：获取矩阵乘法算子中相乘矩阵的维度信息、运算浮点数精度要求、计算机硬件系统的信息，选取 双重约化矩阵乘法(Dense No-pack Matrix Multiplication，DNMM)变换；

S3：根据DNMM变换定义优化进程(Schedule)，对循环程序的分块进行优化；

S4：根据相乘矩阵的维度信息，计算出矩阵乘法算子操作的参数空间；

S5：计算针对DNMM变换的缓存复杂度约束和向量化约束；

S6：根据缓存复杂度和向量化约束，对参数空间进行过滤，得出合理的候选参数空间；

S7：采用迭代方法从候选参数空间中选取优化参数，结合DNMM变换和Schedule，计算矩阵乘法。

进一步，步骤S1和步骤S2所述的矩阵乘法的算子形如：C

进一步，步骤S2中所述的维度信息为M、K、N的数值，其中，

为了更好的描述本发明，本发明中，

进一步，所述的DNMM算法具体实现为：

S401：在K维度上按照K

S402：按照

需要说明的是，本发明所涉及的DNMM算法来源于“Learning to Optimize TensorPrograms”(TVM) 基于CPU的矩阵乘法实现，本发明在其基础上做了关于分块和向量化的通用抽象。

进一步，步骤S3所述的优化Schedule为对DNMM算法的循环程序进行优化，通过对分块上限的定 义，选取合适的分块因子进行循环程序的分块实现，具体循环程序的分块过程为：

(1)在N维度上进行循环程序的分块，初始对应的循环次数为N次，现将循环程序从外至内分为

(2)在K维度上进行循环程序的分块，初始对应的循环次数为K次，将循环程序从外至内分为

(3)在M维度上进行循环程序的分块，初始对应的循环次数为M次，现将循环程序从外至内分为

进一步，步骤S4所述的参数空间G的计算过程为：

S601：计算CPU的核心数P的所有整数因子序列

S602：获取矩阵的维度M和N，遍历序列

S603：获取矩阵的维度K的值，计算K的所有整数因子构成的集合G

S604：按顺序遍历对应的序列G

S605：构造参数空间G＝{(M

特别地，参数是以数组的形式(M

进一步，步骤S5所述的DNMM的缓存复杂度约束为：T＜Z

其中，

DNMM的向量化约束为：K

进一步，步骤S6具体为：参数空间G中随机选择一组参数数组，计算出缓存复杂度和向量化约束， 对参数空间中不符合约束条件的(M

值得一提的是，本发明将解决的问题，不仅限于深度学习编译优化框架下的分块参数空间优化，还有 应用于诸如MATLAB，ATLAS，PLUTO等用于矩阵运算分块优化工具中。

本发明的有益效果在于：本发明提供了一种双重约化的矩阵乘法的分块参数空间优化方法，结合缓存 复杂度分析，重新定义初始化的参数空间，通过对矩阵乘法循环程序进行分块参数的优化，过滤掉那些由 缓存和并行理论指导下的无法提供最佳性能的候选参数组合，用以解决将矩阵乘法的分块和并行计算扩展 到多维度问题，能够提高矩阵乘法的计算效率。

附图说明

为了使本发明的目的、技术方案，本发明提供如下附图进行说明：

图1为本发明提供的一种双重约化的矩阵乘法的分块参数空间优化方法流程构架图。

具体实施方式

为使本发明的技术方案、实施例的目的以及系统架构的优点等更为明晰，下面将结合附图1，对本发 明的优选实施例进行详细的描述。

实施例1：计算机实验平台配置如下：操作系统为64位Linux4.4.0，编译器为GCC5.4.0，处理器为 Intel(R)Core(TM)i7 G9700F，CPU主频为3.00GHz，核心数为8，内存为8GB。针对工程系统问题仿真实 验中的数学模型在数值求解过程中的矩阵乘法问题，本发明提供了“一种双重约化的矩阵乘法的分块参数 空间优化方法”，结合图1，具体步骤为：

步骤一：数学模型进行数值求解可转化为线性方程，形如：“a·x＝b”，进一步求解需要计算x＝a

步骤二：获取矩阵乘法算子中相乘矩阵的维度信息、运算浮点数精度要求、计算机硬件系统的信息， 选取DNMM变换；所述的维度信息为M、K、N的数值，其中，

进一步，所述的DNMM算法具体实现为：

(1)在K维度上按照K

(2)按照

步骤三：根据DNMM变换定义优化Schedule，对循环程序的分块进行优化；所述的优化Schedule为 对DNMM算法的循环程序进行优化，通过对分块上限的定义，选取合适的分块因子进行循环程序的分块 实现，具体循环程序的分块过程为：

(1)在N维度上进行循环程序的分块，初始对应的循环次数为N次，现将循环程序从外至内分为

(2)在K维度上进行循环程序的分块，初始对应的循环次数为K次，将循环程序从外至内分为

(3)在M维度上进行循环程序的分块，初始对应的循环次数为M次，现将循环程序从外至内分为

步骤四：根据相乘矩阵的维度信息，计算出矩阵乘法算子操作的参数空间

(1)：计算CPU的核心数8的所有整数因子序列

(2)：获取矩阵的维度M和N，遍历序列

(3)：获取矩阵的维度K的值，计算K的所有整数因子构成的集合G

(4)：按顺序遍历对应的序列G

(5)：构造参数空间G＝{(M

步骤五：计算针对DNMM变换的缓存复杂度约束和向量化约束；所述的DNMM的缓存复杂度约束 为：T＜512，

其中，

DNMM的向量化约束为：K

步骤六：根据缓存复杂度和向量化约束，对参数空间进行过滤，得出合理的候选参数空间。

步骤七：采用迭代方法从候选参数空间中选取优化参数，结合DNMM变换和Schedule优化的循环程 序，计算矩阵乘法。

经过当下最为流行的深度学习编译框架之一的TVM中加以验证，本发明方法能够实现优化参数空间 的矩阵乘法计算，满足32位浮点数计算精度的要求，矩阵计算的正确性得到了保证。

实施例2：计算机实验平台配置如下：操作系统为64位Linux4.4.0，编译器为GCC5.4.0，处理器为 Intel(R)Core(TM)i7 G9700F，CPU主频为3.00GHz，核心数为8，内存为8GB。针对小(Small)、中(Medium)、 大(Large)规模不同维度的矩阵乘法问题进行性能对比，Small＝{1，8，16}，Medium＝{64，256}， Large＝{1024，4096}，本发明提供了“一种双重约化的矩阵乘法的分块参数空间优化方法”，结合图1，包含 以下步骤：

步骤一：为保证实验数据样本够大，对每个维度进行343次随机生成矩阵实验，将生成的矩阵作为矩 阵乘法算子的输入。

例如，小规模矩阵乘法问题，M∈Small、K∈Small、N∈Small。需要说明的是：M×N×K维度为1×1×1 由于不能分块，故不在实施例实验结果考虑范围。

步骤二：获取矩阵乘法算子中相乘矩阵的维度信息、运算浮点数精度要求、计算机硬件系统的信息， 选取DNMM变换；具体数据的相关设定与实施例1相同。

步骤三：根据DNMM变换定义优化Schedule，对循环程序的分块进行优化。

步骤四：根据相乘矩阵的维度信息，计算出矩阵乘法算子操作的参数空间G。

步骤五：计算针对DNMM变换的缓存复杂度约束和向量化约束。

步骤六：根据缓存复杂度和向量化约束，对参数空间进行过滤，得出合理的候选参数空间G′。

步骤七：采用迭代方法从候选参数空间中选取优化参数，结合DNMM变换和Schedule优化的循环程 序，计算矩阵乘法。

本实施例在矩阵乘法计算的性能加速比和参数空间压缩比上进行了对比，其中，性能加速比是通过 TVM默认的矩阵乘法程序和本发明方法程序矩阵计算时间进行对比，参数空间压缩比是通过本发明方法 的参数空间和TVM默认的矩阵乘法程序的参数空间的对比，实验结果表1所示。虽然性能加速比上本发 明方法略逊，但经验告诉我们，性能加速比在[0.95，1.05]的区间是在合理范围内的，即本发明方法能不会 丢失最佳分块，使用过滤后的空间覆盖了最佳的参数配置，并且将原有的参数空间缩减为原来的约 71.085％。

表1 实施例2对比实验结果

实施例3：由于实施例2考虑的维度都是2的幂次，有利于矩阵乘法的分块计算，在实施例2的计算 机配置的基础上，现针对特殊的维度上无明显分块的素数，采用本发明方法进行性能对比实验。采用本发 明的方法具体实施步骤与实施例2相同。

本实施例中，M∈{7，11，13}、K∈{23，67，191，383}、N∈{23，67，191，383}，同样对每个维度进行343次随 机生成矩阵实验。所不同的是，本实施例中，由于素数无法分解，从而无法简单的进行程序的分块，故而 需要对TVM提供的矩阵算法进行改进，选取TVM提供的计算策略，以便提升计算效率。

TVM提供了“factors”、“power2”和“verbose”，其中，factors为默认的矩阵乘法的分块策略，为维 度因子分块策略；power2为维度向下兼容的最大幂数的因子分块策略；verbose为前两者策略所有因子的 总和进行分块的策略。例如：对M维度采用power2的策略，在TVM中的程序语句为：cfg.define_split(″tile_x″， M，num_outputs＝3，policy＝″power2″)。需要说明的是，本实施例对所有维度都采取相同的分块策略。

本实施例在矩阵乘法计算的性能加速比和参数空间压缩比上进行了对比，实验结果如表2和表3所示。 其中，性能加速比是通过TVM默认(factors)的矩阵乘法程序和本发明方法程序矩阵计算时间进行对比， 参数空间压缩比是通过本发明方法的参数空间和TVM默认(factors)的矩阵乘法程序的参数空间的对比。

表2 实施例3性能加速比对比实验结果

表3 实施例3参数空间压缩比对比实验结果

本实施例可以看出，本发明虽然在参数空间膨胀较大，但大幅度提高了84.8％的计算效率。

最后说明的是，以上优选实施例仅用以说明本发明的技术方案而非限制，尽管通过上述优选实施例已 经对本发明进行了详细的描述，但本领域技术人员应当理解，可以在形式上和细节上对其做出各种各样的 改变，而不偏离本发明权利要求书所限定的范围。