一種面向多物聯代理在線應用的彈性資源調度算法

繆巍巍，王傳君，曾 锃，李世豪，張 震，張明軒

(國網江蘇省電力公司信息通信分公司， 南京 210024)

如今，新興的計算密集型應用往往需要超過單一設備所能提供的計算資源，因此許多已有的系統[1-4]將計算密集型應用卸載到云端或者附近的高性能計算服務器來加快處理速度。比如，MCDNN[1]將基于深度神經網絡的視頻處理任務卸載到云端，Odessa[2]選擇附近的高性能計算服務器作為額外的計算資源去從實時視頻中識別對象，LEO[3]利用芯片數字信號處理器、GPU并協同云服務器來運行推斷算法。盡管這些工作加快了處理速度并降低了時延，但在一些網絡通信資源匱乏的場景中，云服務器和高性能計算服務器帶來的豐富資源卻不是總能輕易獲得的。在電力物聯網[5-6]場景下，不同的邊緣物聯代理產生類型和結構均不同的數據，運行不同的應用，并且組成應用的任務之間可能存在依賴關系，如何將這些任務調度到合適的物聯管理平臺[7-9]的數據處理模塊來處理成為一個頗具挑戰性的問題。

本文試圖設計一個面向多邊緣物聯代理在線應用的調度框架。該框架無需通信基礎設施的輔助，且數據處理應用是由多個存在依賴關系的任務構成的。在一個應用請求在邊緣物聯代理上被提出前，物聯管理平臺的數據處理模塊上可能已有不少不同種類的計算密集型應用在占用計算資源、消耗能量，留給應用處理的資源是隨著時間不斷改變的，如何與其他已有應用更好地計算資源是值得考慮的。而在邊緣物聯代理能量有限的情況下，負載均衡的引入能使得整個系統中的能量得到更充分地利用，在這里，負載均衡定義為單個應用的處理給每個物聯代理帶來能量消耗占剩余能量比重的均衡程度。

在這樣的情形下，在線對應用進行調度決策顯然能夠更好地適應復雜的資源環境。針對與已有應用共享資源的問題，在應用處理請求到來時，物聯管理平臺的數據處理模塊可自定義應用允許占用計算資源的比重。此外，由于物聯管理平臺的數據處理模塊可能在地域上是分布的，2個數據處理模塊之間的數據傳輸速度較慢，連接可能也不穩定，因此多個應用同時在物聯管理平臺的某個數據處理模塊上處理時容易因為爭搶傳輸連接而彼此影響。這里采取一個保守的策略：在單個應用的調度決策中假設一個物聯管理平臺數據處理模塊上同一時間至多只能存在2條連接，一條用于發送數據，一條用于接收數據；這樣能減少多應用因爭搶傳輸連接對彼此的影響，使得更多的應用順利處理，增強了應用處理用時的可預測性，也更貼近客觀實際。為解決問題提出了一個兩階段的啟發式算法：每當一個應用處理請求在一個物聯代理上被提出，首先以優化處理用時為目標進行一次初始調度，然后以實現負載均衡為目標進行多輪的調整調度。最后，進行了大量的仿真實驗，充分驗證了所設計算法能夠在較短的時間內達到接近最優的表現。

1 相關工作

由存在依賴關系的任務構成的應用(將任務視作定點，依賴關系視作有向邊，從而構成有向無環圖，因此本文簡稱為DAG式應用)在多個處理器上的調度，已有不少研究[10-12]。比如，SUNDAR等[10]研究了單個DAG式應用在一個一般的云計算系統上的卸載調度。這個云計算系統包含一個遠程云服務器和一個異構的本地處理器網絡。文中描述了一個在不違背應用處理時限要求下的最小化能量開銷的優化問題，并提出了一個啟發式算法ITAGS來獲得一個有效的決策。ITAGS首先為應用的每個任務分配了一個任務處理時限，然后基于這個任務處理時限對每個任務的調度進行優化。ITAGS并不適合本文的場景，因為文獻[10]作了2個隱含假設，一個是應用任務分配到設備上后，獨占設備所有計算資源，這在真實場景中并不現實；另一個是在應用處理過程中，設備之間能以給定的速度穩定地通信。盡管文獻[10]研究的只是單個DAG式應用的調度，但在實際處理中，設備之間的通信速度必然不可能非常穩定。而當應用處理系統中有多個應用同時在進行處理時，無線傳輸資源的有限會導致應用之間因為爭搶傳輸連接而相互影響，傳輸速度更加難以預測。

F-MStorm[13]是一個基于反饋的在線分布式移動流處理系統。與當前主流的移動流處理系統MStorm[14]采用靜態的配置和調度不同，它根據流處理過程中來自各個移動設備的反饋，在配置層面動態調整每個移動設備上的處理器數目，在調度層面動態調整任務分配方案，在執行層面動態調整上游任務對下游任務的結果數據分配。從而系統可以快速適應變化的環境，始終保持高效的表現。雖然文獻[13]的應用場景和本文非常相似，但它關注的是流處理，和本文的DAG式應用處理不同。

文獻[15]關注的是DAG式應用在邊緣集群上的調度，并以優化應用處理時長和能量開銷為目標提出了2種基于任務復制的啟發式算法。文獻[15]假設處理器是同構的，且未將負載均衡考慮在內。

與文獻[15]類似，LIU等[16]同樣研究DAG式應用在邊緣服務器上的調度，并針對優化應用處理時長這個目標，提出了一種具有性能保證的近似算法。但是文獻[16]中的應用必須部署到有對應處理功能的邊緣服務器上。除此以外，由于它沒有將能量考慮進系統，因此相應地也沒有考慮負載均衡。

2 問題描述

2.1 應用模型

在應用模型中，每個電力物聯網應用有一個軟性的完成時刻限制Tmax，也就是說應用并非要嚴格在Tmax前完成，但超過這個時刻完成會受到懲罰，比如在電力調度應用中，希望調度盡可能快地完成，但并沒有一個嚴格的時間限制，因此使用懲罰函數的形式是比較合理的。定義懲罰函數：

F(T)=max{0，T-Tmax}

(1)

式中：T是應用實際完成的時刻。一個應用中的任務之間的依賴關系可以用一個有向無環圖來刻畫，其中每個結點Xi表示一個任務i，它的計算量用Wi來表示，每條有向邊(Xi，Xj)表示任務Xi需要傳輸結果給任務Xj，數據規模為di，j，因此Xj的計算依賴于Xi的計算結果。

圖1(a)展示了一個應用的任務圖。在一個給定的任務圖中，稱沒有父親結點的任務為入口任務(即圖中的X1)，沒有孩子結點的任務為出口任務(即圖中的X5和X6)。為方便起見，對于一個給定的DAG任務圖，首先對其標準化。

圖1 任務圖和標準化

插入2個計算量為0(即W=0)的虛擬任務。一個任務插在開頭代表應用請求的提出，由它引出有向邊指向原DAG任務圖中所有的入口任務，并且有向邊上需要傳輸的數據規模為0。另一個任務則插在結尾用來匯總所有的結果數據，由原DAG圖中所有的出口任務引出有向邊指向它，有向邊上傳輸的數據就是需要匯總的結果數據。顯然，這2個任務實際分別成了新任務圖唯一的入口任務和出口任務，在調度中，應用可能規定了入口任務和出口任務必須分配到的模塊。用nentry來表示入口任務的編號，用nexit來表示出口任務的編號。顯然這樣的處理不失一般性，因為它并沒有改變應用原有的結構。圖1(b)展示了對圖1(a)中的任務圖進行標準化的結果，X0和X7是被插入的2個虛擬任務。

假設一個應用的任務總數為M(M≥3)，其中包含2個虛擬任務。任務編號為0，1，2，…，(M-1)。

2.2 資源模型

考慮一個物聯管理平臺有多個數據處理模塊構成，這些模塊可能有不同的處理速度，每個模塊在同一時間只能處理一個任務，與此同時，其他分配到這個模塊上的任務在處理隊列中等待。

2.3 計算模型

(2)

用d(i)來表示任務Xi所在數據處理模塊的編號，

d(i)∈{0，1，2，…，(N-1)}

(3)

(4)

(5)

(6)

顯然，入口任務Xnentry準備好計算的時刻就是應用處理請求被提出的時刻，也就是：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

其中，

(15)

此外，任務Xi向它的直接后繼任務傳輸結果數據總的開始和完成時間與它具體向其中每個直接后繼任務傳輸結果數據的開始和完成時間有如下關系：

(16)

(17)

(18)

(19)

式(18)是顯然的，式(19)表明如果Xi的另一個直接前驅Xl在Xk之前請求向Xi傳輸結果數據，那么Xk就必須等到Xl完成這次傳輸后才能有機會開始傳輸。

不難算出在應用處理在數據處理模塊z上的能量消耗Ez：計算消耗的能量，發送數據消耗的能量，和接收數據消耗的能量。用T(z)表示分配在模塊z上的任務編號組成的集合，那么，

(20)

應用處理帶給模塊z的能量消耗Ez占剩余能量的比例為

(21)

并且

ηz≤1

(22)

(23)

(24)

最后，應用的完成時刻

(25)

2.4 問題描述

(26)

基于這個定義，為了保證應用的順利處理，如果有2個任務被分配到了同一個模塊上，并且它們之間存在依賴關系，那么被依賴方應當在依賴方之前得到調度，即，

(27)

(28)

(29)

也就是說，模塊d(i)必須等到本應用所有在任務Xi之前就分配到它上面的任務完成結果數據的傳輸時，才能開始傳輸任務Xi的結果數據。

至此，可以總結該問題：在電力物聯網場景下，由多個物聯代理生成存在依賴關系的任務構成一個DAG式應用；每當一個應用處理請求被提出，我們要根據請求的完成時刻軟性限制、每個模塊允許用來處理該應用的CPU資源占比，每個模塊的剩余能量、發送/處理速度、功率等信息，以及應用的結構和其他相關信息，在線確定如下未知量：

1) 任務調度順序：

2) 任務分配決策：

d(i)，i∈{0，1，2，…，(M-1)}

其中，入口任務和出口任務必須被分配在給定的模塊上，也就是

d(nentry)=zsubmit

(30)

d(nexit)=zsubmit

(31)

3) 任務向直接后繼任務發送結果數據的順序:

?j，k∈S(i),j≠k

來最小化目標變量

式中：α和β是比例因子，用來調整“滿足完成時刻限制”和“負載均衡”對優化目標的重要性。通過合理的設置比例因子，能夠實現兩者的權衡。

總的來說，這個問題可以被描述成一個整數規劃問題：

通過靈活地設置比例因子α和β的值，對這個問題的解決方案可以在各種情況下發揮作用。例如，當應用是時延敏感型或無能量約束情況下，可以將α/β調得較大，以強調目標變量中“滿足規定完成時刻限制”的重要性。

3 算法設計

從問題描述中，不難發現，要在線確定2個順序：任務調度順序和任務向直接后繼發送結果數據的順序，以及一個分配：任務分配，來優化一個包含“任務完成時刻”和“負載均衡”2個要素的目標函數。如果要以窮舉所有情形的方式來搜索最優解，僅僅任務分配就是O(NM)級別的，這在應用包含任務數多、模塊數多的情況下，是難以接受的。因此，提出一種兩階段啟發式算法：當一個應用處理請求被提出，首先以優化處理用時為目標進行一次初始調度，然后以實現負載均衡為目標進行多輪調整調度。

3.1 初始調度階段

3.1.1決定任務調度順序和任務發送結果數據的順序

(32)

(33)

TLAS顯然能反映一個任務的緊急程度，在算法中，使用任務的TLAS作為任務調度的優先級度量，TLAS越小，優先級越高。

具體計算每個任務TLAC和TLAS的方法如下：假設任務Xi所有直接后繼任務的TLAC和TLAS全部已經計算完成。在任務Xi向它的直接后繼任務傳輸結果數據時，直接后繼任務的TLAS是直接后繼任務最晚允許開始計算的時刻，反映了直接后繼任務對于來自Xi的結果數據的渴求程度。特別是考慮到實際情況中，來自一個任務的結果數據往往規模相似，與一個模塊建立的連接速度往往大小相當，傳輸時間對決定傳輸順序的影響并不是很大。因此根據直接后繼任務的TLAS的大小來確定傳輸順序可能是一種比較快捷而穩妥的選擇，將任務Xi的直接后繼任務根據TLAS從小到大排序，這個順序就是算法決定的任務Xi向直接后繼任務傳輸結果數據的順序。

(34)

將這|S(i)|個二元組按照傳輸順序(也就是TLAS從小到大的順序)排列，得到如下序列：

(35)

(36)

按照上面給出的方法算出所有任務的TLAS，從小到大排列，對應的任務順序就是算法給出的任務調度順序。根據上面對于TLAS的計算方法，可以看出，這樣的一個排序是任務關于依賴關系的一個拓撲排序，也就是說，如果按照這個順序調度任務，每個任務必然在它的直接后繼任務之前得到調度。

3.1.2任務分配

算法1初始調度階段算法

輸入：應用任務圖G，模塊相關信息，應用請求提出的時刻Tsubmit和模塊zsubmit。

輸出：任務分配方案。

a) 計算G中任務的逆拓撲排序S

b) 按S依次計算G中每個任務的TLAS

c) ForG中的每個任務

d) 按直接后繼任務的升序傳輸結果數據

e) 優先級隊列PQ←所有任務根據TLAS的升序排序結果

f) 從PQ中按序取出每個任務Xi，依次進行g)～j)的操作

g)If是入口或出口任務 Then

h)d(i)←zsubmit

i) Else

3.2 調整調度階段

在這一階段，任務被重新分配來實現負載均衡，但是并不改變任務的調度順序和任務向直接后繼任務傳輸結果數據的順序。調整調度階段分若干輪，在每一輪按照下述方式來調整。

根據當前的分配策略計算出應用帶給每個模塊能量消耗占模塊剩余能量的比重η，按照η值由大到小的順序，逐個考慮模塊上的當前分配任務的重新分配。重新分配k個模塊上的任務，對這些任務逐個嘗試重新分配到其他模塊上來減小目標變量的取值，具體而言，重新分配到使得目標變量取值降低最多的模塊上，如果重新分配無法降低目標變量取值，就放棄這次嘗試。這里不考慮入口任務和出口任務的重新分配。假設分配在η值前k大的模塊上的任務總共有s個，那么一輪共嘗試約s(N-1)次重新分配。不斷重復每一輪的調整調度，直到連續若干輪目標值的優化幅度都很小。k值的選取和模塊數N有關，較大的N應當對應較大的k。選取k=[N/3]，這樣每一輪調整的嘗試次數比較合理，既不會太多，并且在一定輪數內就能達到不錯的優化效果。

算法2調整調度階段算法

輸入：算法1得到任務分配方案，預先設定的k值。

輸出：調整完的任務分配方案。

a)O←所有模塊根據η的降序排序結果

b) 對O中的前k個模塊，依次進行c)～e)的操作

c) For 模塊上的每個任務Xi

d) IfXi不是入口或出口任務Then

e)d(i)←使得目標值降低最多的模塊

f) 重復步驟b)～e)，直到連續若干輪優化幅度都很小

3.3 算法分析

窮舉算法雖然可以得到理論上的最優調度決策，但是在應用包含任務數和模塊數較大的情況下對應的高昂開銷是無法接受的。這個兩階段的啟發式算法能夠在多項式時間內獲取一個較好的調度決策，可行性高。下面簡要分析一下這個啟發式算法的時間復雜度：

在初始調度階段，首先要計算每一個任務的TLAS，其中涉及對直接后繼任務根據TLAS進行排序，時間復雜度是O(MlogM)，總共有M個任務，因此總的時間復雜度是O(M2logM)。然后要對所有任務根據TLAS進行排序，時間復雜度是O(MlogM)。這時，分配每一個任務的時間復雜度是O(MN)，總的時間復雜度是O(M2N)。綜合來看，初始調度階段的時間復雜度是O(M2(logM+N))。

在調整調度階段，對于每一輪調整，首先要對所有模塊根據η值進行排序，時間復雜度是O(NlogN)，然后考慮重新分配任務，次數是O(MN)，每一次重新分配需要計算一次目標值，時間復雜度是O(M2+N)，因此每一輪調整調度的時間復雜度是O(M3N+MN2)。將以上分析結合起來，這個啟發式算法的時間復雜度是O(M3N+MN2)。

4 實驗

通過大量的仿真實驗來評估所提算法的性能。使用隨機生成的任務圖和實際的參數值來作為實驗數據，在一臺搭載了i9-9880H CPU、16GB內存的筆記本上進行仿真。其中任務圖的隨機性體現在：結構隨機，每個子任務計算量隨機，子任務間傳輸結果數據規模隨機。表1中列出了數據處理模塊的參數，表2中列出了隨機任務圖的參數。

表1 數據處理模塊參數

表2 隨機任務圖參數

首先通過在一個隨機生成的任務圖以及其他給定的參數上測試窮舉算法的表現，來展示通過調整比例因子α和β的比值，本文提出的優化目標，能夠在對“滿足規定完成時刻限制”和“負載均衡”重要性的不同期望下，均給出合理的調度結果。然后，通過調整比例因子α和β的比值、模塊情況、任務圖規模，分別計算窮舉算法、不包含調整調度階段的啟發式算法和完整版本的啟發式算法對應的優化目標值，來展示在不同的情況下，啟發式算法的各個階段均發揮了期望的作用，在優化目標變量上均能給出接近窮舉算法的表現。

仿真參數根據調查和經驗設定，可能與實際情況有一些偏差，但對目標驗證的影響程度并不是很大。比如在數據處理模塊參數(表1)中，盡管電池容量設定得非常小，但是由于考察的是耗能量占剩余能量比重的負載均衡，這樣的設定不但不會影響結果的準確程度，反而使得結果更為直觀。

4.1 優化目標的合理性

隨機生成一個任務數M=12的任務圖，并設置模塊數N=4。假設應用處理請求在t=0.2 s時刻被提出，其入口和出口任務需要在模塊0上完成，此時每個設備的剩余能量占比和允許應用使用的CPU資源占比見表3。

表3 應用處理請求提出時的一些額外參數(N=4)

首先設置一個比較寬松的完成時刻限制Tmax=3.5s，并讓α=1，β從1變化到100。仿真結果表明，窮舉算法得到的調度方案對應的完成時刻、各個模塊上的應用處理耗能量占剩余能量比重、負載均衡因子如表4所示。

由此可以發現，在完成時刻限制比較寬松的情況下，通過優化本文提出的目標，幾乎總能得到一個在應用處理完成時刻不超過Tmax情況下的將負載均衡做到最好的調度方案。

表4 Tmax=3.5 s時，不同α/β取值下的仿真結果

再設置一個比較緊迫的完成時刻限制Tmax=2.5 s，并令α=1，β取從1到50的一系列值，仿真結果如表5所示。

表5 Tmax=2.5 s時，不同α/β取值下的仿真結果

從結果中可以發現，在完成時刻限制比較緊迫的情況下，當β值比較小時，優化目標中“滿足規定完成時刻限制”的重要性比較大，因此得到的調度方案是一個在應用處理完成時刻不超過Tmax情況下的將負載均衡做到最好的調度方案。隨著β值逐漸增大，“負載均衡”在優化目標中的地位不斷提高，得到的調度方案中的應用完成時刻開始突破Tmax，負載均衡也隨之改善。

以上結果顯示，通過合理調整比例因子α和β的比值，本文提出的優化目標，能夠在對“滿足規定完成時刻限制”和“負載均衡”重要性的不同期望下，均給出合理的調度結果。

4.2 算法性能

對于一組給定的模塊信息、任務規模M、任務完成時限Tmax、α和β的比值數據，根據任務規模M隨機生成10個不同的任務圖，分別得到優化目標值后計算它們的平均值。

假設應用處理請求在t=0.2 s時刻被提出，其入口和出口任務需要在模塊0上完成。N=4時每個設備的剩余能量占比和允許應用使用的CPU資源占比見表3；N=5時每個設備的剩余能量占比和允許應用使用的CPU資源占比見表6。

窮舉算法、不包含調整調度階段的啟發式算法和完整啟發式算法對應的仿真結果如表7～10所示。

表6 應用處理請求提出時的一些額外參數(N=5)

表7 M=7，N=4，α=1，Tmax=1.3 s時的仿真結果

表8 M=9，N=5，α=1，Tmax=1.5 s時的仿真結果

表9 M=12，N=4，α=1，Tmax=2.5 s時的仿真結果

表10 M=13，N=5，α=1，Tmax=2.5 s時的仿真結果

以上仿真結果說明，啟發式算法在性能上的表現與窮舉算法是比較接近的，多數情形下，這兩種算法之間的差距在10%～35%。不包含調整調度階段的啟發式算法在增加了調整調度階段后，算法性能也有顯著提升。在實驗過程中發現，當M=13，N=5時，窮舉算法在實驗計算機上耗時已達到50 s，繼續增大N=4和任務圖的規模，耗時呈指數級別增長，而啟發式算法的耗時則一直控制在0.001 s以內。

5 結論

提出了一個兼顧應用完成時間和負載均衡的聯合優化問題，設計了一個兩階段的啟發式算法。仿真實驗結果表明：該算法能夠在較短的時間內達到接近最優。