2021年7月7日，清华大学国强教授、智能产业研究院（AIR）首席研究员刘云新教授与微软亚洲研究院学者合作完成的论文《nn-Meter: towards accurate latency prediction of deep-learning model inferenceon diverse edge devices 》荣获MobiSys 2021大会的最佳论文奖（Best Paper Award），以及Artifact Evaluation的全部三个徽章（badge）。

Mobisys的全称为ACM International Conference on Mobile Systems, Applications, and Services，由ACM SIGMOBILE、USENIX协会与ACMSIGOPS联合发起的顶级学术会议。MobiSys会议旨在展示与移动计算和无线系统、应用、服务的设计、实现、使用、评估相关的重大创新和研究，有非常广泛的影响力和号召力。
论文解析

类型：MobiSys 2021 主会长文
题目：nn-Meter: towards accurate latencyprediction of deep-learning model inference on diverse edge devices （nn-Meter: 精准预测深度学习模型在边缘设备上的推理延迟）
作者：Li Lyna Zhang, Shihao Han, Jianyu Wei,Ningxin Zheng, Ting Cao, Yuqing Yang, Yunxin Liu
随着深度学习在移动端的兴起，推理延迟（inference latency）已经成为在各种移动和边缘设备上运行深度神经网络（DNN）模型的一个重要指标。为此，预测DNN模型推理的延迟非常必要，尤其是对于无法在真实设备上测试延迟或者代价太高的任务，例如从巨大的模型设计空间中寻找具有延迟约束的有效的DNN模型。然而，由于不同边缘设备上运行时（runtime）的不同优化导致了模型推理延迟的巨大差异，准确预测推理延迟仍然非常具有挑战性。目前，现有方法无法实现高精度的预测。
在本文中，我们提出并开发了 nn-Meter，可高效、准确地预测 DNN 模型在不同边缘设备上的推理延迟。它的关键思想是将整个模型推理划分为内核（kernel），即设备上的执行单元，然后执行内核级预测。nn-Meter 建立在两个关键技术之上：
  1. 内核检测：通过一组设计好的测试用例来自动检测模型推理的执行单元；
  2. 自适应采样：从大空间中有效地采样最有益的配置，以构建准确的内核级延迟预测器。
我们在三个常用的边缘硬件平台（移动 CPU、移动 GPU 和Intel VPU）上实现了nn-Meter系统、并使用包含26,000个模型的大型数据集进行评估，结果nn-Meter的表现明显优于先前的最好方法。
背景
目前，尽管深度神经网络大量出现，其基础算子类型数目仍然很少，比如卷积、激活函数、全连接层、BatchNorm 层和元素级算子。同时，如果要直接进行模型级别的预测，其搜索空间太大：试想一个具有N个节点的模型，每个节点有D个特征，那么在模型DAG图中最多存在N×(N-1)条边，则整个预测空间中一共有多达
个模型；所以我们需要寻找更细粒度的方法。虽然算子级别预测是一种细粒度方法，但它并不能捕捉不同设备上的图级别（graph level）的优化（如图1所示）。因此，我们提出了内核级预测方法，一种细粒度级和可感知图优化的方法。
图1 深度学习推理框架的图优化
如图1所示，深度学习推理框架通常会进行一系列模型图转换以优化模型并降低推理延迟。多数优化与后端无关，但也有依赖于目标后端的优化，例如算子融合（operator fusion，如图2所示）。这种优化可以避免将中间结果存入内存，从而降低内存访问成本。因为算子融合需要用到后端的相应内核，所以不同后端的融合规则也自然各不相同。那么，nn-Meter 的测试用例就需要能够检测不同的融合规则。
图2 注：算子融合及其内核实现
设计
系统架构
图3展示了实现 nn-Meter准确预测DNN模型推理延迟的两个核心组件：内核检测和自适应数据采样。对于每个内核，我们提取特征并预测其延迟。所有内核预测延迟之和则为整个模型的预测延迟。
图3 nn-Meter系统架构
内核检测
内核检测可以检测两个算子之间的融合规则，并搜索模型中的所有内核。我们离线收集所有融合规则。对于在线模型预测，内核搜索算法将这些规则递归地应用于目标模型来找到所有内核。
影响算子融合实现的基本因素有：算子类型、算子的连接方式。
算子类型：我们使用每两个可能的算子来组成单入单出连接，以检测它们是否可以融合。如果算子的时间遵循以下不等式1，则认为可融合。其中
为经验值。
连接方式：对于单入/出连接（图4左），只考虑相邻算子就行（即 Op1 和 Op2）；但对于多输入/输出连接，则需要考虑多种情况。比如图4右，要在
中选择离实际时间最近的。
图4 自左到右：单输入单输出、多输出、多输入
基于检测到的融合规则，对于模型图，nn-Meter 递归地将规则应用于图，以找出所有的组成内核（即融合算子）。该算法（Algorithm 1）从根算子(第22 行)开始，以深度优先的顺序对图进行遍历，如果两个算子根据规则（第11行）可以融合，则产生一个新算子（第2行）取代这两个算子。再从这个新操作符继续遍历（第 18 行），最终输出图的所有组成内核的集合。
算法1 搜寻内核
自适应数据采样
我们通过迭代采样过程对最有益的配置进行采样，并离线为目标设备上的所有内核构建机器学习预测器。同时，我们设计了一个测试集来评估采样数据的质量。在每次迭代中，使用测试集来评估更新后的机器学习预测器的性能。对于预测误差较大的数据点，我们对其附近进行更细粒度的数据采样。
最后，我们采用随机森林回归来预测非线性的内核延迟，然后使用算子的延迟总和来估计整个模型的延迟（公式 2）。
构建基准数据集
为了评估 nn-Meter 在任意 DNN 模型上的有效性，我们生成了一个适用于通道搜索和NAS场景的大型数据集。首先，我们在 ImageNet2012上收集了12个最新的、具有完全不同的算子类型和配置的CNN 模型。对于每个模型，我们通过重新采样每层的输出通道数和内核大小来生成 2,000个变体。此外，我们从 NASBench201选取了2,000个在 CIFAR10 上测试精度最高的模型，其中每个模型都有一组不同的连接结构。
总共来说，我们的数据集包含26,000个模型，包含各种不同的运算符（14 种类型）、配置（144,217 个独特点）和连接结构。其中有2,012个不同的模型图，而其余 24k个模型则具有不同的配置。如表1所示，该数据集覆盖范围很广，具有不同的 FLOPs数目 和延迟水平。
表1: 数据集中每个模型变体的FLOPs和延迟（覆盖范围很广）
评估
我们在 CPU、GPU 和 VPU（表 2）的基准数据集（表 1）上对nn-Meter进行了评估。
表2: 用于评估的边缘设备
我们使用了三种基准方法作为比较：(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 的结果（在表1中）。我们预测了每个评估设备上 26,000 个模型的延迟。值得注意的是，我们分别在移动 CPU 和 GPU 上实现了99.0% 和 99.1% 的预测准确率。在Intel VPU 上，我们可以在 ±10% 的误差范围内达到83.4%的预测准确率。
内核级预测评估
作为核心组件，内核检测器自动检测每个设备上的内核。内核级预测减少了由算子融合引起的延迟差异。为了证明有效性，我们建立了算子级别的基准方法，它预测模型中所有算子的延迟，并将它们相加为模型延迟。在所有设备上，我们的内核级预测始终优于算子级预测（如图6），而且算子级别的预测在不同的设备上表现不稳定，也不适用于非Conv主导模型。
图6 两种不同方法的 ±5% 和 ±10% 精度
自适应性数据采集评估
我们现在评估自适应数据采样的两个关键任务的性能：Conv的采样效率和模型预测的有效性。我们将其与随机抽样进行比较。从表3中可以看出，在相同数量的采样数据下，自适应数据采样比随机采样有更小的RMSE和更高的精度。然后，我们比较了用随机抽样、自适应采样数据训练的预测器所达到的模型预测精度。通过采用随机采样数据训练的Conv 预测器，三台设备的准确率分别大幅下降到 5.8%、32.3%、0%。
表3: RMSE 和 ±10% 的准确度
总结
我们提出了nn-Meter，它是一个基于内核的模型推理延迟预测系统，可以准确地预测DNN模型在不同边缘设备上的推理延迟。nn-Meter引入了内核检测，可找出算子融合行为。通过对最有价值的数据进行采样，nn-Meter有效地建立了内核的延迟预测器。我们在一个大型数据集和三种类型的边缘设备上进行了实验，充分验证了nn-Meter的有效性。
参考文献：
[1]Andrew Adams,Karima Ma, Luke Anderson, Riyadh Baghdadi, Tzu-Mao Li, Michaël Gharbi, BenoitSteiner, Steven Johnson, Kayvon Fatahalian, Frédo Durand, and JonathanRagan-Kelley. 2019. Learning to Optimize Halide with Tree Search and RandomPrograms. ACM Trans. Graph. 38, 4, Article 121 (July 2019), 12 pages.
[2]BRP-NASauthors. 2020. Eagle: Efficient and Agile Performance Estimator and Dataset. https://github.com/thomasccp/eagle.
[3]Andrea Di Biagio.2018. llvm-mca: a static performance analysis tool.
[4] Nathan L. Binkert, Bradford M. Beckmann, Gabriel Black, Steven K.Reinhardt, Ali G. Saidi, Arkaprava Basu, Joel Hestness, Derek Hower, TusharKrishna, Somayeh Sardashti, Rathijit Sen, Korey Sewell, Muhammad Shoaib BinAltaf, Nilay Vaish, Mark D. Hill, and David A. Wood. 2011. The gem5simulator. SIGARCH Comput. Archit. News 39, 2 (2011), 1--7.
[5] Ermao Cai, Da-Cheng Juan, Dimitrios Stamoulis, and Diana Marculescu.2017. NeuralPower: Predict and Deploy Energy-Efficient ConvolutionalNeural Networks. In Proceedings of the Ninth Asian Conference on MachineLearning (Proceedings of Machine Learning Research). PMLR, 622--637.
[6] Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. 2020.Once-for-all: Train One Network and Specialize it for Efficient Deployment.In International Conference on Learning Representations (ICLR).
[7] Han Cai, Ligeng Zhu, and Song Han. 2019. ProxylessNAS: Direct NeuralArchitecture Search on Target Task and Hardware. In InternationalConference on Learning Representations (ICLR).
[8] Tianqi Chen and Carlos Guestrin. 2016. XGBoost: A Scalable TreeBoosting System. In Proceedings of the 22nd ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining (KDD).
[9] Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan,Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin,and Arvind Krishnamurthy. 2018. TVM: An Automated End-to-End OptimizingCompiler for Deep Learning. In 13th USENIX Symposium on Operating SystemsDesign and Implementation (OSDI). USENIX Association, Carlsbad, CA,578--594.
[10] Tianqi Chen, Lianmin Zheng, Eddie Yan, Ziheng Jiang, Thierry Moreau,Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. Learning toOptimize Tensor Programs (NIPS'18). Curran Associates Inc., Red Hook,NY, USA, 3393—3404.
[11] Xiaoliang Dai, Peizhao Zhang, Bichen Wu, Hongxu Yin, Fei Sun,Yanghan Wang, Marat Dukhan, Yunqing Hu, Yiming Wu, Yangqing Jia, et al. 2019.Chamnet: Towards efficient network design through platform-aware modeladaptation. In Proceedings of the IEEE Conference on Computer Vision andPattern Recognition. 11398--11407.
[12]Xuanyi Dong and Yi Yang. 2020.NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search.In International Conference on Learning Representations (ICLR).
[13] Lukasz Dudziak, Thomas Chau, Mohamed Abdelfattah, Royson Lee, HyejiKim, and Nicholas Lane. 2020. BRP-NAS: Prediction-based NAS using GCNs.In Advances in Neural Information Processing Systems (Neurips), H.Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.), Vol. 33.Curran Associates, Inc., 10480--10490. https://proceedings.neurips.cc/paper/2020/file/768e78024aa8fdb9b8fe87be86f64745-Paper.pdf
[14] Song Han, Huizi Mao, and William J. Dally. 2016. Deep Compression:Compressing Deep Neural Networks with Pruning, Trained Quantization and HuffmanCoding. In International Conference on Learning Representations (ICLR).
[15] Yihui He, Ji Lin, Zhijian Liu, Hanrui Wang, Li-Jia Li, and Song Han.2018. AMC: AutoML for Model Compression and Acceleration on Mobile Devices.In European Conference on Computer Vision (ECCV).
[16] Ling Huang, Jinzhu Jia, Bin Yu, Byung-Gon Chun, Petros Maniatis, andMayur Naik. 2010. Predicting Execution Time of Computer Programs Using SparsePolynomial Regression. In Advances in Neural Information ProcessingSystems (NIPS).
[17] Intel. 2019. Deploy High-Performance Deep Learning Inference,Open-VINO. https://software.intel.com/content/www/us/en/develop/tools/openvino-toolkit.html.
[18] Gideon Stupp Israel Hirsh. 2019. Intel Architecture CodeAnalyzer.
[19] Samuel J. Kaufman, Phitchaya Mangpo Phothilimthana, and MikeBurrows. 2019. Learned TPU Cost Model for XLA Tensor Programs. NeurIPSworkshop.
[20] Mahmoud Khairy, Zhesheng Shen, Tor M. Aamodt, and Timothy G. Rogers.2020. Accel-Sim: An Extensible Simulation Framework for Validated GPU Modeling.In 47th ACM/IEEE Annual International Symposium on Computer Architecture,ISCA 2020, Valencia, Spain, May 30 - June 3, 2020. IEEE, 473--486. 
[21] Breiman Leo. 2001. Random Forests. In MachineLearning. 5--32.
[22] Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans PeterGraf. 2017. Pruning Filters for Efficient ConvNets. In The InternationalConference on Learning Representations (ICLR).
[23] Hanxiao Liu, Karen Simonyan, and Yiming Yang. 2019. DARTS:Differentiable Architecture Search. In International Conference onLearning Representations (ICLR).
[24] Zechun Liu, Haoyuan Mu, Xiangyu Zhang, Zichao Guo, Tim Kwang-TingCheng Xin Yang, and Jian Sun. 2019. MetaPruning: Meta Learning for AutomaticNeural Architecture Channel Pruning. In Proceedings of the IEEE/CVFInternational Conference on Computer Vision (ICCV).
[25] Charith Mendis, Alex Renda, Saman Amarasinghe, and Michael Carbin.2019. Ithemal: Accurate, Portable and Fast Basic Block Throughput Estimationusing Deep Neural Networks. In Proceedings of the 36th InternationalConference on Machine Learning (ICML). 4505--4515.
[26] Microsoft. 2019. Neural Network Intelligence. https://github.com/microsoft/nni.
[27] Hang Qi, Evan R. Sparks, and Ameet Talwalkar. 2017. Paleo: APerformance Model for Deep Neural Networks. In International Conference onLearning Representations (ICLR).
[28] Stefan Reif, Judith Hemp Benedict Herzog, Timo Hönig, and WolfgangSchröder-Preikschat. 2020. Precious: Resource-Demand Estimation for EmbeddedNeural Network Accelerators. In First International Workshop onBenchmarking Machine Learning Workloads on Emerging Hardware.
[29] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler,Andrew Howard, and Quoc V Le. 2019. Mnasnet: Platform-aware neural architecturesearch for mobile. In Proceedings of the IEEE Conference on ComputerVision and Pattern Recognition (CVPR). 2820--2828.
[30] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler,Andrew Howard, and Quoc V Le. 2019. Mnasnet: Platform-aware neural architecturesearch for mobile. In Proceedings of the IEEE Conference on ComputerVision and Pattern Recognition (CVPR).
[31] Iulia Turc, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.2019. Well-Read Students Learn Better: On the Importance of Pre-trainingCompact Models. arXiv:1908.08962 [cs.CL]
[32] Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, YimingWu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer. 2019. Fbnet:Hardware-aware efficient convnet design via differentiable neural architecturesearch. In Proceedings of the IEEE Conference on Computer Vision andPattern Recognition (CVPR). 10734--10742.
[33] Mengwei Xu, Jiawei Liu, Yuanqiang Liu, Felix Xiaozhu Lin, YunxinLiu, and Xuanzhe Liu. 2019. A First Look at Deep Learning Apps on Smartphones.In The World Wide Web Conference (WWW).
[34] Li Lyna Zhang, Yuqing Yang, Yuhang Jiang, Wenwu Zhu, and Yunxin Liu.2020. Fast Hardware-Aware Neural Architecture Search. In Proceedings ofthe IEEE Computer Vision and Pattern Recognition Workshops (CVPRW).
[35] Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. 2018.Shufflenet: An extremely efficient convolutional neural network for mobiledevices. In Proceedings of the IEEE Conference on Computer Vision andPattern Recognition (CVPR).
作者及单位：
Li LynaZhang （张丽）：微软亚洲研究院高级研究员
Shihao Han （韩世豪）：罗斯-霍曼理工学院学生，微软亚洲研究院实习生
Jianyu Wei （魏剑宇）：中国科学技术大学学生，微软亚洲研究院实习生
NingxinZheng （郑宁馨）：微软亚洲研究院研发工程师
Ting Cao （曹婷）：微软亚洲研究院高级研究员
Yuqing Yang（杨玉庆）：微软亚洲研究院高级研发经理
Yunxin Liu（刘云新）：清华大学国强教授、智能产业研究院首席研究员
撰文 / 蔡依宸 
编辑排版 / 冼晓晴
校对责编 / 黄妍
关于AIR
清华大学智能产业研究院（Institute for AI Industry Research, Tsinghua University，英文简称AIR，THU）是面向第四次工业革命的国际化、智能化、产业化的应用研究机构。AIR的使命是利用人工智能技术赋能产业升级、推动社会进步。通过大学与企业创新双引擎，突破人工智能核心技术，培养智能产业领军人才，推动智能产业跨越式发展。
AIR于2020年由多媒体及人工智能领域的世界级科学家、企业家张亚勤院士创建。
智慧交通（AI+Transportation）、智慧物联（AI+IoT）、智慧医疗（AI+Healthcare）是清华大学智能产业研究院的三个重点研发方向。
AIR长期招聘人工智能领域优秀科研人员
点这里 关注我们
往期精彩：
刘菁菁：How Multimodal AI Empowers People
【预告】AIR学术工作坊第2期｜数据安全和可信AI
AIR与亚信科技联合团队荣获“2021中国RPA+AI开发者大赛”全国冠军暨特等奖
和AIR一起！对话图灵奖得主John E. Hopcroft教授
全球首份！清华大学智能产业研究院联合百度Apollo发布车路协同技术创新白皮书
继续阅读
阅读原文