为什么您的人工智能不再需要云就能运行得更快了

作者： Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen 摘要： 在流数据上进行深度神经网络（DNN）推理需要计算资源来满足推理吞吐量要求。然而，对于延迟和隐私敏感的深度学习应用来说，由于隐含的传输成本以及对第三方云提供商缺乏信任，它们无法负担将计算卸载到远程云。在保持计算在受限环境中的解决方案中，硬件加速可能很繁琐，模型优化需要大量的设计工作，同时会损害准确性。DNN分区是第三种补充方法，它由将推理工作负载分布在几个可用的边缘设备上组成，同时考虑边缘网络的特性和DNN的结构，目标是最大化推理吞吐量（每秒推理次数）。本文介绍了一种预测多线程分布式DNN部署的推理和传输延迟的方法，并定义了一个优化过程来最大化推理吞吐量。然后，我们提出并分析了一个分支定界求解器，以量化实现的性能和复杂性。该分析促成了加速区域的定义，该区域描述了DNN和网络特性在何种确定性条件下DNN分区是有益的。最后，实验结果证实了模拟，并显示了在示例边缘部署中推理吞吐量的提高。 边缘的DNN分区可以在降低到中央服务器（例如云）的带宽使用和延迟的同时，加速推理吞吐量。 引言 2020年，互联设备每天产生约25亿字节的数据。 在此背景下，人工智能（AI）是能够最好地处理日益增长的数据量的一项技术，其应用领域广泛，如计算机视觉中的物体检测、面部识别、语音识别、自然语言处理或自动驾驶。AI，特别是深度学习（DL），除了需要大量数据外，还需要强大的处理能力和内存，这使得云计算成为AI工作负载的 托管解决方案。因此，2019年，96%的AI任务在云端运行。 1 事实上的 2 AI应用程序可能面临严格的延迟限制， ，在自动驾驶、制造监控或任何涉及与现实世界交互的实时推理中。例如，自动驾驶的平均响应时间要求低于100毫秒 ，这使得往返云端的时间对于这些应用来说太长了。类似地，某些应用程序可能会在网络上产生大量的链路使用， ，在计算机视觉中的高质量视频处理的情况下，这会阻止它们在云端运行。数据隐私策略或数据保护法规也可能禁止数据离开特定环境。这促使AI部署到边缘计算，即将计算任务从数据中心迁移到更靠近边缘设备的地方， ，靠近数据源。 例如 [](javascript:void()) 例如 即 与公共云相比，边缘是一个资源受限的环境，存在重要限制 ，因此为边缘开发AI与为云开发AI本质上是不同的。由于设备容量较低、可用资源缺乏弹性以及边缘网络的异构性，在数据源附近分析数据可能具有挑战性。降低计算能力意味着降低可实现的推理吞吐量，这进一步加剧了将重负载从云端迁移到边缘的难度。在某些应用中，推理吞吐量， ，DNN可实现的每秒推理次数，可能与DNN的准确性相关， ，在视频流中的对象跟踪中，将推理速率从每秒15次降低到5次已被证明会使对象检测器的F1分数__3__降低10% 。换句话说，推理吞吐量低的部署可能导致关键信息丢失， ，在视频监控应用中丢失检测。 [](javascript:void()) 即 例如 [](javascript:void()) 例如 在受限的边缘网络上满足性能要求主要有两种方法：模型压缩或硬件加速。 包括将神经网络缩小和优化为模型的轻量级、通常性能较低的版本。标准的模型压缩方法包括剪枝 ， ，去除模型中不必要的参数；量化 ， ，减少存储模型分配的内存；以及知识蒸馏 ， ，训练一个较小的神经网络，其中提取了来自较大网络的知识。模型优化需要大量的设计工作，并且可能阻碍模型准确性。 在边缘设备上意味着寻找既节能又轻巧，同时仍能以足够高的性能运行推理的硬件。边缘加速有几种类型的候选硬件，其效率和特异性各不相同，但标准的处理单元未能达到预期，而专用硬件（如ASIC）则被发现不切实际且昂贵 。 模型压缩 [](javascript:void()) 即 [](javascript:void()) 即 [](javascript:void()) 即 硬件加速 [](javascript:void()) DNN分区是一种补充方法，通过利用边缘网络中现有设备的数量来加速推理，将推理计算分布开——它可以单独使用，或与其他两种方法结合使用。DNN分区包括将神经网络视为一个要分割成多个分区的流水线，并将这些分区分发到边缘设备上。这些分区的放置基于DNN和底层网络的特性。DNN分区依赖于识别分割点，这些分割点是模型图中模型被分成多个分区的点。在运行时，分区按顺序运行，每个分区将中间推理结果发送到下一个分区。这使得每个分区可以在其他设备继续处理卸载的数据时开始处理下一个输入数据，从而提高推理吞吐量，如 所示。在本文的其余部分，DNN分区将通过实时视频流推理的示例进行说明。 图1 A. 相关工作 源于移动边缘云卸载的DNN分区方法旨在优化各种性能指标，如计算延迟、能耗、资源利用率、成本或吞吐量。DNN分区依赖于一个或多个这些指标的关联来定义优化目标，以及一种利用该指标来寻找分区方案的方法。例如，Neurosurgeon 寻求单个分割点，将第一个分区保留在边缘并将第二个分区卸载到云端，以最小化延迟和能耗。物联网应用也考虑了多个DNN的联合分区和卸载，以优化能耗、延迟和/或成本，使用了不同的求解器，如结合了粒子群优化（PSO）和遗传算法（GA）的SPSO-GA ，或使用深度强化学习找到分区方案的DDPQN 。其他例子包括DINA ，它定义了一个整数非线性规划（INLP）问题，并使用基于匹配理论的求解器来优化雾网络的延迟和资源利用率。优化推理吞吐量的方法包括DNN surgery ，它利用中间DNN层输出的较小尺寸来在边缘和云之间分区推理计算。这两种算法都创建了两个分区，一个在边缘，另一个在云端。移动边缘云领域的其他研究 也包括云端的多线程计算，以进一步加速整体推理吞吐量。依赖云进行第二个分区推理计算假设网络连接良好，而在一些孤立的边缘部署中，连接性可能很差，这使得这种假设不确定。Edgent 将之前的方法应用于移动设备和可用的边缘服务器，放宽了卸载到云的限制。这种方法与特定的训练和模型架构相关，并且仍然将分区限制为两个分区。其他方法考虑了多个分割点， ，IONN ，它描述了最小化延迟和能耗的分区问题，同时还考虑了将模型上传到边缘服务器的时间。 [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) 例如 [](javascript:void()) 这些方法要么与远程云交互，要么在分区的性质上受到限制， ，要求精确地分成两部分，无论是否使用多线程。列出的DNN分区研究中没有一项同时考虑了多个分割点和多线程。 例如 B. 贡献 本文提出了一种分布式推理框架，用于最大化流数据上实时DNN计算的推理吞吐量，该框架具有多个分割点和多线程分区。本文的贡献如下： 一个用于计算和传输延迟的分布式DNN模型，通过该模型可以估计给定分区方案的预期推理吞吐量。 DNN分区优化问题的表述，该问题的分支定界求解器的实现，以及对其复杂性的评估。 模拟以探索在变化的云和DNN特性下可能的性能改进。 识别网络和DNN特性中存在最优分区和计算解决方案成本的确定性区域， ，DNN分区有益的条件。 即 实验结果说明了模拟中定义的区域，以及同质和异质环境中预测的准确性和最终的推理吞吐量加速。 为避免混淆，本文的其余部分将把分区深度神经网络称为 ，并将 一词用于表示底层物理通信网络。 DNN 网络 C. 论文大纲 本文的其余部分组织如下。 介绍了深度学习的背景以及本研究中DNN的表示方法。 详细介绍了用于 的推理和传输延迟预测方法，第四节定义了优化问题以及用于做出分区决策的分支定界算法。 介绍了模拟结果，以量化分支定界算法的性能和复杂性，以及在同质网络中提高推理吞吐量的分区存在的条件。 介绍了实验结果，证实了 的模拟，并在异质实验设置中显示了推理吞吐量的提高。最后， 讨论了结果，并扩展了该方法的更广泛适用性。 第二节 第三节 第四节 第五节 第六节 第五节 第七节 第二节。 背景：深度学习 在机器学习领域，深度学习（DL）指的是依赖于使用DNN的方法， ，包含多个隐藏层的多层感知机（或相关的机器学习方法）。深度学习架构最早的参考之一发表于1967年 ，但直到2010年代，DL才首次在语音识别、然后是图像物体检测领域获得关注，因为它能够捕获高维数据中的复杂关系。据估计，深度学习将占2022年AI应用的绝大部分，超过75%的组织使用DNN来处理那些可以用经典方法解决的应用。 DL方法被定义为“ ” 。这些代数电路通常组织成层，形成计算的步骤。术语 指由多层组成的算法。 即 [](javascript:void()) 4 一种机器学习技术，其中假设采取具有可调连接强度的复杂代数电路的形式 [](javascript:void()) 深度 有两种主要的DNN结构：前馈神经网络和循环神经网络。这两种类型的DNN都可以表示为计算图，主要区别在于前馈网络可以表示为有向无环图（DAG），而循环神经网络可能包含循环。循环神经网络用于处理序列数据，其中每个数据点可能与序列中的先前数据点相关联，而前馈神经网络不考虑数据序列中点之间的交互。 本文的其余部分将考虑前馈DNN的情况。 5 第三节。 分布式推理建模 本节介绍了一个模型来表示DNN和网络特性，以便预测给定分区解决方案的计算延迟、传输延迟和最终推理吞吐量。 A. DNN和网络表示 具有N层的N层前馈DNN被建模为一个DAG GA=(L,E)，其中L=(L1,...,LL)是DNN的层。边(Li,Lj)∈E是层Li和Lj之间的连接。每个层Li都有一个相关的计算消耗ci，以进行层前向传播所需的浮点运算次数来衡量。边(Li,Lj)被赋予一个权重si,j，对应于在层Li和Lj之间传输的数据量（以字节为单位）。 物理网络被建模为一个全连接图G=(N,V)，其中N=(N1,...,NN)是计算节点集，V是节点之间的链路集。假设计算节点N1,...,NN分别具有处理速率η1,...,ηN，以每秒浮点运算次数为单位。最后，两个相邻节点Na和Nb之间的链路吞吐量表示为θa,b，以每秒字节为单位。每个节点Ni都通过具有无限吞吐量的链路连接到自身，以表示回送链路，并且链路假定为对称的， ，θa,b=θb,a。 即 分区被定义为映射P:L→N， ，分区将节点编号分配给DNN中的每个层。分区可以表示为一个维度为(N×L)的矩阵P，其中N是网络中的节点数，L是DNN层数，Pa,i=1表示层Li放置在节点Na上，否则为0。以 为例，L=7层，N=2个计算节点，显示的分区将层{L1,L2,L3,L6,L7}放在节点N1上，将层{L4,L5}放在节点N2上，表示为： 即 图2 给定一个分区， 被定义为在同一节点上顺序运行的两个分割点之间的连续层组。在上例中，节点N1将运行两个线程，第一个线程包含{L1,L2,L3}层，第二个线程包含{L6,L7}层。 线程 在定义了这些表示法之后，本节的其余部分将推导出给定分区实现的推理吞吐量的封闭表达式，作为推理（ ）和传输（ ）延迟的函数。 第三节-B 第三节-C B. 推理延迟预测 给定一个分区，本节将关注单个节点上的推理延迟预测。层Li的计算引起的延迟，其消耗为ci，要在具有处理速率ηa的节点Na上计算，表示为Tci(Na)=ci/ηa。给定在一组层L′⊂L上，在具有处理速率ηa的节点Na上运行的所有线程，推理延迟可以表示为： 该表达式是基于处理DNN所需的浮点运算次数（FLOPs）， ，模型中的乘加运算次数的推理延迟估计的一阶近似。 即 边缘设备上的推理延迟估计因运行时优化而变得复杂。nn-Meter 等现有解决方案基于FLOPs预测推理延迟。其他解决方案依赖于具有预计算推理时间的查找表来进行延迟推理。例如，BRP-NAS 使用预训练的图卷积网络来预测推理延迟，同时考虑运行时模型优化。 [](javascript:void()) [](javascript:void()) 在 中，还假设处理器使用其全部容量，这意味着多核处理器被建模为单核处理器，其处理速率等于其核心处理速率之和。还假设计算资源在线程之间平均分配， ，处理器将相同比例的时间分配给每个线程。 公式1 即 在所有节点中，延迟最高的线程决定了分布式DNN的推理吞吐量。不考虑传输延迟，这意味着一旦这个限制线程完成数据帧的计算，它就会直接处理下一个数据帧。其他线程在处理下一个数据帧之前会有空闲时间，因为它们的推理延迟低于最大延迟，如 所示。 图1 给定一个分区矩阵P，推理延迟可以表示为单个向量Tc，大小为N，其中a分量是节点Na上最高的线程推理延迟， ，Tca=Tc(Na)： 即 其中H是反向节点处理速率的对角矩阵diag(η−11,...,η−1N)，c是单个层消耗的列向量(c1,...,cL)。 C. 传输延迟预测 传输延迟可以按如下方式预测：在节点Na和Nb之间的链路（Na,Nb）上，发送数据量si,j在层Li和Lj之间，传输时间为si,j/θa,b，其中θa,b是测量的吞吐量。链路（Na,Nb）上的数据传输si,j∈E′⊂E的时间为： 与推理延迟预测类似，这表明链路在Na到Nb的数据传输之间平均分配。传输延迟预测依赖于链路吞吐量的估计，更具体地说，是 ， ，每秒传输的有用数据量。 有效吞吐量 即 与推理延迟估计类似，这是一阶近似，能有效地提供良好的预测结果，如 c所示，相关系数为R2=0.9998。此方法的缺点是需要饱和链路才能获得吞吐量估计。 图3 给定一个分区矩阵P，传输延迟矩阵Tt可以定义为一个L×L的方阵，其中Tta,b=Tt(Na,Nb)： 其中°是逐项乘积，或Hadamard积，Θ是反向吞吐量矩阵， ，一个N×N的方阵，其中Θa,b=θ−1a,b，S是传输大小矩阵， ，一个L×L的方阵，其中Si,j=si,j如果Li发送数据到Lj，否则为0。 即 即 第四节。 DNN分区 本研究中DNN分区的目标是最大化推理吞吐量，用C表示，它对应于所有不同计算和传输延迟之间的最大延迟的倒数。给定一个分区P，推理吞吐量定义为： 最大化推理吞吐量相当于在Tc和Tt的所有项之间寻找联合的min-max。这可以定义为一个离散优化问题： 其中Ji,j是i×j的全一矩阵，条件 和 要求每个层都放置在一个且仅一个节点上。 (6) (7) 这个问题是一个混合整数非线性规划（MINLP）问题。分区矩阵可以看作是大小为(1×L)且值在[[1,N]]中的向量的单热编码版本。MINLP问题是NP难的，这意味着找到最优DNN分区的复杂度为O(NL)，因为L个层中的每个层都可以放置在N个节点中的一个上。有几种启发式方法可以以比暴力算法更快的时间获得该问题的最优或次优解， ，遗传算法（GA） 、粒子群优化（PSO） 或分支定界（B&B） 。所选择的方法是适应性B&B实现，在 中进行了介绍。 例如 [](javascript:void()) [](javascript:void()) [](javascript:void()) 第四节-A A. 分支定界算法 本节介绍分支定界（B&B）算法在 定义的DNN分区优化问题中的应用。 第四节 在B&B算法中，解空间由一棵树表示。该过程通过评估根节点的分数来消除树的整个分支。这意味着存在一个树形结构，该结构在树中节点的分数与其所有叶节点分数的界限之间建立关系。 解空间的这种树形表示有利于在本研究中使用B&B算法。假设ps是一个大小为s的部分列表，节点ps的子节点是所有以ps开头的列表， ，所有层的前s层按照ps放置的分区。对应于ps填充最后一个ps值的ps下方的叶节点标记为ps~。例如，如果L=5且p2=(2,1)，则p2~=(2,1,1,1,1)。给定Ttmax=maxTt(ps~)对于分区ps~的最大传输延迟，ps下的所有叶节点p将具有比ps~更高的最大传输延迟， ，∀p,maxTt(p)≥Ttmax。这是因为，给定一个部分分区，其他层中的任何位移只会增加节点之间的数据传输。 即 即 在寻找最大化推理吞吐量C(p,GA,GN)的最优分区p的过程中，并给定当前可达到的最佳吞吐量best_throughput，B&B优化通过评估部分分区中的传输时间来消除树的整个分支。这个过程允许B&B优化比暴力算法更快地消除大量情况。例如，如果节点之间的吞吐量与计算能力相比很低， ，节点通过低吞吐量无线连接，则最优解决方案通常是将所有计算保留在一个节点上。B&B算法的优点是，在这种简单的情况下，它会在树的第一阶段消除所有部分分区，从而在N次操作后终止。相反，在链接吞吐量较高的情况下，B&B的复杂性可能更高，因为它无法消除大的分支。 例如 B. 分支定界复杂度 在这种方法中，忽略了实际实现中总分区数造成的开销。这种额外的延迟与分区的总数相关。每个分区都会导致从网络接口控制器（NIC）到内存的数据传输产生额外的延迟，这与PCIe吞吐量、内存吞吐量和传输数据的大小有关。假设数据传输吞吐量受内存吞吐量限制，则该延迟的简单评估将 中的计算延迟更改为： 公式1 在此表达式中，ν是内存吞吐量， ，读/写内存的速度，而(i,j)∈C是所有层Li和Lj，使得边(Li,Lj)是一个分割点，并伴随数据传输si,j。 即 1) 提前停止 随着分区数量的增加，性能和推理延迟预测的准确性都会下降。因此，并且为了在可用网络吞吐量高的情况下增加复杂性，添加了一个提前停止机制来限制最终分区中的分割点数量， ，B&B只会探索最多S个分割点的部分分区，进一步限制了所探索树的大小。带有有限分割点的完整B&B算法如 所示。 即 算法1 算法1 分支定界算法 限制分割点的数量降低了该MINLP问题的复杂度。对于N个节点和L个DNN层，算法考虑的分区总数现在降低到： 而不是对于暴力算法的O(NL)。 第五节。 模拟 本节介绍模拟，以评估算法参数对B&B算法性能和复杂度的影响。B&B的最坏情况复杂度在 中描述，当时部分分区中计算的所有传输时间都超过了已实现的最佳时间，但有效的B&B复杂度取决于DNN和网络特性。以下变量被探索： 公式9 节点数N与最大允许分割点数S之间的关系，它决定了达到最优解所需的B&B迭代次数。 链路吞吐量θ与节点处理速率η之间的关系，它决定了是否存在提高推理吞吐量的分区。 这些交互通过以下指标进行评估，这些指标可用于将提出的方法与现有文献进行比较： 实现的推理吞吐量，以每秒推理次数为单位。 达到解决方案所需的B&B迭代次数， ，解决方案树中已探索的分区数。使用此指标而不是计算时间是为了抽象所使用的设备性能。作为参考，在配有Intel Core i7处理器的台式电脑上运行B&B时，运行102次迭代需要17毫秒，运行104次迭代需要1.269秒，运行106次迭代需要5分钟。 即 为了隔离每个变量的贡献，模拟在一个同质网络场景下运行， ，所有节点具有相同的处理速率，所有链路具有相同的吞吐量。 即 A. 节点数和分割点数 设置包括一个同质网络，其处理速率设置为5GHz（标准边缘设备 ，Raspberry Pi 4__8__的有效处理速率），链路吞吐量设置为10MBps（802.11的有效吞吐量）。网络中的计算节点数N在1到6之间变化，最大分割点数S从0（将所有计算保留在一个节点上）到5（总共6个分区，分布在网络上）之间变化。 例如 a也说明了，当最大分割点数超过S>3时，最佳可实现吞吐量不再提高。在给定的处理速率和链路吞吐量下，增加最大分割点数不会影响实现的推理吞吐量。这一观察的主要优点是它为限制B&B的最大分割点值S提供了一个论据。由于分数保持不变，而复杂性显著增加，因此在这种条件下选择S=3既能保持合理的复杂性又能达到最优解。 图5 这种限制可以解释如下：对于给定的DNN和网络特性，在N=3个节点上找到的最优放置，以及最大分割点数S=3，在网络中添加新节点，或为另一个分割点提供可能性，都不会导致更好的分区。在同质网络中，这意味着任何将层移动到另一个节点的行为都将导致传输延迟高于当前分区中最大计算延迟。这导致了S值的上限，之后最优分区是最佳可实现的 ज्यात。 其中Tcmono是将所有计算保留在一个节点上的计算延迟，Ttdisp是层位移引起的传输延迟，η和θ是同质网络中的节点处理速率和链路吞吐量值，∑Li∈Lci是DNN中所有层消耗的总和，smin是最小的层间数据传输大小。这个表达式可以用来定义S的上限，并限制B&B的计算时间。 在本文的其余部分，实验和模拟将以最大分割点数S=3运行，以限制算法的复杂性，并获得接近最优的分区，这对应于典型的边缘场景。 B. 处理速率和链路吞吐量 该设置包括YOLOv2 的标准实现，部署在具有N=4个计算节点的网络上。B&B的运行最大分割点数为S=3，节点处理速率在0.1GHz到100GHz之间，链路吞吐量在1MBps到10GBps之间。处理速率和链路吞吐量值的范围选择涵盖了广泛的边缘场景： [](javascript:void()) 0.1GHz到100GHz之间的处理速率涵盖了片上系统（SoC）的CPU， ，高通骁龙系列__9__，其处理速率在500MHz到1GHz之间，以及专门的AI嵌入式系统， ，NVIDIA Jetson TX2模块， ，其在 实验中测得的处理速率为30.7 GHz。 例如 例如 10 第六节 1MBps到10GBps之间的链路吞吐量对应于802.11g连接（几MBps）和千兆以太网链路的链路吞吐量。