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 應用到更多邊緣設備上，為高效模型設計做出更大的貢獻。