一種基于引力搜索機制的云工作流調度算法

王旖旎 李 明

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

0 引 言

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

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

1 相關研究

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

2 問題模型

2.1 工作流模型

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

注：節點代表任務，有向邊代表順序關系，節點t1中任務標識下的數字13代表任務的計算負載量，有向邊上的數字代表有向邊對應的出發任務節點產生的數據量

圖1 工作流示例

2.2 云服務模型

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

3 問題定義

3.1 相關參數定義

文中相關參數含義說明如下：

N：種群大??；

n：工作流中任務數量；

ti：任務i；

m：可用虛擬機量；

vj：虛擬機j；

Xi：代理i；

Xbest：至目前為止的最優代理；

α：計算適應度時調度長度和調度代價的權重；

fiti：代理i的適應度；

Mi：代理i的質量；

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

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

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

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

δ：質量門限值。

相關約束和假設如下：

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

(1)

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

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

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

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

3.2 優化問題描述

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

VM-shutdown-time

(2)

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

(3)

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

(4)

因此，工作流的調度代價為：

(5)

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

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

(6)

(2) 0≤α≤1

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

4 算法設計

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

4.1 初始種群生成方式

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

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

(7)

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

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

4.2 代理表示

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

(8)

表1 代理示例

4.3 適應度評估

(9)

4.4 調度方法

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

步驟1以HEFT算法的輸出結果作為種子得到初始種群，以更少的迭代次數產生更優的解。

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

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

4.5 粒子位置更新

考慮系統包含N個代理，代理i的位置定義為：

(10)

(11)

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

(12)

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

(13)

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

(14)

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

(15)

(16)

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

(17)

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

4.6 算法具體步驟

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

算法1HGSA算法過程

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

輸出：任務映射結果M

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

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

3. fork=1 toMAX_ITERATIONdo

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

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

6. 基于計算的適應度值識別最優和最差代理

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

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

9. fori=1 toNdo

10. ifMi<δthen

11. 賦值Pos為區間[1,n]間的隨機整數值

13. 賦值xposi為區間[1,m]間的隨機整數值

14. end if

15. end for

16. end for

17. 基于適應度fiti尋找M個對應的最優代理

18. returnM

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

5 算例分析

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

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

圖3 云資源環境

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

表3 代理初始種群

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

表4 任務優先級及映射

續表4

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

圖4 HEFT解加至種群

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

表5 最優代理結果

表6 調度結果

6 仿真實驗

6.1 實驗配置與性能指標

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

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

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

6.2 實驗結果

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

(a) Epigenomic工作流

(b) Montage工作流

(c) CyberShake工作流

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

7 結 語

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