一种动态变化网络环境下深度学习模型的加速执行方法

摘要

本发明公开一种动态变化网络环境下深度学习模型的加速执行方法，利用网络流算法对DAG类型的神经网络进行切割，允许在将DNN同时部署在边缘端和云端，限制了数据传输的同时也加速了推理。利用无向图割顶的性质，提出了一种两步方法减少了最小割模型的决策时间。利用新的时延测量方法，与其他方法相比，该方法能够达到减少推理时延和提高吞吐量的效果。方法可以自适应的根据网速对卷积神经网络进行切割，当网速较快的时候，尽可能的将计算任务交给云端处理，而当网速较慢的时候，尽可能的将计算任务在边缘进行计算，将中间结果传输到云端进行处理。

说明书

技术领域

本发明提供一种动态变化网络环境下深度学习模型的加速执行方法，主要应用于物联网、边缘计算领域，涉及神经网络算法，以及网络流，Tarjan算法。

背景技术

深度学习近年来取得了很多进展，在很多领域得到了广泛的应用。特别是在计算机视觉领域，将图像识别和视频分析的速度和准确度提高到了一个新的高度。许多的物联网设备配合强大的云计算平台拓展出了许多基于深度学习的视觉应用。例如，自动驾驶技术，车载摄像头产生的视频流数据通过上载到服务器，服务器对视频中的图像进行语义分割和目标检测，然后将数据回传到自动驾驶的决策中心。谷歌眼睛上的智能玻璃捕捉图像并传输到云端进行分析，云端将分析结果回传到智能玻璃并显示出来，实现人类和现实场景的实时交互。

深度学习技术极大地推动了上述物联网应用的发展。其通常采用的方法是以云为中心，将物联网设备产生的图像通过长广域网传输到具有强大计算能力的云端，云端进行推断之后再将结果返回到设备。但是传统以云为中心的方法极大的依赖网络条件，在网络条件差的情况下会造成较大的时延和能量消耗。例如，自动驾驶摄像头捕捉的视频，每秒产生的数据可达750MB，若完全不在物联网设备上进行处理，上载如此巨量的数据到云端所造成的时延是不可接受的。若完全依靠物联网设备处理这些数据，也是十分困难的，由于物联网设备本身受到的计算能力，内存和能量限制，而深度学习模型往往十分的占据内存，其不能完全取代云计算。例如，VGG16模型，平均每张图片所需的内存大小为93MB，在树莓派3B上进行一次完全推理的时间需要2秒钟以上。

针对这个问题，近年来人们提出了一些解决方法，一种是采用边缘和云端联合进行推断的方式实现推理加速。如图1所示，可以看到，AlexNe的特点是卷积层的输出远远小于原始输出，卷积层输出最多能达到284KB，而卷积层的能耗远远小于全连接层。根据CNN的这个特点，研究者提出了一系列的解决方案。这类解决方案是将模型抽象成一条链或者有向无环(DAG)，并根据所给的限制条件根据网络带宽的情况自适应的切分神经网络，把神经网络不同层放置在不同设备上运行。比如Neurosurgeon，DADS。另一种是减少神经模型尺寸和计算次数的方法，比如设计轻量化网络或者对模型进行压缩。模型压缩可以通过修剪现有CNN的权重来实现，即通过将一些权重设置为零来使过滤器稀疏，或者通过设计权重较小的紧凑层来减少参数量。例如，MobileNet、GoogLeNet和SqueezeNet。还有一类方法是设计多出口网络模型，这种类型的神经网络从低到高有多个分类分支，当分类目标的置信度到达阈值以上时，就能在该层将分类结果确定，而不需要往更深层进行传输，减少了传输的数据。代表性的工作有BranchyNet、DDNN。

上述的边云协同推理方法虽然可以自适应的进行模型切分，但存在如下不足。1)DNN的最新进展表明DNN不再局限于链式拓扑，DAG拓扑越来越受欢迎，以前针对链式拓扑结构的方法无法对DAG拓扑结构的神经网络进行自适应切分。例如，在2014年和2015年获得ImageNet挑战赛冠军的GoogleNet和ResNet[2]的拓扑结构都是DAG模型。以Neurosurgeon为首的链式拓扑切割方法，在这些情况下是不能对这些模型进行有效的切分的。2)对DAG拓扑结构的神经网络进行切分的工作，如DADS，时间复杂度很大。考虑到切分的决策一般是在资源受限的终端设备上进行，可用性收到影响。3)已有模型对每层的时间估计不准确。之前的所有工作，每层的运行时间是独立计算的，但这个不符合实际情况。实际上，现有的很多机器学习框架对于激活函数进行了优化，这导致多个层整体运行时间和单独每层的运行时间之和是存在很大差异的。这些优化导致已有的这些切分方法在真正的边缘环境中不能达到最优的效果。

本发明所用到的名词解释如下：

边缘计算：是指在靠近物或数据源头的一侧，采用网络、计算、存储、应用核心能力为一体的开放平台，就近提供最近端服务。

神经网络：是一种应用类似于大脑神经突触联接的结构进行信息处理的数学模型。在工程与学术界也常直接简称为“神经网络”或类神经网络。

DAG：有向无环图，指没有环路的有向图。

割点：在一个无向图中，如果删除某个顶点以及与该顶点相关联的边以后，图的连通分量增多，就称这个点为割点。

发明内容

发明目的：针对现有技术中存在的问题与不足，本发明提供一种动态变化网络环境下深度学习模型的加速执行方法，由于某些中间CNN层的数据大小明显小于原始输入数据的事实，设计一种DNN切割方法，该方法利用网络流算法对DAG类型的神经网络进行切割，允许在将DNN同时部署在边缘端和云端，限制了数据传输的同时也加速了推理。利用无向图割顶的性质，提出了一种两步方法减少了最小割模型的决策时间。利用新的时延测量方法，与其他方法相比，该方法能够达到减少推理时延和提高吞吐量的效果。该方法用于自动驾驶，视频监控等领域，边缘端没有足够的算力支持神经网络的快速推理，而将原始数据全部传输到云端进行处理会带来带宽拥塞，产生传输时延，而且会带来隐私泄露的问题，我们提出的方法可以自适应的根据网速对卷积神经网络进行切割，当网速较快的时候，尽可能的将计算任务交给云端处理，而当网速较慢的时候，尽可能的将计算任务在边缘进行计算，将中间结果传输到云端进行处理。我们的自适应神经网络切割方法(QDMP)，不仅可以对链式神经网络进行切割，而且还能够对DAG类型的神经网络进行切割，使得计算时延和传输时延达到一个平衡，在动态变化的网络中得到最优解。

技术方案：一种动态变化网络环境下深度学习模型的加速执行方法，包括如下步骤：1)得到卷积神经网络每一层在边缘端和云端的实际运行时间以及每一层输出大小；实时监控网络带宽，根据神经网络每一层输出大小和网络带宽得到传输时延。2)将神经网络的层抽象为节点，具有数据传输的两个节点之间连接一条有向边，得到DAG图。3)对DAG模型进行建模，将每个节点拥有的三个时延属性拆分为三条有向边，并建立超级源点和超级汇点；利用网络流算法寻找该模型的最小割，寻找到最小割在原图上所经过的割边，从该割边集处将整个模型进行切割。4)利用Tarjan算法寻找割点集。5)结合3)和4)设计总体算法实现减少时间复杂度的效果。

步骤1)的具体实现过程包括：

a)对于任意节点v

b)定义集合D

步骤3)的具体建模过程：

在DNN的拓扑图G＝中，每个节点都拥有三个延时

下面我们将说明如何由G构建G′。

添加节点：首先构建三个新的节点，分别记为e，c，o。其中e是网络流的源点，最终和e归为一类的节点代表部署在边缘端的节点。c是网络流的汇点，最终和c归为一类的节点代表部署在云端的节点。o是一个虚拟节点，代表外部输入到G中的数据，其本身不属于V，由于数据总是在边缘端产生的，故o永远和e划分在一个集合。

云端时延：基于G′，我们在e和所有的v∈v之间添加一条单向边，我们称之为”红边”，红边的权值为每个节点在云端的时延。在e和o中添加一条权值为inf的边，确保了最小割不会割到这条边上，从而保证e和o属于同一个集合。

边缘端时延：与b)类似，我们在v∈V和c之间添加一条单向边，我们称之为”蓝边”，蓝边的权值为每个节点在边缘端的时延。o不会和c划分到一个集合，所以c和o之间的边权值为0。

传输时延：其余的边我们都用来捕获传输时延。对于G中的每一对有数据传递关系的节点，其边权就是传输时延，我们称之为”黑边”。但若u有多个后继节点，则每一条边权都会捕获一次传输时延，但在实际中u只需要向所有后继节点传输一次数据。为了保证传输时延只被计算一次，对于原图中出度大于1的节点u，都将其拆为两个节点u和u′，其中u向u′连第u层的传输时延，u′代替u向其所有后继节点连容量为inf的边。o与G的输入节点连接，这条边的权值赋值为外部输入带来的传输时延。

构建出图G′后，我们在G′上使用最小割算法，便可以将G′中的节点部署到两个集合中，对应在G中得到V

步骤4)的过程如下：

使用dfs_clock记录的是每个节点第一次被访问的时间戳，pre[v]表示v第一次被访问到的时间，若pre[v]＝0表示v还未被访问，设置子节点数目child为0。low

假设当前顶点为u，从u开始遍历，遍历u的邻接节点得到其子树数量，若child为1，则u为根节点，在u是根节点的情况下，若u只有一个孩子，那么u肯定不是割点，若u存在一个以上的孩子，那么u节点即为割顶。当u不为根节点时，通过遍历u的所有邻接点v，若v节点还未被访问过，我们递归访问v节点，求得low

将所有iscut[u]为true的节点加入V

步骤5)的过程如下：

使用4中所描述过程求出V

值得注意的是，v

利用最小割算法得到最优割边集

本发明方法：第一，提出了一种新的建模方法对DAG进行切割，修正了原来的方法的不足之处。第二，提出了两步切分方法，能够实时进行DAG结构神经网络的切分。第三，发现了连续多层运行时间和单层时间之和不同的现象。本发明方法能够更准确的对模型进行切分。第四，在实际的设备上做了大量的实验，结果表明我们算法的切分准确度和速度都好于之前的算法。

有益效果：与现有技术相比，本发明提供的动态变化网络环境下深度学习模型的加速执行方法，解决了DAG类型神经网络的切割问题。此外，与别的建模方法相比，最多可以提高66倍的切割速度，达到实时切割的效果。在自动驾驶领域，视频监控领域采用此方法可以对推理进行加速，加快数据分析过程。

附图说明

图1为AlexNet不同层输出数据大小和时延柱状图；

图2为GoogLeNet的部分结构示意图；

图3为图2抽象出来的DAG拓扑结构示意图；

图4为DAG构造网络流模型图；

图5为有向无环图上的割边集和割点示意图；

图6为QDMP方法与仅边缘和仅云端的方法对比柱状图；

图7为QDMP方法与DADS和Neurosurgeon的方法对比柱状图；

图8为三种DAG类型神经网络(AlexNet-Parallel、ResNet18、GoogleNet)的割边集示意图。

具体实施方式

下面结合具体实施例，进一步阐明本发明，应理解这些实施例仅用于说明本发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发明的各种等价形式的修改均落于本申请所附权利要求所限定的范围。

一种动态变化网络环境下深度学习模型的加速执行方法，包括1)得到卷积神经网络每一层在边缘端和云端的实际运行时间以及每一层输出大小；实时监控网络带宽，根据神经网络每一层输出大小和网络带宽得到传输时延。2)将神经网络的层抽象为节点，具有数据传输的两个节点之间连接一条有向边，得到DAG图。3)对DAG模型进行建模，将每个节点拥有的三个时延属性拆分为三条有向边，并建立超级源点和超级汇点；利用网络流算法寻找该模型的最小割，寻找到最小割在原图上所经过的割边，从该割边集处将整个模型进行切割。4)利用Tarjan算法寻找割点集。5)结合3)和4)设计总体算法实现减少时间复杂度的效果。具体包括如下内容：

(1)神经网络抽象为DAG模型并对边权赋值

以层为粒度对DNN进行建模，每一个DNN模型都可以被建模为一张DAG图，DNN的每一层都是DAG上的一个顶点，有数据传递关系的两层是DAG上的一条边，层是不可分割的。每一层必须在边缘端或者云端处理。

令G＝代表DNN的DAG结构，其中V＝{v

DAG中含有三种权值，由于每个顶点都可以放置在云端或者边缘端进行处理，故每个顶点在其所处的位置都有一个权值，我们使用

(2)构造网络流模型

在DNN的拓扑图G＝中，每个节点都拥有三个延时

下面将说明如何由G构建G′。

a)添加节点：首先构建三个新的节点，分别记为e，c，o。其中e是网络流的源点，最终和e归为一类的节点代表部署在边缘端的节点。c是网络流的汇点，最终和c归为一类的节点代表部署在云端的节点。o是一个虚拟节点，代表外部输入到G中的数据，其本身不属于V，由于数据总是在边缘端产生的，故o永远和e划分在一个集合。

b)云端时延：基于G′，我们在e和所有的v∈V之间添加一条单向边，我们称之为”红边”，红边的权值为每个节点在云端的时延。在e和o中添加一条权值为inf的边，确保了最小割不会割到这条边上，从而保证e和o属于同一个集合。

c)边缘端时延：与b)类似，我们在v∈V和c之间添加一条单向边，我们称之为”蓝边”，蓝边的权值为每个节点在边缘端的时延。o不会和c划分到一个集合，所以c和o之间的边权值为0。

d)传输时延：其余的边我们都用来捕获传输时延。对于G中的每一对有数据传递关系的节点，其边权就是传输时延，我们称之为”黑边”。但若u有多个后继节点，则每一条边权都会捕获一次传输时延，但在实际中u只需要向所有后继节点传输一次数据。为了保证传输时延只被计算一次，对于原图中出度大于I的节点u，都将其拆为两个节点u和u′，其中u向u′连第u层的传输时延，u′代替u向其所有后继节点连容量为inf的边。o与G的输入节点连接，这条边的权值赋值为外部输入带来的传输时延。

构建出图G′后，我们在G′上使用最小割算法

如图4所示，将说明如何利用以上算法将图4(a)建立为图4(b)，然后利用网络流算法求出割边集。四个顶点中，v

(3)两步切割方法

提出了两步方法减少时间复杂度。第一步是寻找到图G的割点集V

由于DNN的特殊性，其拓扑结构一般是一个长且窄的DAG图，对于链式DNN，其拓扑结构除了首节点和尾节点每一个节点都是一个割点，如图2中DAG所示，v

对于链式拓扑，其最优解必定存在于其拓扑结构的某一个割顶处，这是显而易见的。对于DAG拓扑，虽然在割顶处可以将网络分割开来，但是得到的解并不一定是最优的，在其拓扑结构上有可能存在一组节点，在这组节点处可以得到一组割边，比在割顶处进行分割的时间更少。如图5所示，在v

Theorem：对于DNN的拓扑结构G＝{V，E}，使得总时延最少的最优割边集一定位于V

证明.记图G的最优割边集为E

①若u，v之间没有割顶，那么这组割边就在u和v之间，符合假设。

②若u，v之间存在割顶，对于u和v中的任意割顶s，若E

基于此结论，只需要找到DAG上所有的割点得到V

(4)通过Tarjan算法获取割点集合

割顶的定义是针对无向图的，所以我们首先得到G对应的无向图G′，得到G′的方法很简单，将G中的单向边变成双向边即可。

在G′的DFS树中，割顶有如下定理：

①若u是根节点，如果u有两个及其以上的孩子，那么u是割点；

②若u是非根节点，则其为割顶当且仅当u存在一个子节点v，使得v及其所有后代都没有反向边连回u的祖先；

根据以上定理，可以使用Targin算法求出G′的割点集V

dfs_clock记录的是每个节点第一次被访问的时间戳，pre[v]表示v第一次被访问到的时间，若pre[v]＝0表示v还未被访问。low

(5)两步切割方法整体算法

在V

整体算法描述如Algorithm2所示：使用Algorithm1求出V

两步算法修补了DADS建模方法的缺陷，并且时间复杂度比DADS低很多，DADS直接需要测量每一层的时延，实际操作中比较复杂。DADS的时间复杂度为O((n+m)n

表1.DADS与QDMP方法在不同神经网络上的切割耗时

见表1，实验采取了在三种不同的DAG类型神经网络中做了实验，三种DAG网络分别为AlexNet-Parallel、ResNet18和GoogleNet。采用树莓派3B模拟边缘端，使用8核心Intelcore i7-9700k@3.60GHzCPU和一块NVIDIA RTX 2080i TX GPU模拟边缘端，使用CAT2、3G、4G以及WIFI四种网络环境对本发明的方法进行测试。

首先测试出每种神经网络每层在边缘端的时延，以及每层在云端的时延，并实时监控当前带宽数据。使用keras框架自动获取神经网络的架构，根据架构之间层与层的关系抽象为一个DAG，使用4)中所描述的方法将DAG中的割点集合找到，并使用5)中所描述的算法在子图中构建网络流模型，寻找最佳割边集。

如图8所示，五角星/五边形/菱形/三角形处分别代表了在4种不同网络带宽下本发明方法所找到的割边集合。网速越慢，QDMP越有可能在DAG的较深处对神经网络进行切割，使得传到云端的数据尽可能的少；网速越快，QDMP越有可能在DAG的较浅处对神经网络进行切割，使得边缘端的计算压力尽可能的小。

从实验结果来看，该方法能够根据带宽自适应的对神经网络进行切割，针对DAG类型神经网络找到最优划分割边集，我们可以发现在不同的网速下QDMP选择的切割点都是不同的，并且符合我们的预期，实验结果表明QDMP方法显著减少了时延并增加了吞吐量。