基于最长路融合算法的深度学习计算图优化方法

摘要

本发明公开了一种基于最长路融合算法的深度学习计算图优化方法，包括：1)使用最小代价子图划分估计深度学习计算图的算子融合的加速效果，2)根据代价函数近似得到出一种跨层算子融合规则，3)标记计算图边权，用动态规划求解算子最长路标号，4)使用并查集算法融合标号相同的算子。此方法在保证优化额外开销比较小的同时，显著提高深度学习框架的速度。

说明书

技术领域

本发明涉及人工智能技术领域，尤其涉及一种可用于计算图的算子融合方法。

背景技术

随着大数据与硬件计算能力的增长，以深度学习为代表的人工智能技术在深度学习框架的支撑下快速发展，在计算机视觉、自然语言处理、智能机器人等领域超越传统方法，逐渐成为了科学研究与工程应用的新范式。大部分的深度学习框架采用了Python作为前段语言，后段采用C、CUDA等语言进行加速，计算图(或称为数据流图)是沟通两者的桥梁。

随着使用的训练数据的增加，深度神经网络的参数量、复杂度的扩大，计算图包含的算子数量也迅速增加，在计算图上进行运算和访存需要的时间也快速提高，已经远远超出了硬件性能增长速度。因此，为了支持前沿学术研究与工程应用，原始计算图需要优化，以降低额外存储和运算开销。

发明内容

(一)所要解决的技术问题

本发明要解决的技术问题是：

给定一个深度学习网络的计算图，如何融合计算图的算子，减少计算过程中的访存次数，同时保证计算图不产生自环导致无法计算，从而实现神经网络的加速。

(二)技术方案

为了解决上述技术问题，本发明提出一种基于最长路融合算法的深度学习计算图优化方法，其技术方案为：

首先将算子融合问题转化为最小代价子图划分问题。该方法将计算图看做一个有向无环图，其中，每一个节点代表一个算子，每一条边代表一个变量。如果一条边是一个顶点的入边，则代表对应的变量，为该顶点对应的算子的输入变量。

计算图中的节点分为可融合算子和不可融合算子。可融合算子之间可以融合，不可融合算子则不能和任何算子融合。本方法将算子融合问题形式化成图划分问题。此方法规定合法的划分方案需要满足如下要求：每一个节点都要唯一地属于一个子图；不可融合的算子必须单独存在于子图中，即该子图不包含其他节点；如果一条边的起始节点和终止节点属于同一个子图，那么这条边也属于子图的边集，否则的话该边将不属于任何子图的边集。

此方法使用代价函数近似估计子图划分后的计算量，该代价函数考虑所有算子的内存读写总大小，即跨越两个不同子图、同时也不属于任何子图的边所对应的变量占用的内存大小的总和。

为了快速地最小化该代价函数，此方法使用跨层算子融合规则，除了规定不能融合的情况外，算子应当尽量融合，并且算子融合可以跨越神经网络的不同层。不能融合的情况包括：1)重索引算子不可以与其相连接的前驱元算子融合，因为这种融合通常会导致性能的下降；2)重索引化简算子不可以和其后继算子融合，这种融合并不会提升性能；3)融合不能产生环，否则计算图无法正常执行。

依据以上规则，将计算图中不可融合的边标记距离为1，其他边标记距离为0，输出节点的标号为0，得到一个带有边权的有向图。对计算图进行拓扑排序，按照此顺序用动态规划计算节点标号，每个节点的标号为其输出节点的标号与输出边的距离的和的最大值。

得到计算图中每个节点的标号后，利用并查集算法对节点进行融合。具体融合方式为，对于计算图的每一条边进行判断，若边的两个节点标号相同、不属于同一个子图，并且边满足融合规则，即边权为0，那么将两个节点所属的子图融合为一个子图。从而得到最终的子图划分，最后将每个子图中的所有算子融合为一个算子。

(三)有益效果

上述技术方案具有如下优点：本发明的时间复杂度与计算图中变量数量成线性关系，因此能够在优化额外开销非常小的情况下，显著提高计算性能。对ResNet、DenseNet等深度神经网络模型进行的实际测试表明，此发明找到的计算图融合方案与最优融合方案性能无显著差别。

附图说明

图1为本发明所提出算法的步骤流程图；

图2为本发明所提出基于最长路标号的算子融合示意图；

具体实施方式

下面结合附图和具体实施例对本发明做进一步详细描述。

本发明公开了一种基于最长路融合算法的深度学习计算图优化方法，给定一个深度学习网络的计算图，如何融合计算图的算子，减少计算过程中的访存次数，同时保证计算图不产生自环导致无法计算，从而实现神经网络的加速。

将算子融合问题转化为最小代价子图划分问题。该方法将计算图看做一个有向无环图，其中，每一个节点代表一个算子，每一条边代表一个变量。如果一条边是一个顶点的入边，则代表对应的变量，为该顶点对应的算子的输入变量。同理，如一条边是一个顶点的出边，则代表对应变量为对应算子的输出变量，需要注意的是，每个算子都可能有多个输入以及多个输出。

计算图中的节点将被分为两类，分别为可融合算子和不可融合算子。可融合算子之间可以融合，不可融合算子则不能和任何算子融合。本方法将算子融合问题形式化成图划分问题。计算图被划分成若干个子图，每一个子图就代表了一个融合算子；一个图可以有很多种划分方案，但此方法规定合法的划分方案需要满足如下要求：每一个节点都要唯一地属于一个子图；不可融合的算子必须单独存在于子图中，即该子图不包含其他节点；如果一条边的起始节点和终止节点属于同一个子图，那么这条边也属于子图的边集，否则的话该边将不属于任何子图的边集。

此方法使用代价函数C近似估计子图划分后的计算量，其具体形式为：

其中ω

为了快速地最小化该代价函数，此方法使用跨层算子融合规则，除了规定不能融合的情况外，算子应当尽量融合，并且算子融合可以跨越神经网络的不同层。不能融合的情况包括：1)重索引算子不可以与其相连接的前驱元算子融合，因为这种融合通常会导致性能的下降；2)重索引化简算子不可以和其后继算子融合，这种融合并不会提升性能；3)融合不能产生环，否则计算图无法正常执行。

依据以上规则，将计算图中不可融合的边标记距离为1，其他边标记距离为0，输出节点的标号为0，得到一个带有边权的有向图。对计算图进行拓扑排序，按照此顺序用动态规划计算节点标号，每个节点的标号为其输出节点的标号与输出边的距离的和的最大值，即为到输出节点的最长路的距离。

得到计算图中每个节点的标号后，利用并查集算法对节点进行融合。如图2所示，具体融合方式为，对于计算图的每一条边进行判断，若边的两个节点标号相同、不属于同一个子图，并且边满足融合规则，即边权为0，那么将两个节点所属的子图融合为一个子图。从而得到最终的子图划分，将每个子图中的所有算子融合为一个算子，这样的到融合是合法且高效的。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明技术原理的前提下，还可以做出若干改进和替换，这些改进和替换也应视为本发明的保护范围。