MobiSys 2021 Best Paper | 可高效、準(zhǔn)確地預(yù)測模型推理時間的系統(tǒng)nn-Meter

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

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

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

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

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

論文鏈接：

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

研究背景

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

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

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

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

圖2：算子融合及其內(nèi)核實現(xiàn)

系統(tǒng)架構(gòu)

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

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

自適應(yīng)數(shù)據(jù)采樣：從整個設(shè)計空間中有效地采樣最有益的配置，以高效地構(gòu)建準(zhǔn)確的內(nèi)核級延遲預(yù)測器。

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

圖3：nn-Meter 系統(tǒng)架構(gòu)

內(nèi)核檢測

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

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

圖4：算子連接類型(從左到右)：單輸入單輸出、單輸入多輸出、多輸入單輸出

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

表1：基于融合規(guī)則的模型內(nèi)核搜索算法

自適應(yīng)數(shù)據(jù)采樣

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

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

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

構(gòu)建基準(zhǔn)數(shù)據(jù)集

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

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

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

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

表3：用于評估的邊緣設(shè)備

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

端到端的預(yù)測評估

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

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

圖5：不同預(yù)測方法的預(yù)測精度

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

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