MobiSys 2021 Best Paper | 可高效、準確地預測模型推理時(shí)間的系統nn-Meter

編者按：近日，移動(dòng)計算領(lǐng)域的國際頂級學(xué)術(shù)會(huì )議 MobiSys 2021 在線(xiàn)上舉辦。該大會(huì )由 ACM SIGMOBILE、USENIX 協(xié)會(huì )與 ACMSIGOPS 聯(lián)合發(fā)起，旨在展示與移動(dòng)計算和無(wú)線(xiàn)系統、應用、服務(wù)的設計、實(shí)現、使用、評估相關(guān)的重大創(chuàng )新和研究，在移動(dòng)計算領(lǐng)域具有非常廣泛的影響力和號召力。 

本年度的 MobiSys 大會(huì )共接收到了166篇投稿，而最終入選的論文為36篇。其中，微軟亞洲研究院的論文“nn-Meter: Towards Accurate Latency Prediction of Deep-Learning Model Inference on Diverse Edge Devices”獲得了 MobiSys 2021 的最佳論文獎（Best Paper），并且成為本屆大會(huì )中唯一個(gè)獲得了 Artifact Evaluation 全部三個(gè)最高級別徽章的工作。

深度神經(jīng)網(wǎng)絡(luò )（DNN）模型在實(shí)際部署中的延遲（推理時(shí)間）是決定模型是否可用的一個(gè)重要指標。然而，模型設計過(guò)程中對數以?xún)|計的設計選項進(jìn)行實(shí)際的部署和延遲評估會(huì )造成巨大的開(kāi)銷(xiāo)。因此，如何進(jìn)行高效、準確的模型運行延遲預測對模型的設計至關(guān)重要。但現有技術(shù)缺乏對部署平臺優(yōu)化策略的理解以及對靈活多變模型架構的泛化性，所以無(wú)法做到準確的模型推理時(shí)間預測。

針對上述問(wèn)題，微軟亞洲研究院異構計算組的研究員們提出并開(kāi)發(fā)了nn-Meter 模型推理時(shí)間預測系統。該系統可高效、準確地預測 DNN 模型在不同邊緣設備上的推理延遲，其關(guān)鍵思想是將整個(gè)模型劃分為內核（kernel），即設備上的執行單元，然后執行內核級預測。

相關(guān)論文“nn-Meter: Towards Accurate Latency Prediction of Deep-Learning Model Inference on Diverse Edge Devices”榮獲了 MobiSys 2021 大會(huì )的最佳論文獎（Best Paper），并且是本屆大會(huì )唯一一篇獲得了 Artifact Evaluation 全部三個(gè)最高級別徽章（即代碼可評估、代碼可獲取和實(shí)驗結果可復制）的論文。

論文鏈接：

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

研究背景

事實(shí)上，由于深度學(xué)習算法的飛速發(fā)展（如NAS），每一年都有大量新的網(wǎng)絡(luò )結構出現，例如，MIT 提出的 OFA, 可一次性搜索出50個(gè)滿(mǎn)足不同推理時(shí)間要求的網(wǎng)絡(luò )。這使得預測神經(jīng)網(wǎng)絡(luò )推理時(shí)間時(shí)，必須考慮到預測方法在新網(wǎng)絡(luò )結構上的可泛化性。同時(shí)，如果要直接進(jìn)行模型級別的預測，其搜索空間太大：試想一個(gè)具有 N 個(gè)節點(diǎn)的模型，每個(gè)節點(diǎn)有 D 個(gè)特征，那么在模型 DAG 圖中最多存在 N×(N-1) 條邊，則整個(gè)預測空間中一共有多達 D^N×N×(N-1) 個(gè)模型，所以這就需要尋找更細粒度的方法。

雖然算子級別預測是一種細粒度方法，但它并不能捕捉不同設備上的圖級別（graph level）優(yōu)化（如圖1所示）。好在盡管深度神經(jīng)網(wǎng)絡(luò )大量出現，但其基礎算子類(lèi)型數目仍然很少，比如卷積、激活函數、全連接層、BatchNorm 層和元素級算子。這些較穩定的基礎算子又進(jìn)一步根據推理平臺的優(yōu)化構成了內核，而任意的神經(jīng)網(wǎng)絡(luò )結構本質(zhì)就是由這些基礎算子及內核構成的。因此，微軟亞洲研究院的研究員們提出了內核級預測方法，這是一種細粒度級和可感知圖優(yōu)化的方法。

圖1：深度學(xué)習推理框架的圖優(yōu)化

如圖1所示，深度學(xué)習推理框架通常會(huì )進(jìn)行一系列模型圖轉換，以?xún)?yōu)化模型并降低推理延遲。多數優(yōu)化與后端無(wú)關(guān)，但也有依賴(lài)于目標后端的優(yōu)化，例如算子融合（operator fusion，如圖2所示）。這種優(yōu)化可以避免將中間結果存入內存，從而降低內存訪(fǎng)問(wèn)的成本。因為算子融合需要用到后端的相應內核，所以不同后端的融合規則也自然各不相同。那么，nn-Meter 的測試用例就需要能夠檢測不同的融合規則。

圖2：算子融合及其內核實(shí)現

系統架構

nn-Meter 建立在兩個(gè)關(guān)鍵技術(shù)之上，從而可以準確預測不同模型在部署中的推理時(shí)間，以設計真正高效的模型：

內核檢測：能夠自動(dòng)識別部署平臺的優(yōu)化策略，從而基于這些策略將模型分解為實(shí)際運行的內核。

自適應數據采樣：從整個(gè)設計空間中有效地采樣最有益的配置，以高效地構建準確的內核級延遲預測器。

圖3展示了實(shí)現 nn-Meter 準確預測 DNN 模型推理延遲的兩個(gè)核心組件：內核檢測（Kernel Detection）和自適應數據采樣（Adaptive Data Sampling）。對于每個(gè)內核，nn-Meter 都會(huì )提取特征并預測其延遲，所有內核預測延遲之和則為整個(gè)模型的預測延遲。

圖3：nn-Meter 系統架構

內核檢測

內核檢測可以自動(dòng)識別部署平臺的算子融合規則，從而基于這些規則檢測模型中的所有內核。nn-Meter 會(huì )離線(xiàn)收集所有融合規則，對于在線(xiàn)模型預測，內核搜索算法則會(huì )將這些規則遞歸地應用于目標模型來(lái)找到所有內核。

影響算子融合的基本因素是算子類(lèi)型和算子的連接方式。因此，nn-Meter 對不同的算子類(lèi)型和連接方式分別設計了測試用例以識別融合規則。對算子類(lèi)型，nn-Meter 使用每?jì)蓚€(gè)可能的算子來(lái)組成單入單出連接（圖4（1)），并通過(guò)時(shí)間差來(lái)決定是否發(fā)生了算子融合（如果融合發(fā)生，兩個(gè)相連算子的運行時(shí)間要遠小于算子單獨運行的時(shí)間和）。對這些可融合的算子，nn-Meter 會(huì )用同樣的時(shí)間差方法來(lái)識別多入多出情況下（圖4（2、3））算子融合的規則。

圖4：算子連接類(lèi)型(從左到右)：?jiǎn)屋斎雴屋敵?、單輸入多輸出、多輸入單輸?/p>

基于檢測到的融合規則，nn-Meter 遞歸地將這些規則應用于模型圖，以找出所有的組成內核（即融合算子）。該算法（如表1）從根算子(第22行)開(kāi)始，以深度優(yōu)先的順序對圖進(jìn)行了遍歷，如果兩個(gè)算子根據規則（第11行）可以融合，則產(chǎn)生一個(gè)新算子（第2行）取代這兩個(gè)算子。之后再從這個(gè)新操作符繼續遍歷（第18行），最終輸出圖的所有組成內核的集合。

表1：基于融合規則的模型內核搜索算法

自適應數據采樣

接下來(lái)，研究員們對根據內核檢測算法檢測出的內核單元構建了推理時(shí)間預測器。由于目前并不存在內核級別的數據集，所以研究員們需要構建針對目標硬件平臺上的數據集。然而某些內核所具有的數據采樣空間巨大，例如 Conv-bn-relu 的采樣空間已達到千萬(wàn)數量級。因此，研究員們通過(guò)迭代采樣過(guò)程對最有益的配置進(jìn)行采樣，并離線(xiàn)為目標設備上的所有內核構建機器學(xué)習預測器。

綜合研究員們對于模型設計和模型在硬件平臺上的表現的觀(guān)察，該自適應數據采樣主要采集兩方面的數據。首先是目前模型設計空間中考慮的內核配置參數，研究員們通過(guò)計算當前設計空間的配置參數取值概率分布并根據此概率分布進(jìn)行采樣。第二是某些會(huì )觸發(fā)硬件平臺特殊優(yōu)化的內核配置參數需要采樣，考慮到這些硬件優(yōu)化比較復雜，研究員們設計了一個(gè)自適應數據采樣方法來(lái)逐漸學(xué)習采樣。同時(shí)，算法還設計了一個(gè)測試集來(lái)評估采樣數據的質(zhì)量。在每次迭代中，研究員們可以使用測試集來(lái)評估更新后的機器學(xué)習預測器的性能，對于預測誤差較大的數據點(diǎn)，算法可對其附近進(jìn)行更細粒度的數據采樣。

最后，nn-Meter 采用了隨機森林回歸來(lái)預測非線(xiàn)性的內核延遲，然后使用算子的延遲總和來(lái)估計整個(gè)模型的延遲（公式如下）。

構建基準數據集

為了評估 nn-Meter 在任意 DNN 模型上的有效性，研究員們生成了一個(gè)適用于通道搜索和NAS場(chǎng)景的大型數據集。首先，研究員們在 ImageNet 2012 上收集了12個(gè)最新的、具有完全不同的算子類(lèi)型和配置的 CNN 模型。然后對每個(gè)模型再通過(guò)重新采樣每層的輸出通道數和內核大小來(lái)生成2,000個(gè)變體。此外，研究員們還從 NASBench201 選取了2,000個(gè)在 CIFAR10 上測試精度最高的模型，其中每個(gè)模型都有一組不同的連接結構。

總共來(lái)說(shuō)，該基準數據集包含有26,000個(gè)模型，涉及各種不同的運算符（14種類(lèi)型）、配置（144,217個(gè)獨特點(diǎn)）和連接結構。其中有2,012個(gè)不同的模型圖，而其余24,000個(gè)模型則具有不同的配置。如表2所示，該數據集覆蓋范圍廣泛，具有不同的 FLOPs 數目和延遲水平。

表2：數據集中每個(gè)模型變體的 FLOPs 和延遲

研究員們在 CPU、GPU 和 VPU（表 3）的基準數據集（表 2）上對 nn-Meter 進(jìn)行了評估。

表3：用于評估的邊緣設備

nn-Meter 使用了三種基準方法作為比較：(1)FLOPs, (2) FLOPs+MAC, (3) BRP-NAS；并通過(guò)回歸中的標準指標：均方根誤差 (RMSE) 和相對均方根百分比誤差 (RMSPE)，來(lái)評估預測性能。在該論文中，±10% 的誤差邊界是最大可接受的預測誤差。

端到端的預測評估

nn-Meter 不需要模型級數據來(lái)構建預測器，而且還可以在它從未見(jiàn)過(guò)的模型上進(jìn)行預測：論文選擇了 AlexNets、VGGs、MobileNetv1s、MobileNetv2s和 NASBench201 進(jìn)行評估。對于每個(gè)模型變體，先將該變體作為測試集，剩下的模型變體作為訓練集來(lái)訓練基準方法，然后再進(jìn)行交叉驗證得到評估結果。nn-Meter 則通過(guò)所有內核的預測延遲總和來(lái)預測模型整體延遲。

圖5顯示了不同預測方法的預測精度。與基準方法相比，nn-Meter 是唯一能夠在各種設備上始終實(shí)現準確預測的方法。平均而言，nn-Meter 89.2% 的準確率明顯優(yōu)于 FLOPs (22.1%)、FLOPs+MAC(17.1%) 和 BRP-NAS (8.5%)。

圖5：不同預測方法的預測精度

nn-Meter 在完整的包含26,000個(gè)模型的基準數據集上（表2） 的預測結果中，分別在移動(dòng) CPU 和 GPU 上實(shí)現了99.0%和99.1%的預測準確率。在 Intel VPU 上，nn-Meter 則可以在±10%的誤差范圍內達到83.4%的預測準確率。

綜上所述，研究員們提出的 nn-Meter 是一個(gè)基于內核的模型推理延遲預測系統，可以準確地預測 DNN 模型在不同邊緣設備上的推理延遲。nn-Meter 引入了內核檢測，可找出算子融合行為。而通過(guò)對最有價(jià)值的數據進(jìn)行采樣，nn-Meter 有效地建立了內核的延遲預測器。在一個(gè)大型數據集和三種類(lèi)型的邊緣設備上進(jìn)行實(shí)驗評估后也充分驗證了 nn-Meter 的有效性。未來(lái)，研究員們將把 nn-Meter 應用到更多邊緣設備上，為高效模型設計做出更大的貢獻。