基于邊緣計算的分支神經網絡模型推斷延遲優化

樊 琦，李 卓*，陳 昕

（1.網絡文化與數字傳播北京市重點實驗室（北京信息科技大學），北京100101；2.北京信息科技大學計算機學院，北京100101）

0 引言

近年來，深度學習在一些領域取得巨大成功，其中的深度神經網絡（Deep Neural Network，DNN）方法在各種任務上取得了很好的效果。越來越多的推斷任務譬如自動駕駛［1］、智能語音［2］、圖像識別［3］等都需要用到神經網絡。深度神經網絡主要由多個卷積層、全連接層組成。其中的每一層都對輸入數據進行處理，并傳輸到下一層，在最終層輸出推斷結果。

高精度的DNN 模型有更多的網絡層數，也需要更多的計算資源。目前智能應用任務中，通常將DNN 部署在計算資源充足的云端服務器［4］。在這種方式下，需要數據源把任務數據傳輸至云端的模型中執行推斷任務；云計算模式存在著延遲高、隱私性低和通信成本高等問題［5］，無法很好地滿足任務需求。還有的做法嘗試將推斷模型部署至移動設備端［6］，但由于移動設備受限的資源情況，只能運行簡單的機器學習方法，最終得到精度不高的推斷結果。

邊緣計算作為一種新型計算模式，其核心原則之一是將計算能力推向邊緣，得到了研究人員廣泛關注［7］。在邊緣計算場景下，將DNN 模型部署在設備周圍的邊緣計算節點上。相對于到云服務的距離，邊緣計算節點到數據源近得多，所以低時延特性能輕松實現。但目前的邊緣計算設備處理能力有限，單個邊緣計算節點可能無法很好地完成復雜網絡模型的推斷任務，因此需要多個邊緣計算節點共同部署DNN 模型。在邊緣計算場景下部署DNN的主要挑戰是如何挑選出合適的計算節點來部署模型，要考慮到神經網絡模型的切分、模型的計算需求及邊緣計算節點的網絡狀況，以此來優化多個計算節點協同運行神經網絡模型時的延遲。圖1 展示了分別在云計算和邊緣計算下進行深度學習的場景。云計算場景下用戶設備發送的數據通過網絡上傳到云服務器進行推斷任務。而邊緣計算場景下云服務器只進行延遲容忍的模型訓練過程，然后將訓練好的模型部署在邊緣節點，數據源將推斷任務數據傳輸至邊緣節點，DNN模型進行推斷后再為數據源返回推斷結果。

圖1 云計算與邊緣計算的深度學習模型對比Fig.1 Deep learning model comparison of cloud computing and edge computing

本文主要研究了如何在邊緣計算環境下減少DNN 的推斷延遲。利用BranchyNet深度學習框架在云端服務器上訓練好具有多個分支的DNN 模型，證明了分支神經網絡的分布式部署問題是NP難的，設計并實現了基于分支定界思想的部署算法（Deployment algorithm based on Branch and Bound，DBB），來為DNN 模型找到有最小運行延遲的邊緣節點部署方案。針對數據源推斷任務的延遲要求、地理分布特性，提出選擇節點退出（Select the Node Exit，SNE）算法，為不同的推斷任務數據源選擇合適的邊緣計算節點返回推斷結果。實驗結果表明，與在云端部署神經網絡模型的方法相比，基于邊緣的神經網絡模型推斷方法平均降低了36%的延遲消耗。

1 相關工作

深度學習任務主要分為訓練和推理兩個階段。神經網絡層數的增多帶來的是訓練和推斷延遲以及成本的增大。為使DNN 更好服務于應用，目前有研究關注神經網絡的分布式訓練方面，比如：文獻［8］提出的參數服務器框架，用并行的方式，使用參數服務器在訓練時更新節點參數，以縮短大數據環境下深度學習的訓練時間；文獻［9］考慮了訓練DNN 模型時分布式服務器之間的通信開銷，研究了多種通信算法來提高DNN模型的訓練效率。

在優化神經網絡推斷延遲方面，文獻［10］提出了一種BranchyNet 分支網絡結構，在普通DNN 模型中間添加多個分支網絡模型并部署早期退出點，當系統對推斷任務有把握時，可將任務在模型中間添加的分支中退出，不必使樣本經歷DNN 模型的所有層數，從而減少推斷延遲；文獻［11］利用DNN 模型中卷積層和全連接層廣義矩陣乘積操作的特性，將DNN 模型中這兩部分計算需求劃分為可以并行執行的片段，并部署到多個移動設備上，使用并行計算的方法來減少推斷過程中的延遲；文獻［12］研究了本地與邊緣服務器協同進行DNN 推斷的場景，提出了Edgent 終端-邊緣協同推理框架，將DNN 模型劃分為兩個部分：將資源需求大的部分部署在邊緣服務器上，而資源需求小的模型部分則部署在本地終端設備上；文獻［13］提出了Neurosurgeon 系統，研究了計算機視覺、語音等多種DNN架構的計算和數據特性，設計了DNN模型在移動設備與云服務器上共同部署時的分區方案。對邊緣計算場景中的深度學習推斷任務，有效的任務調度算法也可以提高模型推理性能，文獻［14］中將DNN 模型分別部署在網絡邊緣的網關與遠程云服務器上，通過為深度學習任務設計了一種新的任務卸載策略來提高推斷性能。

此外，還有研究關注減少DNN 模型的計算工作量。文獻［15］中通過剪接、訓練量化和哈夫曼編碼三階段對DNN 模型進行深度壓縮，在不影響DNN 模型精度的前提下，降低了DNN 模型的存儲需求；文獻［16］針對在資源有限的嵌入式設備中進行卷積神經網絡計算所需內存空間和資源過大的問題，提出了結合網絡權重裁剪及面向嵌入式平臺的動態定點量化方法，有效地壓縮了神經網絡模型并降低了計算消耗。

在邊緣計算場景下進行深度學習推斷任務，需要考慮DNN 模型計算特性以及邊緣節點的網絡狀況和計算能力，因此本文綜合考慮這兩點提出分支神經網絡在邊緣計算場景下的分布式部署問題，通過選擇最優部署方案以及優化推斷結果的傳輸來減少推斷任務的延遲。

2 部署模型與問題定義

在邊緣計算場景下部署分支DNN 模型，首先需要在云服務器上完成模型的訓練過程，這個過程是延遲容忍的，本文重點關注模型進行任務推斷的過程。DNN 的結構是層與層之間的有序序列，每一層接收到上一層輸出數據并處理，然后傳輸至下一層。利用這個特性可將DNN 構造為具有多個分支的DNN 模型，每一個分支都由具體的神經網絡層組成，多個分支又共同組成一個完整的DNN 模型。邊緣計算場景中的邊緣計算節點由多種計算性能不同的設備組成，這些設備數量眾多，相互獨立，分散在用戶周圍［17］。單獨的邊緣計算節點只能運行精度不高的簡單模型，自然想到將帶有分支的DNN模型分布式部署到多個邊緣計算節點上，由這些節點共同完成模型的推斷過程。因為各分支有著不同的網絡層結構，這會導致各分支對部署節點的計算資源要求不同，即同一模型部署到不同節點上會導致不同的運行延遲；又考慮到不同邊緣計算節點之間有著不同的網絡狀況，因此分支神經網絡的分布式部署問題需要綜合考慮到節點計算能力、分支模型結構以及節點之間的數據傳輸，不同的部署方式會使得推斷樣本經歷不同分支出口點、DNN 層數，即會導致精度和運行時的延遲不同。因此，需要為給定的DNN 分支模型結構選擇最佳的邊緣計算節點部署。同時數據源到不同邊緣計算節點的距離、網絡狀況也是影響推斷任務效果的因素。因此，問題的研究可以分為兩個階段：第一階段是為訓練好的DNN 分支模型選擇合適的邊緣節點部署，目標是使模型運行時的總延遲最?。坏诙A段是為不同的數據源選擇滿足其延時要求的邊緣計算節點退出推斷結果，并返回數據源。

在邊緣計算場景中，給定邊緣計算節點集合E={e1，e2，…，ei，…，em}以及有n 個分支的DNN 模型集合D={d1，d2，…，dz，…，dn}，其中dz表示第z 個分支，且這n 個模型分支有運行順序的要求；fij表示分支模型i 和j 部分的運行順序；mij表示邊緣節點i與j之間延遲；cij表示將di部署在ej上運行時的延遲；xij表示將第i個模型部分部署到第j個節點上。

問題1 分支神經網絡的分布式部署問題。給定邊緣計算節點集合E 與DNN 分支模型集合D，要求確定一個部署方案，使得在該部署方案下，每一個分支模型都部署到一個邊緣計算節點上，使DNN模型運行時所需總延遲最少。

定理1分支神經網絡的分布式部署問題是NP-難問題。

證明 首先介紹二次分配問題（Quadratic Assignment Problem，QAP）。QAP 可描述為：給定n 個設備和n 個地點，三個n×n 矩陣F=(fij)n*n，D=(dij)n*n與C=(cij)n*n，其中，fij表示設備i與j之間的流量，dij表示地點i與j之間距離，cij表示設備i部署在位置j的花費，fij與dij之間的乘積為通信費用，要求給每個設備分配一個位置，并使設施之間的通信費用與設施到地點上的部署費用之和最小。

其中p(i)表示設施i被分配的地點。

在分支神經網絡的分布式部署問題中，需要將n 個模型分配到m 個節點中的n個節點上（n ≤m），表示為問題規模n×m，而在QAP 中，是將n個設備分配到總數為n的節點上，問題規模為n×n。為了解決規模為n×m 的部署問題，至少需要解決一個規模為n×n的QAP。可以構造m-n個虛擬分支模型，此時部署問題變為規模為m×m 的QAP，再將m 個設備分配到m 個位置上；或是將m 個可用節點位置分為n 組，再將n個設備分配到n 個節點上，此時部署問題變為規模為n×n 的QAP。因此分支神經網絡的分布式部署問題至少與n×n 規模的QAP 一樣難。已知QAP 已經被證明為NP-難問題［18］，因此分支神經網絡的分布式部署問題是NP-難問題。

3 模型部署算法設計

3.1 基于分支定界思想的部署算法

本文基于分支定界思想設計了分布式神經網絡模型的部署算法。DBB 采用單賦值策略，在每一個步驟選擇一個未分配的模型分配到一個空閑的位置。每次分配都會計算當前已分配問題的下界，若當前下界大于已知的最優解下界，則表明對當前解分支繼續探索不會得到更好的解下界，則將上一次分配的位置移除，為當前模型分配其他空閑位置；若當前計算下界小于已知最優解下界，算法則會繼續采用單賦值策略繼續為當前解分配其他的對象。在為模型分配節點過程中，算法為每個節點定義節點性能：每個邊緣節點到其相鄰節點的延遲與當前模型部署延遲之和越小，則節點越有可能被部署，以此提升下一次分配得到更好下界的可能性。若模型已被全部分配至節點上，計算此時下界，若小于已知最優解下界，則記錄當前解并更新下界。此時算法再通過回溯至解空間樹上一層，為已分配模型選擇其他節點部署來尋找下一個可行解。

算法1 DBB。

輸入 DNN 模型集合D 以及邊緣計算節點集合E，代表n 個分支模型分別部署在m 個邊緣計算節點上的n×m 延遲矩陣C，邊緣計算節點之間通信的延遲矩陣M，記錄已部署的模型與設施集合為I與J，模型ik不允許被放置的節點集合記為P(ik)，C*為初始下界。

輸出 部署模型對應的節點序列。

1） C*=∞，i1=d1

2） for j ←1to m：

3） 集合I ←i1，集合J ←j1

4） for k ←1 to n-1

calculate B

if B ≥C*

go to 6）

else if B的值未改變

go to 5）

else ik+1=dk+1

replace I by I ∪{ik+1}，J by J ∪{jk+1}

此時C1即完整分配的花費

if C1＜C*，C*=C1，存儲已分配對(in，jm)，k=n

else k=n

6） 將ik與jk分別從I與J中移除

7） P(ik)=P(ik)∪{jk}

calculate B

8） if B ≥C*，then go to 9）

else 分配ik到位置t，t ?J ∪P(ik)

Jk=t，replace I byI ∪{ik}，J by J ∪{jk}

go to 4）

9） 此時ik-1與jk-1從I與J中移除

replace p(ik-1)by p(ik-1)∪jk-1，k=k-1

else 得到最優解(in，jm)

通過分析，該算法復雜度主要體現在計算問題每一階段的下界部分，下界的定義方法會影響到算法的搜索效率。當問題規模n×n 中n 不超過20 時，可以很快得到問題最優解。而問題所考慮的有n個分支的神經網絡模型中，n的規模不會很大，這也是未采用啟發式方法，而使用分支定界思想設計部署算法的原因。算法中邊界定義如下：假定模型i被放置到位置j，計算當前解的下界B=C1+C2+C3。

其中：C1表示已分配模型的延遲成本，C2表示已分配與未分配模型之間傳輸的延遲成本，C3是未分配位置的模型的延遲成本。對本文問題來說，C3的計算策略是將未分配計算節點與其余未分配節點延遲按升序排列，再將需要分配的模型部分依次放置上去。

3.2 選擇節點退出算法

部署模型任務完成之后，得到邊緣節點上運行分支神經網絡模型的最小延遲部署方案。而在推斷任務的實際情況中，還需考慮數據源到邊緣節點之間的距離、網絡狀況。推斷樣本經歷不同的邊緣節點會導致結果延遲與精度的改變。邊緣計算應用具有軟實時特征，用戶請求需要在一定的期限內返回［19］，且推斷結果的精度同樣影響用戶的體驗質量。為給推斷任務選擇合適的出口點返回推斷結果，本文設計了選擇節點退出算法。對給定延遲要求的推斷任務，從已部署的邊緣節點集合D 中選出目標節點d 返回推斷結果，在保證推斷滿足延遲要求情況下，使推斷樣本經歷更多的邊緣節點，最終為數據源返回符合延遲要求且保證精度的推斷結果。

如圖2 中，圖中央分布的是邊緣計算節點，標有數字的是已部署神經網絡模型的節點。當數據源1 與2 有任務需推斷時，首先將數據發送至部署了神經網絡模型第一層的邊緣節點1，隨后為數據源1 選擇符合任務要求的邊緣節點2 返回推斷結果，為數據源2選擇邊緣節點5返回推斷結果。

圖2 推斷任務運行場景Fig.2 Running scenario of inference task

算法2 SNE算法。

輸入 已部署的DNN 模型網絡拓撲；需推斷任務的延遲要求latency；數據源距離第一個邊緣節點延遲B1；第i 個邊緣節點距數據源延遲Bi；任務退出點N；預測延遲f()；推斷任務從第1 個到第i個邊緣計算節點上推斷所用延遲

輸出 符合任務t延遲要求的N。

1） For k ←1 to n

2） ELk←f(ELk)

3） For i ←1 to n

return i，store i to set I

5） return N=max I

6） else return null

4 實驗結果與分析

4.1 實驗環境

本文使用NS2 網絡模擬器仿真邊緣計算的網絡場景，將基于邊緣計算的分支網絡部署模型與基于云計算的DNN 模型推斷進行對比。在深度學習框架BranchyNet下訓練了一個具有多個分支的DNN 模型，用于Cifar-10 數據集上的圖像分類任務。在NS2 網絡模擬器中仿真了以數據源、邊緣節點與云服務器為主的網絡分布場景。圖3 說明了具有5 個分支、6個出口點的分支神經網絡模型B-AlexNet。為了便于說明，僅繪制卷積層和全連接層。

圖3 分支神經網絡模型主要結構Fig.3 Main structure of branchy neural network model

實驗中為設置異構的邊緣節點網絡環境，采取將JetsonTX1、JetsonTX2、JetsonTK1 和JetsonNaNo 四種不同的邊緣設備在每次生成網絡拓撲時隨機分配到邊緣節點上的方法。參考四種設備不同的計算性能參數，使用文獻［20］中的Paleo 框架預測了模型各分支在邊緣節點上的模型運行延遲，如表1。

4.2 實驗結果

首先將本文提出方法與現有在云端部署神經網絡模型的方法進行對比。將訓練好的分支神經網絡模型分別部署在邊緣節點上和云服務器上。圖4 實驗中基于邊緣計算的方法中延遲取的是模擬10 次不同網絡分布后的延遲平均值，節點之間帶寬設置為1 Mb/s。實驗結果表明，兩種方法中，當數據源的任務經模型推斷后從同一出口點退出時，即此時兩種方式對任務推斷的精度相同，基于邊緣計算的神經網絡模型推斷所用延遲比云端部署方式更短。且綜合不同的推斷精度考慮，本文方法所用推斷延遲較云端部署方法平均降低了36%。

下面基于圖5 的網絡拓撲，分析邊緣節點上神經網絡模型對不同地理位置的數據源進行推斷任務的性能。首先由DBB 從隨機生成的邊緣節點分布集合中選擇了節點1、2、3、4、5、6部署分支神經網絡模型。

表1 分支模型在邊緣設備上的運行延遲 單位：msTab.1 Branchy model running delay on edge devices unit：ms

圖4 本文方法與云服務器方法的推斷延遲對比Fig.4 Inference delay comparison of the proposed method and cloud server method

圖5 網絡模擬狀態Fig.5 Simulation state of the network

實驗結果如圖6 所示，可發現當推斷樣本返回的推斷精度低時，即此時樣本在部署早期分支退出點的節點退出（如節點1、2、3），此時數據源節點8距離退出點更近，因此獲得了更好的延遲效果；隨著推斷樣本精度的提升，邊緣節點在分支神經網絡模型后期的退出點為數據源返回推斷結果，此時后期退出點距離數據源節點9更近，因此節點9的推斷任務取得比節點8更好的延遲效果。

圖6 邊緣場景下不同數據源任務推斷延遲對比Fig.6 Task inference delay comparison of different data sources in edge computing scenario

實驗中還發現推斷任務的運行延遲受到網絡帶寬的影響，因此在實驗中考慮設置網絡帶寬為500 kb/s，此時的推斷任務運行情況如表2 所示，精度為-1 時表示當前推斷無法滿足任務延遲要求。當推斷任務延遲要求為50 ms 時，云服務器與邊緣場景下的SNE 算法都無法滿足任務的延遲需求；隨著推斷任務延遲要求降低，SNE 算法通過選擇早期的分支模型進行任務推斷，并輸出中等精度的推斷結果；當任務延遲要求達到350 ms 時，兩種方式都可以滿足推斷任務延遲要求，為數據源返回最高精度分支模型的推斷結果。

表2 網絡受限情況下邊緣與云場景下任務推斷精度對比Tab.2 Comparison of inference accuracy in edge and cloud scenarios with limited network

5 結語

針對現有基于云的深度學習任務推斷延遲過高問題，本文提出在邊緣計算場景下部署分支神經網絡模型以減小推斷延遲，設計了基于分支定界思想的部署算法（DBB）來為給定的DNN 模型選擇合適的邊緣計算節點部署，降低了推斷任務所需要的延遲；同時設計了選擇節點退出算法（SNE）為不同延遲要求的推斷任務滿足選擇合適節點返回推斷結果。實驗結果顯示，與傳統在云端部署神經網絡模型的方法相比，本文提出的邊緣計算場景下部署分支神經網絡模型平均降低了36%的推斷延遲。