移動云計算任務(wù)交互圖的能效映射與調(diào)度

孫赫勇 文 勃 鄭 丹 周 強

1(中車青島四方機車車輛股份有限公司大連分公司 遼寧 大連 116000)2(中車青島四方機車車輛股份有限公司青島分公司 山東 青島 266000)3(中車青島四方機車車輛股份有限公司焦作分公司 河南 焦作 454150)4(北京交通大學軟件學院 北京 100044)

0 引 言

移動云計算可以將移動設(shè)備上的計算任務(wù)、數(shù)據(jù)處理及存儲卸載至云端資源上，從而降低移動設(shè)備對于計算資源的巨大需求，解決復雜性應用任務(wù)的執(zhí)行[1-2]。移動應用中的任務(wù)模塊通常具有相互關(guān)聯(lián)性，因此通常以任務(wù)交互圖TIG進行建模[3]。TIG中的任務(wù)需要在保持性能和能效的基礎(chǔ)上映射并調(diào)度至遠程云端資源上。映射即是通過匹配任務(wù)需求和資源能力將資源分配給任務(wù)，調(diào)度即是在所分配的資源上執(zhí)行任務(wù)的過程。每個TIG擁有多個頂點和有向邊，頂點代表包含需要執(zhí)行的指令集的任務(wù)，有向邊代表任務(wù)的映射資源間的數(shù)據(jù)流，代表通信代價。由于通信代價取決于任務(wù)間的數(shù)據(jù)流大小和傳輸帶寬，不同的任務(wù)-資源映射，其通信代價也是不同的。

由于每個資源上的處理器均可通過動態(tài)電壓/頻率調(diào)整DVFS技術(shù)運行在不同的離散頻率下[4]，頻率越高，完成時間越短，但其能耗也越高。因此，計算代價在不同的資源頻率分配下也是不同的，這取決于映射處理器的運行頻率。對于TIG而言，從開始節(jié)點至出口節(jié)點間的每條路徑的完成時間為計算代價與通信代價之和。擁有最大完成時間的路徑即為TIG的關(guān)鍵路徑。任務(wù)卸載至云端資源上執(zhí)行不能影響應用執(zhí)行的性能和能耗，這表明進行卸載應確保任務(wù)在期限內(nèi)完成，且能耗也得到降低。應用卸載問題的目標即是尋找最優(yōu)的任務(wù)-資源分配(即映射)與最優(yōu)資源頻率分配(即調(diào)度)，使得整個TIG不僅可以在全局期限內(nèi)完成，還可以使能耗達到最小化。

相關(guān)工作中，文獻[5]提出一種基于調(diào)度的整數(shù)線性規(guī)劃ILP算法，文獻[6]提出一種基于固定優(yōu)先級的任務(wù)調(diào)度算法，然而，兩篇文獻在模型中并沒有考慮映射階段的能耗降低和通信代價的影響。文獻[7-8]同步考慮了映射階段和調(diào)度階段的能耗，但忽略了通信代價對能耗的影響。文獻[9]提出一種基于兩階段調(diào)度與映射框架的整數(shù)規(guī)劃IP算法，尋找最優(yōu)任務(wù)-資源匹配與電壓分配方案。然而，調(diào)度決策中卻忽略了考慮通信代價。不同于以上工作，文獻[10]提出一種CAHPC算法，將通信代價考慮到調(diào)度與映射階段中進行能耗優(yōu)化。然而，本文的工作將移動應用卸載問題形式化為一個二次分派問題，以兩層遺傳算法進行了求解，且以任務(wù)交互圖TIG對移動應用進行了分割，提供了對單個任務(wù)模塊進行卸載決策的可行性。

本文將卸載決策問題建模為一個二次分派問題，并提出一種兩層遺傳算法進行求解，其中：內(nèi)層調(diào)度問題的目標是通過構(gòu)建最大化的計算代價尋找最優(yōu)資源頻率分配；而外層映射問題的目標是尋找最優(yōu)的任務(wù)-資源分配方案，以產(chǎn)生接近于全局期限的完成代價。即算法將利用不超過期限的松馳時間，得到能效更高的調(diào)度方案。

1 系統(tǒng)模型

1.1 相關(guān)定義

1) 任務(wù)交互圖(Task Interaction Graph,TIG)。TIG為工作流結(jié)構(gòu)，即有向無循環(huán)圖，其每個頂點代表一個任務(wù)，每條邊代表任務(wù)間的數(shù)據(jù)傳輸。

2) 運行頻率f。f為資源上處理器在執(zhí)行任務(wù)時的運行頻率，該頻率可利用處理器上的DVFS技術(shù)進行調(diào)整，若處理器運行在較高的執(zhí)行頻率，則計算代價(時間)更低，但能耗更高。

(1)

4) 通信代價Tcomm。執(zhí)行所有任務(wù)i∈N期間所有數(shù)據(jù)傳輸花費的時間即為TIG的通信代價。對于每個任務(wù)-資源分配a∈A，假設(shè)通信代價在所有資源-頻率分配組合下為常量，而對于不同的任務(wù)-資源分配，其值不同。

(2)

式中：Cij表示任務(wù)分配后兩個資源間的通信時間；p,q∈P。

5) 完成代價Ttotal。TIG的完成代價為計算代價和通信代價之和，表示為：

Ttotal=Tcomp+Tcomm

(3)

6) 全局期限dg。執(zhí)行TIG的最大允許時間即為全局期限dg。該值為整個TIG在移動設(shè)備上執(zhí)行的估算時間，可確保卸載環(huán)境下的TIG執(zhí)行優(yōu)先于整個TIG在移動設(shè)備上的執(zhí)行，以此改善能效并維持性能。

(4)

7) 擴展因子Sf。全局期限與TIG完成代價之比即為擴展因子，且Sf≥1。擴展因子的最優(yōu)值為1，即TIG剛好在截全局期限到達時完成。Sf<1表明TIG完成代價超過全局期限，無法滿足性能要求。

(5)

8) 松馳時間Tslack。對于每個任務(wù)-資源分配，松馳時間為全局期限dg與TIG的最遲完成代價Ttotal之差。若松馳時間較少，則表明完成代價已與期限較為接近。

Tslack=dg-Ttotal

(6)

9) 剩余松馳時間Tresidual。對于每個任務(wù)-資源分配，剩余松馳時間為全局期限與通信代價及平均計算代價之差。若Tresidual較高，TIG的執(zhí)行可通過利用DVFS放緩任務(wù)執(zhí)行而增加計算代價，進而降低執(zhí)行能耗。

(7)

10) 局部期限dl(Ti)。完成任務(wù)Ti的最大允許時間為局部期限。初始條件下，任務(wù)Ti的平均計算代價即為其局部期限，然后剩余松馳時間Tresidual以正比于平均計算代價%Tresidual(即初始局部期限)的方式在所有任務(wù)間進行分配，并被添加至各自的平均計算代價中，以此為任務(wù)設(shè)置新的擴展局部期限。

(8)

式中：

(9)

1.2 執(zhí)行時間模型

TIG負載在運行頻率為f的處理器上的執(zhí)行時間為：

(10)

為了最小化功耗，TIG中的每個任務(wù)需要執(zhí)行于不同的運行頻率上。因此，式(10)可重寫為：

(11)

(12)

1.3 通信時間模型

執(zhí)行于兩個資源上的任務(wù)間的數(shù)據(jù)傳輸量為DMbit，傳輸帶寬為BWMbit/s，則通信時間為：

(13)

1.4 能量模型

任務(wù)的計算能耗為功耗與執(zhí)行時間的乘積，功耗取決于運行頻率，執(zhí)行時間為式(11)，那么：

(14)

(15)

類似地，總體通信能耗Ecomm為：

(16)

式中：Pi,tx和Pi,rx分別表示發(fā)送和接收功率；Cij表示對應的通信時間。因此，TIG執(zhí)行的總體能耗為：

E=Ecomp+Ecomm

(17)

2 問題形式化

將移動設(shè)備上的應用劃分為包含多個互聯(lián)部分的TIG，表示為有向圖G(V,E,dg)。令T={Tj,1≤j≤N}表示TIG中的任務(wù)集合，圖的每個頂點Tj∈V代表TIG中的一個任務(wù)，每個任務(wù)Tj可表示為三元組Tj，其中：Ec表示任務(wù)執(zhí)行需要的總CPU周期數(shù)，即執(zhí)行負載；F(Tj,Ti)∈E表示任務(wù)Tj與Ti間的數(shù)據(jù)流；dl(Tj)表示任務(wù)Tj的局部期限。假設(shè)每個任務(wù)Tj最多可擁有5個模塊M={Mk,1≤k≤5}，可在相同或不同的處理器頻率下執(zhí)行以降低資源能耗。任務(wù)Tj的所有模塊執(zhí)行所需的CPU周期數(shù)之和恒為Ec，dg給出TIG完成執(zhí)行的全局期限。令P={pi,1≤i≤P}表示資源集合，也可表示為有向圖結(jié)構(gòu)，每個節(jié)點pi代表一個資源，每個資源pi可表示為二元組pi，其中：f表示資源的運行頻率；D(pi,pj)∈E表示資源pi與pj間的帶寬。每個資源pi上的處理器可運行于離散的頻率下，表示為f={fk,1≤k≤F}。

N個任務(wù)在M個資源上的映射不僅取決于計算代價，還取決于通信代價。為了計算最優(yōu)代價，問題求解需要計算所有任務(wù)-資源分配下的總代價?；谝陨戏治觯韵聦⒃撔遁d決策問題定義為具有以下假設(shè)的二次分派問題(Quadratic Assignment Problem,QAP)[11]：

1) 所有處理器資源擁有相同的離散運行頻率集合；

2) 對于每個任務(wù)的不同模塊，所有資源可以相同或不同的運行頻率進行任務(wù)執(zhí)行；

3) 每個任務(wù)至多可分配至一個資源上執(zhí)行；

4) TIG需在全局期限內(nèi)完成，而單個任務(wù)需在其局部期限內(nèi)完成。

基于此，QAP可表示為：

(18)

約束條件為：

Tcritical≤dg

(19)

(20)

(21)

aij∈{0,1}i,j=1,2,…,N

(22)

首先，基于以上優(yōu)化模型，分別分析決策變量a∈A和f∈F。

1) 分配決策a：對于每個任務(wù)-資源分配a∈A，全局松馳時間Tslack為全局期限與計算代價和通信代價之差。最優(yōu)全局松馳時間可以通過列舉所有任務(wù)-資源分配A下的全局松馳時間得到。決策變量a∈A給出了擁有最小全局松馳時間的任務(wù)-分配解，這表明TIG的完成代價Ttotal已接近于TIG的全局期限。

2) 頻率決策f：對于每個任務(wù)-資源分配a∈A，計算代價Tcomp為任務(wù)分配至資源上的執(zhí)行代價。然而，計算代價在所分配的處理器利用DVFS改變頻率時會發(fā)生變化。例如：若處理器運行在更高頻率，則計算代價較低，但能耗更高。離解的運行頻率結(jié)構(gòu)可以使頻率決策變量f∈F識別出最大化代價時的最優(yōu)資源運行頻率，從而得到最小化的全局松馳時間。

其次，對于式(18)給出的目標函數(shù)而言，第一部分dg給出全局期限，即TIG完成的最大延時；第二部分給出單個任務(wù)-資源分配下的總體計算代價，但僅在任務(wù)i分配至資源p，即aip=1時才進行計算；第三部分給出單個任務(wù)-資源分配下的總體通信代價。

最后，對于約束條件，式(19)表明僅當最終的執(zhí)行時間小于或等于全局期限時，才可以將當前的任務(wù)-資源分配添加至全局松馳時間中。式(20)和式(21)表明每個任務(wù)僅能分配至一個資源上。式(22)表明分配變量aip為二進制數(shù)，即為0或1。

3 兩階段混合整數(shù)QAP

為了計算全局松馳時間，需要同時得到計算代價和通信代價。計算代價取決于處理器資源的運行頻率，通信代價取決于資源間的帶寬。對于單個通信代價，可能擁有較大的計算代價，由于對于每個任務(wù)-資源分配(即映射)而言，其資源頻率分配(即調(diào)度)可能較大。此時的計算代價的取值范圍為以最快處理器頻率得到的最小代價至以最慢處理器頻率得到的最大代價。為了得到最小的全局松馳時間，計算代價必須盡可能大。因此，為了找到最優(yōu)的任務(wù)-資源分配，必須找到最優(yōu)的資源頻率分配，進而在不超過期限的同時產(chǎn)生最大化的計算代價?；诖朔治隹芍?，直接求解式(18)的目標函數(shù)值比較困難。然而，計算代價與通信代價間的相互無關(guān)性使得可以將式(18)中的問題分解為由子問題S和上層問題T組成的兩階段混合整數(shù)QAP，以簡化TIG的最優(yōu)全局松馳時間的求解過程。

3.1 子問題S

子問題S的目標是在所有可能的頻率f∈F下找到一個頻率分配，使得該頻率在每個任務(wù)-資源分配中可以得到最大的計算代價。對于給定的任務(wù)-資源分配aip∈A和運行頻率f∈F，子問題S試圖尋找處理器運行頻率組合，得到最優(yōu)的計算代價，可表示為：

(23)

約束條件為：

Tip

(24)

3.2 上層問題T

(25)

式(25)的約束條件為式(19)-式(22)。因此，求解上層問題T即求解式(18)。子問題S和上層問題T聯(lián)立考慮為一個兩階段混合整數(shù)二次分派問題QAP，而T即為映射階段的優(yōu)化問題。

4 基于松馳時間的TIG調(diào)度

本節(jié)提出一種基于松馳時間TIG調(diào)度算法，實現(xiàn)TIG中任務(wù)的映射與調(diào)度。QAP為NP聯(lián)合優(yōu)化問題，利用兩層遺傳算法GA求解兩階段QAP，分別定義：getOptimalTaskResource(G(V,E,dg))(算法1)為求解映射最優(yōu)化，即外層GA；getOptimalResourceFrequency((G,f),a∈A,f∈F)(算法2)為求解調(diào)度最優(yōu)化，即內(nèi)層GA。

圖1 兩層映射與調(diào)度GA算法

兩種GA算法的過程如算法1和算法2所示。

算法1映射階段GA算法

Input:workflowG(V,E,dg),Task-Resource Assignmenta∈A,Resource-Frequency assignmentf∈F

Output:Optimal Task-Resource Assignment,Optimal Resource-Frequency assignment

[2]foreacha∈Ado

[3] calculate theTcritical

[5] calculate the Communication costTcomm

[6] calculate residual slack timeTresidual

[7] assign the local deadlinedlto all the tasks inG(V,E)

[9] calculate the global slack timeTslack

算法2調(diào)度階段GA算法

Input: workflowG(V,E,dg), Task-Resource Assignmenta∈A,Resource-Frequency assignmentf∈F

Output: Optimal Resource-Frequency assignment getOptimalResourceFrequency((G,f),a∈A,f∈F)

[1]foreachTaskjdo

[2]foreachProcessorido

[3]foreachFrequencykdo

[4] calculateTcomp

[7]endforeach

[8]endforeach

[9]endforeach

具體步驟如下：

步驟S1通過調(diào)用映射GA算法getOptimalTaskResource(G(V,E,dg))開始優(yōu)化過程，即算法1步驟1。

步驟S3對于每個任務(wù)-資源分配，利用式(7)計算Tresidual，即算法1步驟6。

步驟S4利用式(8)和式(9)，將剩余松馳時間Tresidual分配至每個任務(wù)作為其局部期限dl(Ti)，即算法1步驟8；并調(diào)用調(diào)度階段GA算法，即算法1步驟8。

步驟S5對于每個資源頻率分配，利用式(1)計算Tcomp，即算法2步驟4。

5 仿真實驗

實驗測試了不同的TIG結(jié)構(gòu)下的算法性能，TIG以隨機方式生成，包括隨機生成任務(wù)的執(zhí)行指令周期數(shù)、任務(wù)間的數(shù)據(jù)流以及全局期限等，資源參數(shù)包括運行頻率和資源間的帶寬也以隨機方式生成。算法以枚舉法產(chǎn)生任務(wù)-資源分配和FF種資源頻率分配組合。利用MABLAB R2012b作為實驗環(huán)境。實驗結(jié)構(gòu)數(shù)據(jù)如表1所示。

表1 實驗結(jié)果

5.1 映射階段指標分析

映射階段指標包括能耗節(jié)省、擴展因子和全局松馳時間。為了測試能效，隨機生成的TIG被映射與調(diào)度至資源上。實驗中，以Eoffload表示任務(wù)卸載后得到的能耗，Emobile表示任務(wù)完全在移動設(shè)備上執(zhí)行得到的能耗，能耗節(jié)省比例計算為：

(26)

表1中:對于擁有3個任務(wù)的TIG，Emobile=154 mJ，Eoffload=93 mJ，根據(jù)式(26)，能量節(jié)省為40%。平均來說，任務(wù)卸載可以節(jié)省約35%的能耗，這表明調(diào)度階段算法計算最優(yōu)的運行頻率是有效可行的。擴展因子描述的是卸載應用任務(wù)的完成時間的可擴展性，應用擴展性越好，其值越接近于1。對于擁有3個任務(wù)的TIG，dg=1.02 s，Ttotal=0.85 s，根據(jù)式(5)，擴展因子為1.2，而表中結(jié)果顯示TIG的平均擴展因子為1.4。類似地，全局松馳時間給出的是任務(wù)可擴展其運行的剩余時間。對于擁有3個任務(wù)的TIG，dg=1.02 s，Ttotal=0.85 s時，根據(jù)式(6)，全局松馳時間為0.17 s，而平均全局松馳時間為0.56 s。

5.2 調(diào)度階段指標分析

(27)

(28)

表1中，對于擁有3個任務(wù)的TIG，其總卸載期限為0.94 s，而總初始期限為0.58 s，根據(jù)式(28)，其緩慢值為62%?？梢?，TIG的平均緩慢值在初始值的基礎(chǔ)上增加了37%。改進緩慢值的主要障礙在于TIG的通信代價，它會降低剩余松馳時間。

成功率SR是度量任務(wù)成功執(zhí)行次數(shù)的指標。若移動設(shè)備上的能耗小于卸載的能耗或本文設(shè)計的調(diào)度算法無法在所有資源頻率組合下提供最優(yōu)的計算代價(無法滿足其局部期限)，則應用無法執(zhí)行完成，即為一次失敗的調(diào)度過程。從表1的結(jié)果可以看到，算法具有78%的平均調(diào)度成功率。

圖2給出了在不同TIG中算法得到的最優(yōu)資源頻率分配結(jié)果，圖3給出了在不同TIG中算法得到的最優(yōu)任務(wù)-資源分配結(jié)果。圖2中，對于擁有3個任務(wù)的TIG，任務(wù)模塊#1、#2、#3、#4和#5分別運行在頻率600、600、600、600和1 400 MHz下。圖3中，對于擁有3個任務(wù)的TIG，任務(wù)#1、#2和#3分別分配至資源#3、#2和#1上運行。

圖2 資源頻率最優(yōu)分配

圖3 任務(wù)-資源最優(yōu)分配

5.3 與同類調(diào)度算法對比分析

利用SPECJVM實驗床中的開源移動應用DBAP進行大規(guī)模實驗仿真對比，該移動應用是一種數(shù)據(jù)庫訪問程序應用，其TIG結(jié)構(gòu)上總體由33個任務(wù)節(jié)點、82條有向邊構(gòu)成。同時，選取文獻[9]的IP算法、文獻[10]的CAHPC算法和同為遺傳算法的DPGA算法[12]進行性能比較。DPGA算法在遺傳操作上不同于傳統(tǒng)的遺傳算法，利用了初始種群和預留種群進行解的進化，以此豐富種群個體，為單層次的遺傳調(diào)度。圖4和圖5是算法隨著迭代次數(shù)的改變而得到的執(zhí)行時間和執(zhí)行能耗的實驗結(jié)果?？梢钥闯觯薎P算法，其他所有迭代式算法的執(zhí)行時間和執(zhí)行能耗均是隨著迭代次數(shù)的增加而下降的，這是由于IP算法在尋找最優(yōu)任務(wù)-資源匹配與電壓分配方案時是一次性計算結(jié)果，而沒有采用啟發(fā)式算法的迭代尋優(yōu)，因此其執(zhí)行時間和執(zhí)行能耗是恒定值。本文算法比對比算法在兩項指標上更加有效，可以以更少的迭代次數(shù)和更快的速度收斂到最優(yōu)解上，這表明本文算法能有效利用松馳時間，其決策時間也更短。比較而言，DPGA算法比CAHPC算法的性能更好，DPGA采用了更好的初始種群配置方法，可以有效豐富種群個體，增加遺傳尋優(yōu)概率。而本文算法采用了兩層遺傳算法對卸載決策問題進行求解，通過建模為一個二次分派問題尋找最優(yōu)資源頻率分配方案，這種內(nèi)層調(diào)度和外層映射的兩階段求解方法，可以產(chǎn)生接近于全局期限的完成代價，進而使得算法在執(zhí)行時間和執(zhí)行能耗上具有更好的優(yōu)勢，較其他算法可以節(jié)省更多的能量。

圖4 執(zhí)行時間

圖5 執(zhí)行能耗

6 結(jié) 語

本文將卸載決策問題建模為一個二次分派問題，并提出一種兩層遺傳算法進行求解，其中：內(nèi)層調(diào)度問題的目標是通過構(gòu)建最大化的計算代價尋找最優(yōu)資源頻率分配；而外層映射問題的目標是尋找最優(yōu)的任務(wù)-資源分配方案，以產(chǎn)生接近于全局期限的完成代價。

本文算法利用不超過期限的松馳時間，得到能效更高的調(diào)度方案。實驗結(jié)果表明，在本文算法下進行的任務(wù)卸載，平均可以為移動設(shè)備節(jié)省約35%的能耗。