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

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

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

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

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

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

論文鏈接：

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

研究背景

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

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

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

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

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

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

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

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

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

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

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

內(nèi)核檢測(cè)

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

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

圖4：算子連接類型(從左到右)：?jiǎn)屋斎雴屋敵觥屋斎攵噍敵?、多輸入單輸?/p>

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

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

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

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

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

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

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

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

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

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

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

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

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

端到端的預(yù)測(cè)評(píng)估

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

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

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

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

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