邊緣計(jì)算環(huán)境中基于復(fù)制的任務(wù)加速機(jī)制

劉 敏 彭麗麗 蔡園園 王興陽(yáng)

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

0 引言

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

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

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

現(xiàn)有的復(fù)制方法無(wú)法應(yīng)對(duì)這些挑戰(zhàn)?；跈z測(cè)的算法需要花費(fèi)大量時(shí)間和成本來(lái)監(jiān)控和識(shí)別掉隊(duì)者。通常，這樣的開(kāi)銷(xiāo)是巨大的，因此基于檢測(cè)的策略有其固有的缺陷?；诳寺〉乃惴ㄌ崆皬?fù)制任務(wù)的一定數(shù)量的副本，并將其卸載到相應(yīng)的邊緣。但是，在執(zhí)行算法之前，時(shí)延總是未知的，因此無(wú)法找到卸載這些副本的最佳邊緣。

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

1 問(wèn)題分析

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

圖1 基于復(fù)制的任務(wù)加速機(jī)制基本工作原理

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

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

2 基于復(fù)制的任務(wù)加速算法思想

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

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

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

3 結(jié)束語(yǔ)

本文將多臂賭博機(jī)應(yīng)用于任務(wù)復(fù)制問(wèn)題，并對(duì)邊緣計(jì)算性能和鏈路帶寬的隨機(jī)性進(jìn)行了描述，提出了一種邊緣計(jì)算環(huán)境中基于復(fù)制的任務(wù)加速機(jī)制?；趶?fù)制的任務(wù)加速機(jī)制的核心在于用多臂賭博機(jī)刻畫(huà)計(jì)算時(shí)延和傳輸時(shí)延的波動(dòng)性，設(shè)置padding項(xiàng)權(quán)衡探索和利用。