王旖旎 李 明

1(重慶商務職業(yè)學院 重慶 401331)2(重慶大學計算機學院 重慶 400044)

0 引 言

云環(huán)境中的工作流調(diào)度廣泛應用于科學研究與商業(yè)領域，如天文學、天氣預測、醫(yī)療和生物信息學等。工作流規(guī)模較大，包括大量獨立和依賴型任務，需要規(guī)模較大的計算、通信和存儲環(huán)境實現(xiàn)其調(diào)度與執(zhí)行。工作流調(diào)度的實質(zhì)是具有偏序關系的任務至云資源間的映射問題，通常以滿足用戶定義的相關QoS約束為目標完成工作流任務的執(zhí)行[1]。傳統(tǒng)的網(wǎng)格工作流調(diào)度問題更加注重調(diào)度效率，即優(yōu)化調(diào)度時間，沒有考慮資源使用帶來的調(diào)度代價[2]。云計算環(huán)境中，資源的處理能力和處理租用價格不一，資源能力越高，價格也越高。此時，具體應用的調(diào)度策略所帶來的調(diào)度時間和調(diào)度代價也不相同。因此，同步考慮工作流執(zhí)行的時間和代價，這將更加符合云環(huán)境下工作流調(diào)度的場景。

然而，現(xiàn)實的情況是，優(yōu)化工作流的調(diào)度時間和調(diào)度代價本身是兩個相互沖突的目標。若要降低調(diào)度時間，則工作流任務將偏好在性能更高的資源上執(zhí)行，而資源性能越高，其利用代價也將越高；反之，若要降低調(diào)度代價，則工作流任務將偏好在價格更低的資源上執(zhí)行，而資源價格越低，其性能也將越低，此時調(diào)度時間也將延長。為了解決這一問題，提出一種基于引力搜索算法的工作流調(diào)度算法，利用引力搜索的進化機制，通過代理適應度的評估，得到最終在調(diào)度時間和調(diào)度代價上綜合性能最優(yōu)化的任務映射方案。

1 相關研究

為了解決工作流調(diào)度問題，啟發(fā)式調(diào)度算法是常規(guī)方法。文獻[3]提出LOSS和GAIN兩種算法分別用來優(yōu)化預算約束下的時間和代價，但僅涉及單目標優(yōu)化。文獻[4]討論了IaaS云環(huán)境中的代價和截止時間約束工作流調(diào)度，但所考慮的資源僅為同質(zhì)資源模型。文獻[5]提出兩種云工作流調(diào)度算法：一階段算法IC-PCP和兩階段算法IC-PCPD2。兩種算法可以在多項式時間內(nèi)得到載止時間約束下的代價最小調(diào)度方案。文獻[6]提出了在混合云中截止時間約束的代價最小化調(diào)度算法HEFT，利用子截止時間的概念進行資源的重調(diào)度，并實現(xiàn)了代價最小化。文獻[7]則實現(xiàn)了包任務在截止時間約束下的代價最小化調(diào)度，但僅適用于獨立任務調(diào)度。文獻[8]利用粒子群搜索方法求解了用戶截止時間約束下費用最小化的工作流調(diào)度方案。文獻[9-11]提出了一種截止時間與預算約束時工作流調(diào)度遺傳算法，但也僅是實現(xiàn)執(zhí)行代價或執(zhí)行時間的單一優(yōu)化?？梢钥闯觯陨蠁l(fā)式或元啟式算法多數(shù)僅進行了壟斷和單一目標優(yōu)化。針對以上問題，本文將從優(yōu)化調(diào)度長度和調(diào)度代價兩個方面入手，提出新的云工作流任務調(diào)度算法，提升在兩個指標上的綜合性能。

2 問題模型

2.1 工作流模型

工作流應用可表示為有向無循環(huán)圖DAG，G=(T,E)，如圖1所示，其中：T={t1,t2,…,tn}表示任務集合；E表示有向邊集合；一條邊ti→tj表明前驅ti與后繼tj間的執(zhí)行次序約束。因此，任務tj在ti完成前無法開始執(zhí)行。每個任務ti擁有以MI表示的計算負載屬性。而每條邊ti→tj擁有的屬性為任務ti生成的輸出數(shù)據(jù)量，該數(shù)據(jù)即執(zhí)行tj需要的數(shù)據(jù)。若任務不存前驅，則可視為入口任務tentry；若任務不存在后繼，則可視為出口任務texit。若工作流擁有多個入口任務，可添加零計算負載無數(shù)據(jù)輸出的傀儡任務至工作流結構中。擁有多個出口任務的工作流也可作類似操作，不影響計算工作流調(diào)度時間和代價。

注：節(jié)點代表任務，有向邊代表順序關系，節(jié)點t1中任務標識下的數(shù)字13代表任務的計算負載量，有向邊上的數(shù)字代表有向邊對應的出發(fā)任務節(jié)點產(chǎn)生的數(shù)據(jù)量

圖1 工作流示例

2.2 云服務模型

假設云服務包含m個虛擬機，表示為V={v1,v2,…,vm}。每個虛擬機擁有自身的計算能力，以MIPS衡量。所有虛擬機之間是全連通結構，可寄宿于一個或多個物理云服務器上。傳輸任務ti至tj的輸出數(shù)據(jù)的時間可考慮為通信開銷時間。若任務ti與tj執(zhí)行于同一虛擬機上，則通信開銷為零。

3 問題定義

3.1 相關參數(shù)定義

文中相關參數(shù)含義說明如下：

N：種群大??；

n：工作流中任務數(shù)量；

ti：任務i；

m：可用虛擬機量；

vj：虛擬機j；

Xi：代理i；

Xbest：至目前為止的最優(yōu)代理；

α：計算適應度時調(diào)度長度和調(diào)度代價的權重；

fiti：代理i的適應度；

Mi：代理i的質(zhì)量；

σ：價格模型中的隨機變量；

Vcbase：最慢虛擬機的基準價格；

digvj：虛擬機vj的性能下降；

γ：控制引力常量偏差的常量；

δ：質(zhì)量門限值。

相關約束和假設如下：

1) 考慮虛擬機的性能變化來計算執(zhí)行任務時的有效CPU周期，對于虛擬機vj，性能變化表示為degvj，利用degvj，任務ti在虛擬機vj上的執(zhí)行時間可重寫為：

(1)

式中：Load(ti)表示任務ti的計算負載；Capacity(vj)表示虛擬機vj的計算能力。

2) 計算執(zhí)行代價時考慮單位支付時間τ。若租用虛擬機的時間小于τ，則按照全部時間單位τ支付費用。

3) 利用虛擬機時需要考慮虛擬機的初始啟動時間，即在計算調(diào)度長度時需要加入虛擬機啟動時間，同時將虛擬機的關機時間也考慮至調(diào)度長度中。

4) 虛擬機之間以相同帶寬進行全連通。

3.2 優(yōu)化問題描述

1) 調(diào)度長度Makesapn計算。調(diào)度長度即為整個工作流的總體執(zhí)行時間，包括租用虛擬機的啟動時間、執(zhí)行時間、虛擬機間的數(shù)據(jù)傳輸時間和虛擬機的關機時間。假設數(shù)據(jù)正在傳輸過程中虛擬機無法執(zhí)行任務，則調(diào)度長度等于虛擬機啟動時間、所有虛擬機中虛擬機時間VM-time的最大值及虛擬機關機時間之和。VM-time[i]表示最后一個時間戳至虛擬機vi執(zhí)行其指定任務的時間間隔。啟動時間和關機時間僅需計算一次的原因在于虛擬機僅需在首次啟動并在最后一次關機。因此，調(diào)度長度為：

VM-shutdown-time

(2)

2) 調(diào)度代價cost計算。調(diào)度模型中，云服務器由擁有針對不同負載類型的不同計算能力的虛擬機組成，式(1)表示任務ti在虛擬機vj上的執(zhí)行時間，令τ表示任務的單位支付時間，Vcbase表示最慢虛擬機的基準價格，cost(ti,vj)定義為任務ti在虛擬機vj上的執(zhí)行代價：

(3)

式中：σ表示隨機變量，以產(chǎn)生不同的虛擬機價格組合和能力,CCvj表示虛擬機vj的CPU周期數(shù)，CCslowest表示虛擬機中最慢CPU周期數(shù)。令Bi,j表示布爾變量，定義為：

(4)

因此，工作流的調(diào)度代價為：

(5)

3) 最優(yōu)化問題。云工作流的調(diào)度目標即是最小化調(diào)度長度和調(diào)度代價，可表示為最小化兩個目標的線性組合，將其形式化為：

Minz=α×Makespan+(1-α)×Costtotal

(6)

(2) 0≤α≤1

其中：約束條件(1)表明工作流中的任一任務僅能分配至一個虛擬機上；約束條件(2)表明權重因子，表示算法對于調(diào)度長度和調(diào)度代價優(yōu)化的偏好。

4 算法設計

本文設計的算法稱為混合引力搜索算法，簡稱HGSA。

4.1 初始種群生成方式

以HEFT算法[13]的輸出結果作為初始種群的生成方式，即以最小化最早完成時間為目標進行任務調(diào)度，具體包括兩個步驟：

步驟1計算任務優(yōu)先級。該階段中，每個任務的優(yōu)先級利用平均執(zhí)行時間和平均通信時間計算。優(yōu)先級定義為升秩值表達。根據(jù)由高到低的優(yōu)先級排序得到任務調(diào)度次序，從而滿足給定工作流的任務執(zhí)行順序約束。任務ti的優(yōu)先級定義為：

(7)

式中：wi,avg表示任務ti的平均執(zhí)行時間；ci,j,avg表示任務ti與tj間的平均通信時間。

步驟2任務與虛擬機間的映射。通過在所有可用虛擬機上計算任務最早開始時間EST和最早完成時間EFT，根據(jù)任務的優(yōu)先級，得到任務的調(diào)度結果。

4.2 代理表示

算法中，工作流中任務與虛擬機間的映射可視為一個代理agent。對于擁有n個任務的工作流和m個虛擬機的云服務器的調(diào)度環(huán)境，代理i可表示為維度為1×n的矢量，即：

(8)

表1 代理示例

4.3 適應度評估

(9)

4.4 調(diào)度方法

HGSA算法包括兩個階段。第一階段僅集中于調(diào)度長度的優(yōu)化，第二階段優(yōu)化調(diào)度代價，同時最小化適應度值，適應度則同步考慮了調(diào)度長度和調(diào)度代價。第一階段產(chǎn)生的結果可指導引力搜索算法GSA中粒子的運動，可以改進傳統(tǒng)GSA的隨機初始化粒子運行機制。算法具體步驟為：

步驟1以HEFT算法的輸出結果作為種子得到初始種群，以更少的迭代次數(shù)產(chǎn)生更優(yōu)的解。

步驟2根據(jù)適應度函數(shù)保留當前代中的最優(yōu)粒子，確保最優(yōu)代理在未來代中不被剔除。

步驟3質(zhì)量小于門限值δ的代理從當前種群中剔除，由于該類代理在種群更新中貢獻較少。剔除以上代理后，添加以最優(yōu)代理為基礎的新的代理至種群中，改進種群全局適應度。

4.5 粒子位置更新

考慮系統(tǒng)包含N個代理，代理i的位置定義為：

(10)

(11)

式中：ε表示極小常量；Ri,j(k)表示第k次迭代時代理i與代理j間的歐氏距離，定義為：

(12)

若代理i在維度d上的總引力為其他代理在維度d上產(chǎn)生的引力的隨機權重和，則：

(13)

式中：randj表示[0,1]間的隨機數(shù)?？芍?，代理i在第k次迭代時在維度d上的加速度為：

(14)

由此可知，代理的位置和速率更新可計算為：

(15)

(16)

G(k)為引力常量G0和迭代次數(shù)k的函數(shù)，定義為：

(17)

式中：γ表示較小常量，用于控制引力常量的降低；G0在算法開始時初始化，并隨著算法的執(zhí)行而降低，以改進搜索準確性。

4.6 算法具體步驟

算法1是HGSA的具體執(zhí)行過程。步驟1為將任務在虛擬機間進行隨機映射以產(chǎn)生初始種群，步驟2為將HEFT算法輸出的結果播種至種群中。初始種群準備就緒后，種群中的代理需要迭代若干次數(shù)以產(chǎn)生最終結果，即步驟3-步驟16。迭代的第一步是計算引力常量，即步驟4。然后在步驟5中，根據(jù)式(9)計算每個代理的適應度。根據(jù)適應度值，步驟6為識別種群中的最優(yōu)代理和最差代理，步驟7為計算所有代理的質(zhì)量。步驟8為通過計算純引力、純加速度和速率，以更新每個代理的位置。剩余步驟中，算法用新的代理取代劣勢代理。新代理的生成方式為將任務映射至隨機選取的虛擬機上，剩余映射方案則仍然維持不變。

算法1HGSA算法過程

輸入：工作流應用W，云服務資源CSS

輸出：任務映射結果M

1. 初始化擁有N個隨機代理的種群X

2. 利用HEFT生成的解代替種群中的一個代理

3. fork=1 toMAX_ITERATIONdo

4. 利用式(19)計算G(k)

5. 利用式(10)計算適應度值fiti

6. 基于計算的適應度值識別最優(yōu)和最差代理

7. 利用式(11)計算代理質(zhì)量Mi

8. 利用式(13)-式(18)計算每個代理的速率與位置

9. fori=1 toNdo

10. ifMi<δthen

11. 賦值Pos為區(qū)間[1,n]間的隨機整數(shù)值

13. 賦值xposi為區(qū)間[1,m]間的隨機整數(shù)值

14. end if

15. end for

16. end for

17. 基于適應度fiti尋找M個對應的最優(yōu)代理

18. returnM

HGSA算法根據(jù)原始引力搜索算法的空間搜索步驟進行最優(yōu)解搜索，因此其時間復雜度與GSA算法相同，同為O(N)，N為初始化的粒子數(shù)量。

5 算例分析

考慮一個Montage工作流進行算法算例分析，工作流包括16個任務，T={t1,t2,…,t16}，云環(huán)境包括4個虛擬機，V={v1,v2,v3,v4}，工作流的結構和虛擬機結構如圖2和圖3所示。4個虛擬機為全連通結構，算法分析的目標是以優(yōu)化調(diào)度長度和調(diào)度代價為目標，將任務調(diào)度至虛擬機上執(zhí)行。表2給出算例中的相關參數(shù)，表3給出算法步驟1描述的生成初始種群結構。

圖2 算例應用的工作流結構

圖3 云資源環(huán)境

參數(shù)取值虛擬機數(shù)量4虛擬機計算能力2.0,3.5,4.5,5.5MIPS網(wǎng)絡帶寬1Mbit/s虛擬機啟動時間和關機時間0.5s虛擬機性能變化24%最大迭代次數(shù)10種群大小N100引力常量G05權重系數(shù)α0.5較小常量γ0.3劣勢代理的質(zhì)量門限值δ0.1極小常量ε10

表3 代理初始種群

利用式(8)計算任務優(yōu)先級，根據(jù)優(yōu)先級的降序排列，任務被依次映射至一個虛擬機上，使得任務的最早完成時間達到最小化。表4為算法得到的任務優(yōu)先級與相應任務映射情況。同時可以計算出HEFT算法得到的調(diào)度長度和調(diào)度代價分別為36.57 s和＄50.31。

表4 任務優(yōu)先級及映射

續(xù)表4

圖4顯示了HEFT生成的映射方案加至初始種群以取代劣勢代理的示例，即算法步驟2。

圖4 HEFT解加至種群

至此，當前種群包含HEFT生成的代理和隨機生成的代理，種群按照算法中步驟3-步驟16的迭代步驟進行進化。表5給出了每次迭代中最優(yōu)代理的相關值情況，表6則是相應的調(diào)度結果，此時的調(diào)度長度為32.64 s，調(diào)度代價為＄47.71。

表5 最優(yōu)代理結果

表6 調(diào)度結果

6 仿真實驗

6.1 實驗配置與性能指標

本節(jié)利用CloudSim平臺下的仿真實驗的方法對工作流調(diào)度算法進行性能分析，測試算法包括標準GSA算法[14]、HEFT算法[13]和HGA算法[15]。除種群模式設置為500，最大迭代次數(shù)設置為200之外，其他參數(shù)與表2相同。

通過標準化方法對調(diào)度長度和調(diào)度代價作出處理，以調(diào)度長度比率SLR和調(diào)度代價比率MCR作為性能評估指標，分別定義為：

選取四種不同科學領域的工作流結構作為數(shù)據(jù)測試源，包括：Epigenomic工作流(同時擁有計算密集型和網(wǎng)絡密集型任務)、Montage工作流(網(wǎng)絡密集型任務)、CyberShake工作流(同時擁有I/O密集型和網(wǎng)絡密集型任務)以及Inspiral工作流(計算密集型任務)。工作流的具體結構可參見文獻[12]。

6.2 實驗結果

圖5為四種工作流在不同任務規(guī)模下得到的SLR和MCR指標情況。可以看到，在所有工作流類型中，HGSA算法的MCR指標是優(yōu)于HEFT、HGA和GSA算法的，這說明初始種群的優(yōu)化配置和引力搜索機制可以得到代價更低的工作流調(diào)度解。比較標準的引力搜索GSA算法，該算法未優(yōu)化初始種群；而比較混合遺傳算法HGA，該算法則在種群位置更新上不如本文算法效率高。HEFT算法在進行工作流調(diào)度時，僅考慮了任務的執(zhí)行時間優(yōu)化，因此其代價性能是最差的。此外，在SLR指標上，HEFT是所有算法中性能最好的，因為該算法是以調(diào)度長度為單目標進行的工作流算法。HGSA在SLR指標上優(yōu)于HGA和GSA算法，雖然同為雙目標優(yōu)化算法，但本文在引力搜索機制上的改進，以及初始種群融入HEFT調(diào)度方案的優(yōu)化方法，使得本文算法在搜索最優(yōu)解時效率更高，在調(diào)度代價最優(yōu)的同時僅僅犧牲了極小的調(diào)度長度性能，其綜合性能是四種算法中最優(yōu)的。而在四種不同類型工作流結構中得到的結果并沒有體現(xiàn)很大差異，這說明本文算法在適應性上也是較優(yōu)的。

(a) Epigenomic工作流

(b) Montage工作流

(c) CyberShake工作流

(d) Inspiral工作流圖5 算法執(zhí)行結果

7 結 語

為了同步優(yōu)化云環(huán)境中工作流調(diào)度的長度和代價，提出了一種基于引力搜索算法的工作流任務調(diào)度算法。首先以異構最早完成時間機制生成引力搜索的部分初始代理，并結合隨機生成方式，得到初始種群。然后，利用引力搜索的進化機制，通過代理適應度的評估，得到最終在調(diào)度時間和調(diào)度代價上綜合性能最優(yōu)的任務映射方案。利用一個算例對算法的有效性進行了論證與評估，結果表明，本文算法不僅可以得到最小的調(diào)度時間，調(diào)度代價也是對比算法中最小的。