MobiSys 2021 Best Paper | 可高效、准确地预测模型推理时间的系统nn-Meter

编者按：近日，移动计算领域的国际顶级学术会议 MobiSys 2021 在线上举办。该大会由 ACM SIGMOBILE、USENIX 协会与 ACMSIGOPS 联合发起，旨在展示与移动计算和无线系统、应用、服务的设计、实现、使用、评估相关的重大创新和研究，在移动计算领域具有非常广泛的影响力和号召力。 

本年度的 MobiSys 大会共接收到了166篇投稿，而最终入选的论文为36篇。其中，微软亚洲研究院的论文“nn-Meter: Towards Accurate Latency Prediction of Deep-Learning Model Inference on Diverse Edge Devices”获得了 MobiSys 2021 的最佳论文奖（Best Paper），并且成为本届大会中唯一个获得了 Artifact Evaluation 全部三个最高级别徽章的工作。

深度神经网络（DNN）模型在实际部署中的延迟（推理时间）是决定模型是否可用的一个重要指标。然而，模型设计过程中对数以亿计的设计选项进行实际的部署和延迟评估会造成巨大的开销。因此，如何进行高效、准确的模型运行延迟预测对模型的设计至关重要。但现有技术缺乏对部署平台优化策略的理解以及对灵活多变模型架构的泛化性，所以无法做到准确的模型推理时间预测。

针对上述问题，微软亚洲研究院异构计算组的研究员们提出并开发了nn-Meter 模型推理时间预测系统。该系统可高效、准确地预测 DNN 模型在不同边缘设备上的推理延迟，其关键思想是将整个模型划分为内核（kernel），即设备上的执行单元，然后执行内核级预测。

相关论文“nn-Meter: Towards Accurate Latency Prediction of Deep-Learning Model Inference on Diverse Edge Devices”荣获了 MobiSys 2021 大会的最佳论文奖（Best Paper），并且是本届大会唯一一篇获得了 Artifact Evaluation 全部三个最高级别徽章（即代码可评估、代码可获取和实验结果可复制）的论文。

论文链接：

https://dl.acm.org/doi/pdf/10.1145/3458864.3467882

研究背景

事实上，由于深度学习算法的飞速发展（如NAS），每一年都有大量新的网络结构出现，例如，MIT 提出的 OFA, 可一次性搜索出50个满足不同推理时间要求的网络。这使得预测神经网络推理时间时，必须考虑到预测方法在新网络结构上的可泛化性。同时，如果要直接进行模型级别的预测，其搜索空间太大：试想一个具有 N 个节点的模型，每个节点有 D 个特征，那么在模型 DAG 图中最多存在 N×(N-1) 条边，则整个预测空间中一共有多达 D^N×N×(N-1) 个模型，所以这就需要寻找更细粒度的方法。

虽然算子级别预测是一种细粒度方法，但它并不能捕捉不同设备上的图级别（graph level）优化（如图1所示）。好在尽管深度神经网络大量出现，但其基础算子类型数目仍然很少，比如卷积、激活函数、全连接层、BatchNorm 层和元素级算子。这些较稳定的基础算子又进一步根据推理平台的优化构成了内核，而任意的神经网络结构本质就是由这些基础算子及内核构成的。因此，微软亚洲研究院的研究员们提出了内核级预测方法，这是一种细粒度级和可感知图优化的方法。

图1：深度学习推理框架的图优化

如图1所示，深度学习推理框架通常会进行一系列模型图转换，以优化模型并降低推理延迟。多数优化与后端无关，但也有依赖于目标后端的优化，例如算子融合（operator fusion，如图2所示）。这种优化可以避免将中间结果存入内存，从而降低内存访问的成本。因为算子融合需要用到后端的相应内核，所以不同后端的融合规则也自然各不相同。那么，nn-Meter 的测试用例就需要能够检测不同的融合规则。

图2：算子融合及其内核实现

系统架构

nn-Meter 建立在两个关键技术之上，从而可以准确预测不同模型在部署中的推理时间，以设计真正高效的模型：

内核检测：能够自动识别部署平台的优化策略，从而基于这些策略将模型分解为实际运行的内核。

自适应数据采样：从整个设计空间中有效地采样最有益的配置，以高效地构建准确的内核级延迟预测器。

图3展示了实现 nn-Meter 准确预测 DNN 模型推理延迟的两个核心组件：内核检测（Kernel Detection）和自适应数据采样（Adaptive Data Sampling）。对于每个内核，nn-Meter 都会提取特征并预测其延迟，所有内核预测延迟之和则为整个模型的预测延迟。

图3：nn-Meter 系统架构

内核检测

内核检测可以自动识别部署平台的算子融合规则，从而基于这些规则检测模型中的所有内核。nn-Meter 会离线收集所有融合规则，对于在线模型预测，内核搜索算法则会将这些规则递归地应用于目标模型来找到所有内核。

影响算子融合的基本因素是算子类型和算子的连接方式。因此，nn-Meter 对不同的算子类型和连接方式分别设计了测试用例以识别融合规则。对算子类型，nn-Meter 使用每两个可能的算子来组成单入单出连接（图4（1)），并通过时间差来决定是否发生了算子融合（如果融合发生，两个相连算子的运行时间要远小于算子单独运行的时间和）。对这些可融合的算子，nn-Meter 会用同样的时间差方法来识别多入多出情况下（图4（2、3））算子融合的规则。

图4：算子连接类型(从左到右)：单输入单输出、单输入多输出、多输入单输出

基于检测到的融合规则，nn-Meter 递归地将这些规则应用于模型图，以找出所有的组成内核（即融合算子）。该算法（如表1）从根算子(第22行)开始，以深度优先的顺序对图进行了遍历，如果两个算子根据规则（第11行）可以融合，则产生一个新算子（第2行）取代这两个算子。之后再从这个新操作符继续遍历（第18行），最终输出图的所有组成内核的集合。

表1：基于融合规则的模型内核搜索算法

自适应数据采样

接下来，研究员们对根据内核检测算法检测出的内核单元构建了推理时间预测器。由于目前并不存在内核级别的数据集，所以研究员们需要构建针对目标硬件平台上的数据集。然而某些内核所具有的数据采样空间巨大，例如 Conv-bn-relu 的采样空间已达到千万数量级。因此，研究员们通过迭代采样过程对最有益的配置进行采样，并离线为目标设备上的所有内核构建机器学习预测器。

综合研究员们对于模型设计和模型在硬件平台上的表现的观察，该自适应数据采样主要采集两方面的数据。首先是目前模型设计空间中考虑的内核配置参数，研究员们通过计算当前设计空间的配置参数取值概率分布并根据此概率分布进行采样。第二是某些会触发硬件平台特殊优化的内核配置参数需要采样，考虑到这些硬件优化比较复杂，研究员们设计了一个自适应数据采样方法来逐渐学习采样。同时，算法还设计了一个测试集来评估采样数据的质量。在每次迭代中，研究员们可以使用测试集来评估更新后的机器学习预测器的性能，对于预测误差较大的数据点，算法可对其附近进行更细粒度的数据采样。

最后，nn-Meter 采用了随机森林回归来预测非线性的内核延迟，然后使用算子的延迟总和来估计整个模型的延迟（公式如下）。

构建基准数据集

为了评估 nn-Meter 在任意 DNN 模型上的有效性，研究员们生成了一个适用于通道搜索和NAS场景的大型数据集。首先，研究员们在 ImageNet 2012 上收集了12个最新的、具有完全不同的算子类型和配置的 CNN 模型。然后对每个模型再通过重新采样每层的输出通道数和内核大小来生成2,000个变体。此外，研究员们还从 NASBench201 选取了2,000个在 CIFAR10 上测试精度最高的模型，其中每个模型都有一组不同的连接结构。

总共来说，该基准数据集包含有26,000个模型，涉及各种不同的运算符（14种类型）、配置（144,217个独特点）和连接结构。其中有2,012个不同的模型图，而其余24,000个模型则具有不同的配置。如表2所示，该数据集覆盖范围广泛，具有不同的 FLOPs 数目和延迟水平。

表2：数据集中每个模型变体的 FLOPs 和延迟

研究员们在 CPU、GPU 和 VPU（表 3）的基准数据集（表 2）上对 nn-Meter 进行了评估。

表3：用于评估的边缘设备

nn-Meter 使用了三种基准方法作为比较：(1)FLOPs, (2) FLOPs+MAC, (3) BRP-NAS；并通过回归中的标准指标：均方根误差 (RMSE) 和相对均方根百分比误差 (RMSPE)，来评估预测性能。在该论文中，±10% 的误差边界是最大可接受的预测误差。

端到端的预测评估

nn-Meter 不需要模型级数据来构建预测器，而且还可以在它从未见过的模型上进行预测：论文选择了 AlexNets、VGGs、MobileNetv1s、MobileNetv2s和 NASBench201 进行评估。对于每个模型变体，先将该变体作为测试集，剩下的模型变体作为训练集来训练基准方法，然后再进行交叉验证得到评估结果。nn-Meter 则通过所有内核的预测延迟总和来预测模型整体延迟。

图5显示了不同预测方法的预测精度。与基准方法相比，nn-Meter 是唯一能够在各种设备上始终实现准确预测的方法。平均而言，nn-Meter 89.2% 的准确率明显优于 FLOPs (22.1%)、FLOPs+MAC(17.1%) 和 BRP-NAS (8.5%)。

图5：不同预测方法的预测精度

nn-Meter 在完整的包含26,000个模型的基准数据集上（表2） 的预测结果中，分别在移动 CPU 和 GPU 上实现了99.0%和99.1%的预测准确率。在 Intel VPU 上，nn-Meter 则可以在±10%的误差范围内达到83.4%的预测准确率。

综上所述，研究员们提出的 nn-Meter 是一个基于内核的模型推理延迟预测系统，可以准确地预测 DNN 模型在不同边缘设备上的推理延迟。nn-Meter 引入了内核检测，可找出算子融合行为。而通过对最有价值的数据进行采样，nn-Meter 有效地建立了内核的延迟预测器。在一个大型数据集和三种类型的边缘设备上进行实验评估后也充分验证了 nn-Meter 的有效性。未来，研究员们将把 nn-Meter 应用到更多边缘设备上，为高效模型设计做出更大的贡献。