劉 敏 彭麗麗 蔡園園 王興陽

江蘇電力信息技術(shù)有限公司

0 引言

隨著邊緣計算的發(fā)展，網(wǎng)絡邊緣產(chǎn)生的數(shù)據(jù)呈指數(shù)級增長，據(jù)預測，在不久的將來，邊緣集群數(shù)據(jù)的產(chǎn)生速度將超過當今互聯(lián)網(wǎng)的容量。隨著邊緣集群數(shù)量的增加和機器學習的快速發(fā)展，機器學習作業(yè)成為邊緣系統(tǒng)的主要工作負載。

每個邊緣集群有限的資源使得機器學習作業(yè)的運行具有很大的挑戰(zhàn)。一個作業(yè)的完成通常取決于最慢的任務，即慢任務。避免慢任務的傳統(tǒng)方法是將任務卸載到遠程云，然而這會導致較大的廣域網(wǎng)絡延遲和較大的資金成本。另一個有潛力的替代方案是將任務從過載的邊緣復制到空閑的邊緣。當任何一個副本完成時，該任務就完成了。也就是說，任務的完成取決于其最快的副本，這可能會減少任務排隊和計算時延。但是在邊緣集群中實現(xiàn)高效的任務復制有以下幾個挑戰(zhàn)。

首先，要選擇最佳副本位置，需要提前知道在邊緣集群中運行的任務的計算時延，在做出復制決策并完成副本之前，無法知道此類信息。其次，邊緣集群之間的網(wǎng)絡帶寬通常是時變的，這也導致了不確定的傳輸時延。這兩個相互交織的挑戰(zhàn)進一步使任務的完成變得不可預測。因此，設計一種能夠持續(xù)適應這種動態(tài)和不確定環(huán)境的高效復制算法并不容易。

現(xiàn)有的復制方法無法應對這些挑戰(zhàn)。基于檢測的算法需要花費大量時間和成本來監(jiān)控和識別掉隊者。通常，這樣的開銷是巨大的，因此基于檢測的策略有其固有的缺陷。基于克隆的算法提前復制任務的一定數(shù)量的副本，并將其卸載到相應的邊緣。但是，在執(zhí)行算法之前，時延總是未知的，因此無法找到卸載這些副本的最佳邊緣。

文中首先建立了基于多臂賭博機的邊緣系統(tǒng)的任務復制問題的模型，并給出了相應的公式。其次，設計一種邊緣環(huán)境中基于復制的高效任務加速機制，即TRAN，通過權(quán)衡探索和利用來最小化任務級regret。在TRAN中，將由多個邊緣集群組成的系統(tǒng)視為一個多臂賭博機，并將每個邊緣集群視為多臂賭博機中的一個手臂。對于過載邊緣上的任務，作出在線決策，以決定為任務選擇哪些手臂，即執(zhí)行任務副本的目標邊緣群集，證明了所提出的TRAN機制的regret是次線性的。

1 問題分析

一個機器學習作業(yè)通常包含多個任務，一個任務由一個三元組構(gòu)成，分別是該任務的輸入數(shù)據(jù)量、輸出數(shù)據(jù)量以及任務的類型。由任務類型和輸入數(shù)據(jù)量可以得出該任務的計算量。從而，任務復制時延模型可以定義為以下三部分：（1）副本從一個邊緣到目標邊緣的傳輸時延；（2）副本在目標邊緣上的計算時延；（3）從目標邊緣向原邊緣傳回結(jié)果的時延。時延模型的第一部分取決于其輸入數(shù)據(jù)大小和帶寬。第二部分取決于任務所需的計算量和邊緣的計算能力。第三部分則取決于計算結(jié)果的大小和帶寬。如圖1是基于復制的任務加速機制的基本原理。其中綠色作業(yè)的任務3經(jīng)過決策之后，選擇了邊緣4和邊緣7作為目標邊緣集群來執(zhí)行副本。

圖1 基于復制的任務加速機制基本工作原理

由于執(zhí)行任務時網(wǎng)絡帶寬和邊緣集群計算性能的不斷波動，無法在復制決策之前預測復制到不同邊緣的任務的完成延遲。而且，決策后的總延遲仍然是一個隨機量。每個任務的實際完成延遲只有在任務實際完成后才能知道。因此，任務完成延遲是未知分布的樣本。具體而言，在上述時延模型中，帶寬和邊緣計算能力滿足未知分布，隨時間波動，無法提前預測。因此，使用多臂賭博機模型來解決復制的隨機性問題。

基于任務復制和多臂賭博機，設計了一種邊緣環(huán)境中的高效任務加速機制，即TRAN，通過權(quán)衡探索和利用來最小化任務級regret。在TRAN中，將由多個邊緣集群組成的系統(tǒng)視為一個多臂賭博機，并將每個邊緣集群視為多臂賭博機中的一個手臂。對于過載邊緣上的任務，會在線作出決策，以決定為任務選擇哪些手臂，即執(zhí)行任務副本的目標邊緣群集。該算法的每次決策都為算法本身的學習提供了一次樣本，通過學習不斷完善的模型也就是每次在線決策的依據(jù)。隨后，證明了所提出的TRAN機制的regret是次線性的。

2 基于復制的任務加速算法思想

解決上述任務復制問題的主要挑戰(zhàn)來自兩個方面。第一個方面是估計機器學習任務的計算量。第二個方面是基于在線多臂賭博機的任務復制算法的設計。在這兩部分的算法設計中，基于復制的任務加速算法的體系結(jié)構(gòu)如圖2所示，描述了TRAN算法的體系結(jié)構(gòu)。計算量估計模塊根據(jù)任務數(shù)據(jù)量和任務類型估計任務的計算量。邊緣系統(tǒng)管理器模塊則根據(jù)歷史的系統(tǒng)狀況預估邊緣集群的計算能力和網(wǎng)絡帶寬。TRAN代理和調(diào)度器模塊根據(jù)邊緣系統(tǒng)管理器模塊的預判作出復制決策。

其中，任務計算量模塊的設計思想如下。若任務為機器學習推斷任務：直接根據(jù)模型結(jié)構(gòu)，統(tǒng)計計算過程中的原子操作數(shù)量，估計任務的總體計算量。若任務為機器學習訓練任務：若該訓練過程能夠直接通過閉式表達式獲取最優(yōu)模型參數(shù)向量，通過分析該等式可直接得到計算量與輸入數(shù)據(jù)量的關(guān)系。對于大部分需要通過迭代更新的訓練任務，一次迭代可表述為一個閉式表達式，因此根據(jù)輸入向量維度N，一次迭代的計算量也是能準確估算的。

TRAN代理（基于多臂賭博機的在線決策模塊）主要通過不斷在線決策，逐步學習整個邊緣系統(tǒng)的帶寬和計算性能的分布。再利用學到的分布，為系統(tǒng)的下一次復制決策提供依據(jù)。在算法運行的過程中，也設置了padding項來平衡探索和利用，以使整個邊緣系統(tǒng)所有作業(yè)的完成時延最小。

3 結(jié)束語

本文將多臂賭博機應用于任務復制問題，并對邊緣計算性能和鏈路帶寬的隨機性進行了描述，提出了一種邊緣計算環(huán)境中基于復制的任務加速機制?；趶椭频娜蝿占铀贆C制的核心在于用多臂賭博機刻畫計算時延和傳輸時延的波動性，設置padding項權(quán)衡探索和利用。