Abstract (key idea)

现在的Mobile Devices配备了很多的CPU+GPU+DSP的设备。但是现在的大多数NN model因为自己的顺序结构导致无法充分地利用这些异构处理器。本文提出了一种新的模型适应（model adaption）策略NN-Stretch，它针对处理器体系结构来对模型进行分支。

NN-Stretch的关键思想是将模型结构从长而窄的模型水平拉伸为短而宽的多分支模型。我们将模型分支问题形式化为一个优化问题。
NN-Stretch通过考虑硬延迟约束（通过变化分支的汇聚点和每个分支的缩放方式以适应异构处理器）以及软准确性约束（通过保持模型骨架和每个分支的表达容量）来缩小设计空间。根据这些约束，NN-Stretch可以高效生成准确而高效的多分支模型。

为了方便简单部署，本文还设计了一种基于子图的空间调度器，用于现有推理框架的并行执行多分支模型。我们的实验结果非常令人期待，与单个CPU/GPU/DSP执行相比，速度提升了高达3.85倍，准确性提升了高达0.8%。

1 Introduction

本质上来说，NN Model的并行执行依赖于模型结构的并行性。例如现有的工作[21,42]是通过将运算符（OP）分割到不同设备进行执行，它是利用了OP的运算并行性。但是这样的更适合那些计算密集型的OP。否则，处理器之间的通信成本（同步、数据映射，数据转换）可能会覆盖掉并行执行的收益。然而，在移动端的NN模型中，计算密集型的运算符很少见。例如，作者的测量结果显示，CPU和GPU之间的通信成本约为1毫秒，但MobileNetV1 [17]的每个运算符的延迟通常<1毫秒。
另一方面，跨运算符并行性适用于所有运算符。它在不同处理器上并发执行没有数据依赖关系的运算符，而不是分割单个运算符。然而，这里的挑战是广泛使用的NN模型，如ResNet [12]和EfficientNet [32]都由顺序运算符组成，即单个分支，因此无法应用跨运算符的并行性。此外，即使是多分支模型，也很难从异构处理器的并发执行中受益，因为不同分支上的计算负载不平衡，例如Inception系列[34]。
与此同时，许多模型适应技术[8, 14, 22, 47]，如模型剪枝，已被提出来优化模型结构以便于在移动端部署，但它们通常专注于单个处理器上的推理加速。迄今为止，这些技术中没有考虑到为异构计算适应模型。此外，这些方法通常以牺牲模型准确性为代价来降低延迟。

根据这些现象，作者提出了一个重要的研究问题：我们能否自动将给定的单分支模型转换为平衡的多分支结构，以便在异构处理器上进行高效的并行执行？与为降低延迟而牺牲模型容量的剪枝或蒸馏相比，这种模型分支操作可以在不损失模型容量（即准确性）的情况下加速推理。

为了回答上述问题，本文提出了一种名为NN-Stretch的新型模型适应策略和支持系统，用于在移动/边缘设备上进行模型部署。据我们所知，这是第一种实现自动模型分支并行执行的模型适应技术，即分支并行性（如图1所示）。为了更好地实现模型部署，我们认为所提出的模型适应技术应具备以下特点：

在不损失准确性的情况下降低延迟；
不需要额外的模型设计工作；
与其他模型适应技术（如修剪）相比没有更多开销。

NN-Stretch的关键思想是通过水平拉伸将通常较长而窄的单分支模型转化为具有多个分支的短而宽的模型，如图1所示。每个分支提取不同组特征。这种转换的有效性得到了之前研究中讨论过的结论支持，即在一定程度上增加或减少模型深度或宽度可以成功保持其准确性[1, 6, 10, 25, 29]。

要实现这个系统主要要解决两个问题：

什么时候去合并这些分支，这里叫做meeting point，合并每个分支提取的特征。
如何去缩放每个分支。

我们将这个问题转化为一个优化问题。与其他模型设计空间类似，设计选项的数量太大以至于无法高效搜索。为了减少设计选项的数量，我们引入了“硬”延迟约束（与上述两个因素直接相关）和“软”准确性约束（与这两个因素的相关性更加间接和不可预测）。只有满足约束条件的设计选项需要被考虑。

具体而言，我们采用以下约束条件。

对于延迟方面，我们有：
1. 成本摊销式汇合点识别，通过控制分支的深度来摊销处理器通信成本；
2. 异构感知的深度-宽度缩放，在每个分支上缩小深度（层数）或宽度（过滤器数量），以降低总计算成本并提高异构处理器利用率。
对于准确性方面，我们有：
1. 保持结构的汇合点识别，在模型阶段中采用特征图大小更新作为汇合点来保持模型骨架；
2. 保证容量的深度-宽度缩放，通过设置深度和宽度的下限来保持每个分支的表达能力。

这些约束条件的组合迅速减少了设计选项，从而可以快速生成多分支模型。

执行这种多分支模型的主要挑战源于当前推理框架在一个处理器上按顺序运行模型。为了解决这个挑战，我们设计了一个基于子图的空间调度器来补充现有的推理框架。它使用处理器级别子图（即一系列操作符，只有第一个操作符依赖其他处理器）作为调度单元进行处理器分配。因此，每个模型分支都是一个被安排在特定处理器上运行的子图。调度器设计还解决了不同处理器通信机制方面的正确性和效率问题，例如将不同处理器同步或异步地运行到主机CPU上。

在这项工作中，我们对流行的CNN模型，包括EfficientNet [32]、RegNet [31]和ResNet [12]，使用ImageNet [9]数据集进行了NN-Stretch的评估。比较基准是TFLite [24]推理框架和CoDL [19]，这是目前在CPU+GPU处理器上的最先进的并行推理系统。我们在三款不同手机上进行了设备内评估，分别使用了三种不同的处理器，包括CPU、GPU和DSP。结果显示，与仅使用CPU、仅使用GPU和仅使用DSP相比，在CPU+GPU+DSP上，NN-Stretch可以分别实现高达2.3倍、3.85倍和2倍的加速。模型准确性得到保持。

事实上，NN-Stretch是第一个能够灵活组合可用处理器进行推理的方法，例如GPU+DSP和CPU+GPU+DSP。它基于实际设备使用情况提供更多调度选项。NN-Stretch与其他模型部署优化方法（如量化、模型修剪和操作符内核优化）是正交的。NN-Stretch已经开源[1]。

Main contributions

我们提出了一种新的模型适应策略，可以将单分支模型转化为多分支模型，以享受分支并行性的好处；
我们设计了汇合点识别和深度-宽度缩放技术，以实现有效的模型分支，并考虑了模型和硬件特性；
我们在推理框架中设计了基于子图的调度器，以支持异构处理器上的并行推理。
我们实现了NN-Stretch系统，展示了延迟降低和准确性提升的效果。

在本节中，我们描述了移动SoC的特性、典型的NN模型架构以及两者之间的不匹配之处。具体而言，移动SoC独特之处在于它们的CPU核心和GPU具有可比较的性能，并且可以同时执行模型的不同分支。然而，流行的NN模型是顺序连接的，无法直接利用这个特性（第2.1节）。早期大部分模型适应工作都假设在单个处理器上执行，而不是在异构处理器上执行（第2.2节）。此外，我们还解释了现有的多分支NN设计不能用于适应我们需求的通用自动模型分支化（第2.3节）。

2.1 Mismatch between Heterogeneous Architecture and Model Structure

并发异构计算架构。与服务器不同，移动设备采用了独特的异构计算架构。以广泛使用的移动CPU和GPU为例：

性能可比较。与服务器GPU相比，其运行速度比CPU快几个数量级，但由于芯片和功耗限制，移动CPU和GPU在深度学习模型推理方面具有相似的性能，如图3所示。
统一内存。与通常为CPU和GPU分别配备独立内存单元的服务器不同，移动CPU和GPU共享统一内存[20]。因此，可以避免昂贵的数据复制成本。由于这两个特性，存在采用异构并发计算来加速模型推理的机会。

顺序模型结构。当前广泛使用的NN是由按顺序依赖于彼此的操作符组成的。设计NN的一般做法是首先设计一个层（可以是单个操作符或一个构建块），然后在每个阶段中重复堆叠该层。一个阶段是具有相同特征图大小的层序列。图2显示了代表性NN模型的构建块。表1以RegNetX-4GF为例列出了各个阶段，其中主要由四个阶段组成，每个阶段中包含2、5、14和2个块。在一个阶段内，第一个构建块应用卷积（简称Conv）stride=2，而后续的块应用stride=1。阶段内的其他超参数保持不变，例如过滤器数量。

通信密集型的操作符内并行性。为了同时执行顺序NN，三篇研究论文?layer [21]、Optic [42]和CoDL [19]探索利用NN的操作符内并行性。它们将每个操作符（沿输出通道或高度/宽度维度）分区到不同的处理器上运行，如图3a所示。在执行一个操作符时，处理器之间进行通信以共享输出结果给下一个操作符使用。尽管CPU/GPU/DSP处理器在移动SoC上共享统一内存，但通信通常会引入以下开销：

数据转换，将数据转换为每个处理器使用的类型；
数据映射，将数据映射到每个处理器的地址空间；
处理器同步，在完成某个动作后通知其他处理器。

处理器之间的通信开销是显著的，特别是对于轻量级的移动端NN。图3比较了MobileNetV1每个操作符的通信延迟和单处理器执行时间。通信延迟相对稳定，约为1毫秒，超过了大多数操作符在仅CPU或GPU上的推理延迟。

不支持处理器并发。尽管研究工作?layer和Optic已经提出了并发处理器执行的方法，在实际生产场景中，当前工业级NN推理框架不支持多处理器并发执行，原因是高昂的通信成本，无论是移动端框架如TFLite [24]、Mace [27]和ncnn [38]还是服务器端框架如ONNX runtime [28]和TensorFlow [11]。相反，它们按顺序在每个处理器上运行操作符，如图4所示。本文提出了一种基于子图修改的方法来使可用移动端推理框架能够实现多处理器并发执行。

2.3 Lack of Model Adaption Suitable for Multi-Processor Execution

由数据科学家设计的NN模型通常在实际使用中存在差距，并需要对不同设备进行模型适应以进行部署。这种差距可能包括：

运行时间不理想，
模型大小和内存占用过大，
硬件不适合的操作符类型。

在实际应用中，模型的运行时间可能超出了可接受的范围，需要通过优化和调整来减少推理时间。此外，移动设备通常具有有限的存储容量和内存资源，因此需要减小模型大小和内存占用，以便能够在设备上高效地运行。最后，在硬件层面上，某些操作符类型可能无法充分利用特定设备的计算能力或者与设备架构不匹配，因此需要对模型进行调整以适应目标硬件。

为了解决这些问题，可以采取一系列策略和技术来进行模型适应。例如，在移动端可以使用轻量级网络结构、剪枝和量化等方法来减小模型大小并提高推理效率。还可以针对特定硬件平台进行优化，并使用硬件加速库或指令集来提高性能。

总之，在将NN模型部署到实际设备上之前，需要进行模型适应以解决运行时间、模型大小和操作符类型等方面的差距，以确保在不同设备上获得良好的性能和效果。

因此，提出了不同的模型适应技术，可以分为三个主要方向：

模型缩放[12, 17, 37]。它通过扩展给定模型的深度（层数）、宽度（过滤器数量，即输出通道数）或分辨率来生成不同大小和FLOPs（浮点操作数）的模型，以适应不同设备。例如，EfficientNets在所有维度上进行统一缩放，模型大小范围从7.8 MB到66 MB，准确率从79%到84%不等。
模型压缩。与为不同设备和任务调整模型深度或宽度相比，模型压缩主要关注去除权重冗余以将模型压缩为更小的尺寸。这包括一系列技术，如模型修剪[13, 14, 22, 46]和量化[4, 43, 45]。
针对处理器设计的NN [8, 36, 47, 50]。它使用硬件高效的操作符或超参数来设计NN。例如，EfficientNetEdgeTPU [32]和MobileNetEdgeTPU [2]旨在通过增加专家选择的构建块来扩展设计空间，并在Edge TPU上高效运行。

上述技术将模型调整为减少内存和计算资源使用量，或更好地利用单个处理器的特性，极大地促进了NN模型在移动设备上的部署。然而，它们都没有考虑到移动设备的独特特点，即CPU-GPU异构计算。

还有一些技术利用现有的独立子图。DUET [51]针对子图分区编译调度问题。DUET依赖于模型中现有的并行分支，然后为多处理器编译内核。但DUET无法为模型生成新的分支。BlastNet [23]依赖于多DNN并发执行。BlastNet将每个模型划分为块，并将这些块安排在不同处理器上进行调度。这两种技术都严重依赖于现有的独立子图进行并发执行，并不适用于顺序DNN模型。

为了解决这个挑战，本文提出了一种新的模型适应策略，通过分支化一个模型来利用异构处理器。

2.3 Call for General and Automatic Model Branching

存在一些手工制作的多分支NN，例如Inception系列[18, 33–35]和通过神经架构搜索（NAS）获得的模型，如NASNet [3]和Cai等人的研究[52]。Inception（如图5所示）在不同分支中使用不同大小的卷积核来提取全局和局部信息，以实现高准确性和低延迟。尽管手工制作的多分支NN经过精心设计，并且每个阶段都定制了块，但目前还不清楚如何将Inception架构适应新的数据集/任务[44]。因此，该技术无法推广到通用的自动模型分支化。基于NAS的方法从由基本多分支块组成的大空间中搜索最优NN。尽管它可以节省人工劳动力，但在计算方面代价太高，例如NASNet [3]需要2000个GPU小时才能找到合适的多分支NN，这使得它在部署上变得不切实际。

为了解决这个挑战，我们的论文提出了一种通用、实用且自动化的分支技术。

3 NN-STRETCH SYSTEM OVERVIEW

图6显示了NN-Stretch系统的概述。它涵盖了模型适应/设计和模型推断两个阶段。在设计阶段，NN-Stretch接收顺序模型、训练函数及其数据集以及目标部署平台（设备类型和推断框架）作为输入。NN-Stretch输出分支化的模型。为了方便并行推断，模型格式增加了每个操作符的两个新属性:

是否是meeting point
推荐运行处理器。

在推断阶段，我们设计了基于子图的空间调度器来支持多处理器上的并行推断。它将每个分支划分为一个子图，作为在处理器上运行的基本调度单元。选择处理器时考虑到模型设计建议、处理器可用性以及延迟或能量优先级。

模型设计的第一步是识别meeting point，同时考虑延迟通信成本和保持模型结构以确保准确性。通过这些汇合点对模型进行分割。然后，在分支化过程中应用重复缩小比例方法，考虑到延迟方面的处理器异构性和准确性方面的容量保证。该过程首先将一个片段复制成多个分支，导致膨胀的模型大小，然后缩小每个分支的宽度（即过滤器数量）或深度（即层数），将模型大小缩小回原始大小。生成多分支模型后，类似于其他模型适应技术，通过给定的训练函数和数据集对新模型进行训练。

meeting point和缩放比例的选择是基于减少延迟的指导。延迟可以在设备上测量，也可以进行预测。我们扩展了最先进的nn-Meter [49]延迟预测器，以在目标设备上预测延迟。

4 MODEL BRANCHING

为了将一个深而窄的网络转换为具有多个分支的短而宽的网络，关键问题是在哪里进行分支以及每个分支的结构是什么样的。我们首先探索了不同的NN设计方法，例如面向处理器定制的方法[8, 36, 47, 50]，通过这些方法我们尝试在不同分支中用搜索到的处理器友好型层替换一些层。然而，我们发现这些方法很容易违背NN-Stretch的原则，导致准确性损失、大量模型适应开销或需要模型设计者参与。因此，它们作为一种通用且自动化的部署策略并不实际。

因此，我们得出了NN-Stretch模型分支化的重要指导原则：主要保持给定模型的结构和容量（权重大小和计算总量即FLOPs）。为此，NN-Stretch将模型分支化设计为一个复制和缩放过程。具体来说，NN-Stretch采用以下三个步骤：

识别汇合点以将顺序（深而窄）网络划分为多个片段；
复制每个片段形成多分支网络结构；
缩小每个分支的深度和宽度以减少推断成本。

本节将介绍我们如何制定和解决模型分支化问题。

4.1 Large Design Space for Model Branching

问题建模。NN-Stretch引入了一系列需要为模型分支化指定的超参数。具体而言，表2列出了所有超参数及其类型、形状和潜在值：汇合点数量(\(N_{meet}\))、分支数量(\(N_{branch}\))、汇合点位置(\(L_{meet}\))、深度缩放比例(\(R_{depth}\)) 和宽度缩放比例 (\(R_{width}\))。

在指定了所有这些超参数之后，NN-Stretch将给定的模型（表示为图\(G_{seq}\)）转换为多分支模型（表示为图\(G_{branch}\)），表示为：

\[G_{branch} = F(G_{seq},N_{meet},N_{branch},L_{meet},R_{depth},R_{width}) \quad (1) \]

其中\(F\)表示图形转换。值得注意的是，不同的宽度缩放因子可能导致不同的输出通道数。为了解决这个差异问题并恢复通道数，图形转换\(F\)在每个分支后插入一个1×1卷积操作符，并连接所有分支（参见本节末尾显示的示例图8）。

在NN-Stretch中，我们的目标是为给定的模型\(G_{seq}\)找到一组合适的超参数\((N_{meet},N_{branch},L_{meet},R_{depth},R_{width})\)，生成一个具有最小延迟的多分支模型（\(G_{branch}\)），同时确保多分支模型的准确性大于或等于预定义的目标准确性（例如，\(G_{seq}\)的准确性，或者有一个可接受的松弛度）。正如[1, 6, 10, 25, 29]所讨论的那样，在深度和宽度上对模型进行缩放具有类似的表达能力，并且可以在一定范围内成功保持其准确性。

总体上，可以将模型分支化问题建模为以下优化问题：

\[\begin{align*} \min_{N_{meet},N_{branch},L_{meet},R_{depth},R_{width}}{Latnecy(G_{branch})} & \quad (2) \\ s.t. \quad Accuracy(G_{branch}) \ge Accuracy(G_{seq}) & \quad (3) \end{align*} \]

然而，由于以下两个原因，快速找到满足方程2和3的多分支转换的超参数集合是非常具有挑战性的。首先，设计空间非常庞大。对于一个具有30-50层的流行CNN模型来说，模型分支化的超参数设计选择很容易超过10^{50个。其次，即使可以快速准确地预测或在实际设备上测试转换后的多分支模型的推断延迟，其准确性只能在训练阶段之后进行验证，这需要大量GPU资源和训练时间，更不用说约10}50个设计选择了。

直接搜索所有潜在超参数选择的组合是不可行的。在NN-Stretch中，我们提出了一种系统化方法来大幅缩小搜索空间，包括：

对超参数对推断效率影响进行分析；
观察超参数对模型准确性的影响。

4.2 Narrowing Down Design Space from Inference Latency Perspectives

通常，汇合点和缩放比例的超参数与转换后的多分支模型的推断延迟具有直接和统计相关性，这也可以在实际设备上进行准确快速的预测或测试。因此，我们可以明确地建立延迟与超参数之间的关系，并剪除具有不满意延迟的解决方案。

成本分摊的汇合点识别。在移动SoC上运行多分支模型时，每个汇合点自然成为处理器之间的通信点。更多的汇合点会导致更高的通信成本，甚至可能抵消由分支并行性带来的延迟减少。如表3所示，汇合点数量的增加导致整体延迟显著增加。

为了避免由高通信成本引起的长延迟解决方案，我们对汇合点数量和位置添加了约束条件，如公式4所示。其原理是通过段深度(一系列的层)来分摊通信成本。

\[\begin{align*} Latency(communication) \le \alpha \cdot \sum_{j=L[i]}^{L[i+1]-1}{Latency(layer_j)} , \quad \forall i \in [0,N_{meet}-1) & \quad (4) \end{align*} \]

\(Latency(communication)\)是处理器之间的通信延迟; \(Latency(layer_j)\)是某一层的计算延迟。\(\alpha\)是用户定义的分摊比例。（例如，0.1的意思是通信成本低于每个段的延迟时间的10%。）

异构感知的深度-宽度缩放。在NN-Stretch中，多个分支在异构处理器上运行。因此，分支的数量（\(N_{branch}\)）由移动SoC上的处理器数量\(N_{processor}\)决定。

与成本分摊的汇合点识别类似，我们对深度/宽度缩放比例设置了下限，以避免增加整体延迟的滞后分支。

\[\begin{align*} Latency_{proc_{i}}(branch_{i}) \le \beta \cdot Latency_{proc_{i}}(original_{segment}), \quad \forall i \in [1,N_{branch}] & \quad (5) \end{align*} \]

其中，\(\beta\)表示一个调整系数（通常为1.1或1.2），用于限制每个分支的浮点运算量（FLOPs），而\(proc_i\)则表示执行原始段的最快处理器。

由于移动SoC本身具有异构性，不同的处理器（例如CPU、GPU、DSP）具有不同的架构，并且倾向于使用不同的缩放选项来完全匹配其架构特性。例如，深度缩放导致分支形状相对较宽，适用于高度并行化的GPU和DSP。如图7所示，当运算符变得更宽时，在GPU上实现的性能（GFLOPs/秒）大幅增加。另一方面，宽度缩放导致分支相对较深，更适合CPU，因为CPU擅长串行小型运算符。因此，根据不同的硬件特性，可以应用相应的缩放策略约束来进一步缩小搜索空间。

最后但并非最不重要的是，在移动SoC中的处理器具有类似但略有不同的性能功耗。充分利用所有处理器的最佳方法是将每个分支的FLOPs与执行该分支的处理器性能对齐，如公式6所示。（再次注意FLOPs表示浮点运算次数，而FLOPS表示吞吐量即每秒浮点运算次数）。

\[\begin{align*} FLOPs(branch_1):FLOPs(branch_2): \dots :FLOPs(branch_n) \\ \approx FLOPS(proc_1):FLOPS(proc_2): \dots :FLOPS(proc_n) & \quad(6) \end{align*} \]

4.3 Narrowing Down Design Space from Model Accuracy Perspectives

与第4.2节中列出的明确定义和分析的与延迟相关的约束不同，准确性相关的约束是“软”约束，因为模型推断准确性存在不确定性和不可预测性。根据顺序模型本身的特点和初步实验观察，可以应用特定于模型的软约束来进一步缩小搜索空间。

保持结构的汇合点识别。在流行的CNN模型（例如ResNet、MobileNet、ShuffleNet）中，模型通常由多个阶段组成，每个阶段中的所有构建块共享相同的架构。为了尽可能保留专家设计的模型结构，我们首先将各个阶段之间的连接点作为汇合点，使每个阶段成为一个要分支的片段。

除了推断效率外，汇合点的数量还会影响模型准确性。直观地说，拥有更多的汇合点会导致更频繁的特征交换，从而很可能带来更好的准确性。而较少的汇合点则倾向于降低模型准确性，因为信息交换不足。在ResNet56上进行实验，并根据表3所示从1到9变化\(N_{meet}\)与我们直觉相符。因此，对于特定模型，我们对汇合点数量设置一个下限，在该下限以下将违反方程式3中对准确性要求。

保证容量的深度-宽度缩放。之前的研究[7, 26]指出，极浅或极窄的网络具有有限的表达能力，并且会削弱模型的准确性。受到这一发现的启发，我们还可以引入对深度缩放和宽度缩放比例的下限，以避免搜索无法保持原始准确性的极浅或极窄分支。我们在ResNet上进行的实验也表明，在表4中具有极低缩放比例（0.3）的分支模型表现不如那些在类似FLOPs数量下产生相似模型大小的缩放比例。通常情况下，可以通过针对不同模型进行初步实验来获得关于缩放比例下限的信息。

值得注意的是，约束条件不仅限于第4.2节中介绍的方程式4、5和6，以及第4.3节中介绍的软约束。可以针对各种神经网络模型提出和探索进一步缩小搜索空间的约束条件。在NN-Stretch中，通过这些约束条件，我们可以将流行的CNN模型的搜索空间有效地从\(10^{50}\)缩小到不到10或20。因此，我们能够使用网格搜索有效地找到合适的分支超参数。

例如，图8展示了EfficientNet在NN-Stretch中生成的多分支阶段。EfficientNet有7个阶段，我们以第5个阶段为例进行说明。该阶段有7个块和176个通道，即（深度、宽度）为（7, 176）。在这里，我们将\(\alpha\)设为0.1，\(\beta\)设为1.0，并将缩放比例下限设为0.5。在所有候选项中，一个深度为6、宽度为136的CPU分支和一个深度为4、宽度为160的DSP分支实现了最佳延迟降低效果。

5 SUB-GRAPH-BASED SPATIAL SCHEDULER

对于推断系统来说，模型是一个包含一组操作符的图形，操作符是处理器内的调度单元。为了有效支持多个处理器的并行执行并减少通信成本，NN-Stretch利用更粗粒度的子图作为处理器之间的调度单元。子图的定义是在一个处理器上运行的一系列操作符，其中只有第一个操作符依赖于其他处理器的输出。因此，每个模型分支都是一个子图，并被调度在一个处理器上运行（以图8为例）。

调度程序设计面临的挑战源于不同处理器之间的通信机制，这要求进行正确性和效率方面都需要仔细设计。
以GPU为例。由于它提供低级编程API（如OpenCL），可以编程以同步或异步方式与主机CPU运行。然而，DSP库只提供同步方式下的操作符级和图形级API，这会阻塞CPU线程直到完成。
类似地，在考虑处理器之间数据共享时，移动SoC上的处理器具有统一内存，并且不需要进行内存复制。然而，并没有硬件支持缓存一致性，在软件中必须保证一致性[5]。GPU具有显式API（即内存映射），确保所有缓存中更改过的数据被写回到内存，并准备好供其他处理器读取。另一方面，DSP没有明确提供这个功能，而是隐藏在高级API中。

处理器通信的线程池。因此，线程管理专门针对不同的通信机制进行设计。为了解决DSP上仅支持同步方式的问题，我们实现了一个线程池，并为与DSP通信分配一个单独的CPU线程。线程池只在初始化时创建一次，以避免为每个子图重复创建线程带来的开销。出乎意料地，我们观察到这个通信线程与大核心之间存在很大竞争。例如，在为DSP通信添加一个线程后，推断变得非常不稳定，并且速度可能慢2倍。因此，我们将通信线程绑定到小核心上，并将大核心留给操作符执行线程。

对于可以异步运行的处理器（如GPU），我们的调度程序不使用单独的通信线程以避免竞争。为了解决不同的数据共享机制，在GPU上显式调用内存映射API以实现缓存一致性。对于DSP，则使用C++ future同步方法等待DSP通信线程完成后访问数据以实现一致性。

调度过程。算法1展示了调度过程。

在推断初始化的模型解析阶段，NN-Stretch将图形划分为拓扑排序的子图。基于设计建议、处理器可用性以及延迟/能耗优先级，它可以为每个子图决定执行处理器。

在推断过程中，如果一个子图是汇合点（第3到6行），它会启动CPU子图执行，等待所有处理器完成，然后连接所有结果。如果子图目标是GPU，则调度程序不会启动单独的线程。它将必要的命令（第15到19行），包括内存映射、数据转换和操作符内核，入队到GPU队列，并返回。如果子图目标是DSP，则将其推送到线程池中的一个单独线程中。在此线程完成后，future对象将被设置，并且CPU可以读取与DSP共享的数据（第21行）。

6 DISCUSSION

模型训练成本的降低。NN-Stretch的异构感知模型设计在针对目标处理器进行定制时表现最佳。如果需要将模型部署到不同的移动设备上，可能会引入重新设计和重新训练的成本。可以利用神经架构搜索领域中的超网络训练方法[48]来解决这个问题。超网络包含一系列具有不同模型配置的子网络。通过权重共享技术，可以一次性训练超网络中的所有子网络。我们在第7.4节消融研究中使用了这种方法，因为我们需要比较由不同方法设计的许多不同模型。所有模型变体都一起进行训练。与从头开始训练一个模型相比，超网络训练需要3倍更多的GPU小时数。

此外，我们观察到对于相同的SoC系列（例如Qualcomm Snapdragon 855和888），处理器设计相对稳定，只是提升了处理器性能。因此，如果在新设备上模型表现如预期，则避免进行模型重新设计。

更多调度机会。NN-Stretch基于设备上其他应用程序对处理器实际使用情况，实现了不同处理器之间灵活组合进行推断。对于已经在单个处理器上实现实时性能的小型模型，NN-Stretch还提供了增加模型大小和准确性的空间，而延迟成本保持不变。我们还将在消融研究中展示NN-Stretch的准确性和延迟权衡结果。

适应动态工作负载。NN-Stretch的一个关键设计目标是通过为可用处理器组合生成并行模型结构来适应动态工作负载。例如，如果GPU正在繁忙地进行渲染，我们可以使用CPU+DSP进行推断。同样地，如果CPU繁忙，我们可以使用GPU+DSP。相比之下，许多DNN模型使用顺序结构，只能在一个处理器上运行。这限制了灵活性和根据Amdahl定律的加速上限。我们的模型结构确实对处理器具有亲和性以获得更好的性能。但这并不妨碍它在其他处理器上运行。我们将在第7.4节消融研究中展示NN-Stretch对动态工作负载的适应结果。

与当前移动软件堆栈的集成。我们的模型设计仅更新模型结构，并与推断系统解耦。在更新后的模型文件输入到推断系统后，可以应用任何模型优化或压缩技术。我们的调度程序集成到推断系统调度程序中，将操作符入队到可用处理器以进行并行执行。我们使用的推断系统包括Google的TFLite和小米的Mace，它们都是广泛使用的移动推断系统。

应用于其他任务和模型。NN-Stretch 的一个设计原则是通过保持总的FLOPs数量、基本模型结构和容量保证的分支缩放来维持模型准确性。我们在复杂的ImageNet数据集上评估了NN-Stretch作为一个示例。现实世界中有许多任务。我们期望NN-Stretch能够保持准确性。本文针对移动设备上广泛使用的卷积模型进行了研究。对于Transformer模型，也可以利用NN-Stretch，例如在CPU、GPU和DSP上并行化多个注意力头和FFN层。探索更多任务、数据集和Transformer模型可以成为未来有前景的工作。

7 EVALUATION

7.1 NN-Stretch Implementation

该模型设计是基于Facebook的pycls[31]实现的，pycls是一个使用PyTorch编写的图像分类代码库，最初用于RegNet模型。pycls使用基本的训练设置，没有任何训练或测试增强，并提供简单、强大和可重现的基准。我们将多分支模型构建器、TFLite模型生成器、延迟预测器和超网络训练器集成到pycls中。

并行推断是在TFLite 2.8.0 [24]中实现的。TFLite的主要更新如下：增强操作符解析在GetOpsToReplace中；子图分区在PartitionGraphIntoIndependentNodeSubsets中；将子图调度到不同处理器中，在Invoke中完成。子图由HexagonDelegateKernel对象（用于DSP）和TfLiteGpuDelegateV2对象（用于GPU）包装。

为了测量CPU和GPU之间的通信延迟，我们利用OpenCL Event对象[30]，它提供了GPU命令执行的时间信息，包括排队（主机将命令入队）、提交（主机将命令提交给设备）、运行（命令在设备上开始执行）和完成（命令在设备上执行完成）。我们计算从排队的clEnqueueMapBuffer命令到第一个GPU计算内核开始执行之间以及最后一个GPU计算内核完成执行并且clEnqueueUnmapObject完成之间的时间作为通信延迟。这样，通信延迟包括内核入队开销、数据转换和内存映射/解除映射。对于CPU和DSP，它们共享相同的物理地址空间，没有内存映射/解除映射的成本。Hexagon DSP不提供用于细粒度分析的API。我们通过将正常的仅DSP执行中hexagon_nn_execute_new的经过时间从DSP通信线程在线程池中总延迟中减去来获取通信延迟。

代码总行数（LOC）包括对pycls和Tensorflow进行了2860行修改，并且有1058行测试工具代码。

7.2 Experiment Setup

测试模型,在评估中选择了ResNet、RegNet和EfficientNet这三个神经网络模型。它们是广泛使用的模型，而且它们的模型大小适合移动部署。它们由不同的主干块组成，如残差瓶颈和MBConv，并且使用不同的主干操作符，如普通卷积、分组卷积和深度可分离卷积。我们还选择了每个模型的两个变体，以展示NN-Stretch在不同模型长度和宽度上的有效性，即ResNet-34/50、RegNetX-1.6GF/4GF和EfficientNet-Lite4/B5。表6中显示了这些模型的FLOPs和大小。

为了将RegNet部署到移动GPU上，我们遵循常见做法，用多个小卷积替换分组卷积，并将每个小卷积对应于一个分组。为了部署EfficientNet-B5，我们去除了SE操作符，并将CPU分支上的Swish操作符替换为ReLU6。

由于DSP仅支持INT8计算，所有模型都进行了INT8量化。CPU也具有硬件支持的INT8指令。移动GPU不支持INT8执行，因此这些模型在FP16下执行。

图像分类任务是基于大规模ImageNet数据集的流行图像分类应用。ImageNet包含128万张训练图像和5万张验证图像。推断时输入图像的尺寸为NHWC = <1, 224, 224, 3>。每个模型的训练代码和配置都来自pycls。训练配置如下：所有模型使用带有0.9动量的SGD优化器，半周期余弦学习率调度，并进行100个训练周期。ResNet和RegNet使用学习率为0.2，批大小为256，权重衰减为5e-5。EfficientNet使用参考学习率0.4，批大小256，权重衰减1e-5。训练时间与基准模型相同。

硬件设备方面，我们在三种不同的移动SoC上评估了NN-Stretch，并集成了不同的CPU、GPU和DSP。表5列出了详细规格信息。Pixel 6没有配备DSP。

我们尽力在每个设备上运行不同的处理器组合，但是由于推断系统存在一些不支持的设置，无法对所有组合进行评估。例如，骁龙888芯片目前不支持TFLite Hexagon DSP代理，在小米11上无法评估DSP性能；此外，在Mali GPU上，TFLite OpenCL后端不支持具有超过四个输出张量的分割操作符。这意味着RegNetX-1.6GF/4GF无法在Pixel 6上进行评估。

能耗测量方面，我们通过读取/sys/class/power_supply来监测推断过程中手机的实时功率，并以0.1毫秒的间隔采样功率，然后对功率进行积分以获取能量消耗。

比较基准方面，我们有两个基准。第一个是使用默认TFLite进行单处理器推断的延迟。第二个是CoDL系统，即在移动CPU和GPU上利用内部运算并行性的最先进并行推断系统。为了公平比较，我们直接更新了CoDL代码以支持多分支并行推断。基准CoDL结果使用图像为基础的GPU内存类型、启发式链搜索策略和输出通道作为划分维度。

7.3 Overall Results

准确率：表7比较了NN-Stretch生成的多分支模型与给定基准模型的准确率。我们通过调整深度/宽度缩放比例为不同设备设计了不同的模型。由于Mi11和Mi9之间的CPU与GPU计算性能相似，它们共享多分支模型。我们可以看到，NN-Stretch能够保持模型的准确性。

可以通过应用知识蒸馏（KD）来重用给定模型的权重。此外，由于我们拉伸后的模型与原始模型具有类似的结构，在这种情况下，KD甚至可以表现得更好。但在我们的评估部分中，为了证明拉伸后的模型具有相同甚至更好的表达能力，我们使用与原始模型相同的训练配置从头开始训练它们。通过对ResNet-34（Mi9/C+G）和ResNet-50（Mi9/C+G）应用加权软标签蒸馏[15]，我们可以分别达到73.7%和76.9% 的准确率。

加速到TFLite：图9显示了默认TFLite上单处理器（CPU/GPU/DSP）基线和NN-Stretch之间推断延迟的比较。通过多分支模型设计和子图调度，NN-Stretch实现了基于可用性灵活的处理器组合，例如CPU+GPU、CPU+DSP、GPU+DSP和CPU+GPU+DSP，用于并行推断。相对于最快的单处理器，在三个平台上我们可以分别实现高达2.2倍、1.4倍和1.8倍的加速。当同时使用三个处理器时，获得最快的推断速度；其次是CPU+DSP，然后是CPU+GPU。需要注意的是，GPU以FP16模式运行，因此在某些模型中其性能可能不如INT8 CPU和DSP。

仅考虑分支加速时，通过添加更多处理器可以实现接近理想的加速。然而，在这种端到端加速比较中，与理想情况相比肯定存在一定差距。例如，在Mi9/C+D上的ResNet-50实现了1.5倍的加速。根据单个CPU和DSP的延迟预计应该达到1.9倍加速。主要原因如下：（1）模型的起始块和结束块没有并行化。这些块所占总延迟的比例取决于模型结构。在ResNet-50中，这占总延迟的11%；对于EfficientNet来说，则为15%。因此，EfficientNet不适合进行三处理器并行计算。（2）另一个原因是处理器之间的通信开销。以Mi9/C+D上的ResNet-50为例，这种开销占总延迟的17.9%。

由于Pixel 6和Mi11平台不支持某些功能，因此在图中缺少相应的条形图，原因在第7.2节中有解释。

加速到CoDL：图11显示了与CoDL基线的延迟比较。由于CoDL仅适用于CPU+GPU并行运行，我们还在CPU+GPU上运行了NN-Stretch。与GPU相比，NN-Stretch实现了高达1.9倍的加速，并且相对于CoDL实现了1.6倍的加速。RegNetX和EfficientNet没有进行评估，因为当前版本的CoDL不包括分组卷积和INT8深度可分离卷积。Pixel 6没有进行评估，因为CoDL使用的Mace框架不支持OpenCL 3.0。

对于这些相对较小的模型来说，由于内部操作并行性带来高通信成本，CoDL无法实现延迟降低。然而，由于NN-Stretch只需要在汇合点进行同步，在这方面开销大大减少。例如，在Mi11上运行ResNet-50时，CoDL需要12.2毫秒用于通信，占总延迟的35.3%。相比之下，NN-Stretch将通信开销降低到3.0毫秒。

功耗和能量消耗：我们还评估了NN-Stretch的功耗和能量消耗。如图10所示，对于单个处理器的功耗，将模型在CPU上运行会消耗最高的功率，范围为5.1到6.5瓦。DSP的功耗最低，范围为1.2到2.0瓦。这是由于DSP的结构较简单。有趣的是，与单个CPU相比，NN-Stretch使用多处理器并不会大幅增加功耗。最显著的增加出现在EfficientNet-Lite4上，增加了24%。这种现象是因为推断计算分布在多个处理器上，并且降低了CPU的功率和利用率。例如，在设计用于CPU+DSP的ResNet-34时，CPU分支中卷积层宽度缩放到50%，这是所有模型中最小的缩放比例之一，导致比CPU更低的功耗。

类似地，在能量方面，将模型在DSP上运行成本最低，其次是与其他处理器一起使用DSP（即GPU+DSP和CPU+GPU+DSP）。与单个CPU相比，CPU+GPU+DSP可以将能量成本降低56.3%。

讨论：尽管DSP消耗较少的功率和能量，但其适用性非常有限。它仅支持INT8精度的常见操作符、长向量计算，并且没有低级可编程API [41]。CPU和GPU仍然是移动设备上DNN推断最广泛使用的处理器。总之，NN-Stretch使得DNN推断能够根据模型和硬件特性以及延迟和能量优先级灵活选择适当的处理器来运行。

7.4 Ablation Study

由于本节评估了许多不同设计的模型，我们使用超网络训练方法将所有模型变体一起进行训练。正如您将看到的，与从头开始训练每个模型相比，超网络训练可以实现具有竞争力的准确性和延迟结果。

分段复制的有效性：为了评估在汇合点识别和分段复制后每个分支是否能够有效提取特征，我们生成一个在缩小之前进行训练和准确性评估的模型，如表8所示。结果显示，仅通过复制分段，膨胀后的模型可以实现高出1.5%的准确率，这为进一步缩小以降低延迟留下了空间。

不同的缩放策略：第4.3节建议对每个分支在不同维度上进行缩放。这样做可能使得各个分支具有更好的准确性，并更好地利用异构硬件特性。本节还评估了其他可能性（即仅对两个分支进行深度缩放或仅对两个分支进行宽度缩放），以与对每个分支进行长度和宽度缩放进行比较，如表9所示。结果显示，与其他两种方法相比，NN-Stretch可以实现更高的性能和更好的准确性。

准确率提升：除了降低延迟和保持准确性外，NN-Stretch还通过设置不同的延迟约束和不同的分支缩放比例提供了提高准确性的机会。图12显示了在Mi9/C+D上对ResNet-50进行NN-Stretch时的延迟和准确性权衡线。它位于原始模型之上，这意味着在类似的延迟下，NN-Stretch可以实现更高的模型准确性，并且因此为用户根据延迟和准确度预算提供更多选择。

适应动态工作负载：NN-Stretch可以通过利用不同可用处理器进行执行来适应动态工作负载。为了验证这一点，我们引入了干扰工作负载，并将NN-Stretch的延迟响应与单处理器基线进行比较，如图13所示。使用的干扰工作负载是Gables [16]，它在CPU或GPU上执行屋顶模型基准测试，包括内存和计算密集型操作。NN-Stretch在每次模型推断后监视处理器的利用率。如果NN-Stretch检测到处理器与其他进程存在资源争用，它将将模型移动到其他处理器上运行。

图中显示了三个阶段，由两条虚线标记。在[0, 50)模型推断期间，干扰工作负载在GPU上运行。基线推断在CPU上运行，而NN-Stretch则在GPU+DSP上运行。在[50, 155)期间，干扰工作负载以及基线都在CPU上运行。由于干扰的存在，基线的延迟变得波动不定。最差情况下的延迟可能达到222毫秒。这可能是因为Gables正在执行计算密集型操作时导致的。另一方面，在第50次推断之后检测到争用时，NN-Stretch将模型移动到GPU+DSP上运行。尽管NN-Stretch在GPU+DSP上运行ResNet-34的延迟成本高于CPU+DSP，但仍然比基线快得多。在[155, 200)期间，干扰工作负载被移回GPU上运行。基线和NN-Stretch的延迟响应变得与第一阶段（即[0, 50)）相似。

8 CONCLUSION

本文仔细研究了如何通过利用移动设备上配备的异构处理器（即CPU、GPU、DSP）来加速DNN模型的推断过程。具体而言，我们提出了将通常以顺序结构组织的模型重构为多分支结构，并将每个分支分配给一个处理器进行并发执行。

据我们所知，NN-Stretch是第一个利用分支并行性加速模型推断的工作。未来，我们将继续在这个方向上进行探索，研究如何在不同的硬件平台（如机器人或自动驾驶汽车）以及不同的深度学习模型（如自然语言处理模型）上采用我们的方法。我们希望看到分支并行性成为一种普遍类型的并行性，使得许多不同的深度学习模型推断场景受益。