一種基于改進二進制粒子群的工作流云調(diào)度算法

熊聰聰，高 萌，趙 青，徐丹瀅

(天津科技大學(xué)人工智能學(xué)院，天津 300457)

隨著數(shù)據(jù)規(guī)模日漸龐大、計算日趨復(fù)雜，科學(xué)工作流已經(jīng)不能滿足數(shù)據(jù)處理的需求，批處理科學(xué)工作流應(yīng)運而生.批處理科學(xué)工作流較科學(xué)工作流運算更為復(fù)雜，數(shù)據(jù)處理能力更強，它是包含大量批處理任務(wù)組的科學(xué)工作流.批處理科學(xué)工作流廣泛應(yīng)用于高能物理學(xué)、氣象學(xué)、生物信息學(xué)等不同領(lǐng)域，是建模和管理數(shù)據(jù)密集型數(shù)據(jù)的有效手段.

云計算為批處理科學(xué)工作流的處理提供了技術(shù)手段支持.云計算在 2006年由搜索引擎服務(wù)提供商Google率先提出[1].目前，云計算的用戶數(shù)量已經(jīng)超過 40億.云計算是依靠虛擬技術(shù)進行使用，按需訪問是云計算的特點.數(shù)據(jù)密集型應(yīng)用是云計算環(huán)境下最普遍的應(yīng)用之一，數(shù)據(jù)通信往往是數(shù)據(jù)密集型應(yīng)用的性能瓶頸.面對龐大的數(shù)據(jù)規(guī)模，怎樣對其進行合理的任務(wù)分配，使得云計算能夠高效完成任務(wù)和給出合理調(diào)度方案顯得尤為重要.

作為云計算的核心技術(shù)，任務(wù)調(diào)度是云計算處理任務(wù)過程中的重要環(huán)節(jié)之一，因此優(yōu)化任務(wù)調(diào)度機制是提高云計算綜合性能的重要方法[2].在云環(huán)境中，任務(wù)調(diào)度是一個非確定性多項式問題(NP難題)的優(yōu)化問題[3].任務(wù)調(diào)度可以合理地分配計算資源任務(wù)，并且對計算的任務(wù)進行高效率的調(diào)度，主要目標(biāo)是將不同的用戶任務(wù)分配合適的資源，例如主機或虛擬機(VM)，并找出可以執(zhí)行任務(wù)的適當(dāng)順序在分配資源中執(zhí)行.任務(wù)調(diào)度促進了云數(shù)據(jù)中心的可持續(xù)發(fā)展，高效率的任務(wù)調(diào)度策略是非常必要的.

近年來，隨著應(yīng)用領(lǐng)域的不斷擴大，批處理科學(xué)工作流的調(diào)度問題引起了國內(nèi)外學(xué)術(shù)界的重視，Cai等[4]提出的方法只考慮了批量任務(wù)組的整體同步調(diào)度，沒有考慮批處理數(shù)據(jù)組中任務(wù)的單獨調(diào)度問題.此后，Cai等[5]又對該方法進行改進，提出了一種基于多規(guī)則調(diào)度的算法，通過提高剩余時間間隙的利用率以最小化租賃成本，可以用于批處理數(shù)據(jù)組中單個任務(wù)的調(diào)度，考慮到了任務(wù)轉(zhuǎn)移、浪費預(yù)測，但沒有考慮任務(wù)間數(shù)據(jù)的傳輸成本增加的問題.本文希望考慮批處理工作量中子任務(wù)的調(diào)度問題以及數(shù)據(jù)密集型任務(wù)中最為關(guān)鍵的數(shù)據(jù)傳輸成本的變化，將采用元啟發(fā)式算法加以解決.這是因為元啟發(fā)式算法通?？梢栽谟邢薜臅r間里高效、智能地探索搜索空間，以找到接近最佳的解決方案[6-7].而粒子群算法是近年來受到廣泛關(guān)注的一種元啟發(fā)式算法，具有效率高、收斂好的特點.

粒子群算法是美國的兩位學(xué)者 Eberhart和Kennedy源于對鳥群捕食行為的啟發(fā)提出的一種元啟發(fā)式算法，主要用來解決尋找最優(yōu)解問題.Rodriguez等[8]提出基于粒子群算法的動態(tài)時間片資源分配方法，雖然為了避免調(diào)度失敗，采用了最大化任務(wù)執(zhí)行時間假設(shè)的方法，但缺乏對任務(wù)間的數(shù)據(jù)依賴的考慮.馬亮等[9]提出一種改進的粒子群調(diào)度算法，以任務(wù)的完成時間為出發(fā)點進行考慮，對算法進行變異和修改，改進后的算法具有很好的性能，但著重考慮了任務(wù)的完成時間，未對其他影響因素進行考量.Saeedi等[10]提出一種改進的多目標(biāo)粒子群優(yōu)化算法求解工作流調(diào)度問題，該算法考慮了 4個影響因素，但未對粒子群算法的收斂性進行優(yōu)化.

粒子群算法一般用于連續(xù)空間上的求解問題，而二進制粒子群算法更適合于求解 0/1離散空間上的求解問題，這與任務(wù)的調(diào)度模型非常相似.但已有研究成果顯示，二進制粒子群算法存在收斂性不好的問題[11-12]，所以本文對粒子的更新公式進行了修改.隨著速度的逐漸降低(趨近于 0)，發(fā)生跳轉(zhuǎn)的概率增大，改進的算法有效避免了這個問題.實驗結(jié)果表明，該算法提高了最優(yōu)解的探測能力，所得最優(yōu)解具有更好的實際調(diào)度時間和成本，提高了資源的利用率.在相同的條件設(shè)置下，該算法優(yōu)于未經(jīng)改進的二進制粒子群算法，當(dāng)?shù)螖?shù)增多時，其綜合調(diào)度性能優(yōu)點明顯.

1 批處理科學(xué)工作流任務(wù)調(diào)度模型描述

工作流應(yīng)用程序被建模為 DAG 圖，即 E＝{T，U}，其中 T = { t1,t2, … ,tn}表示所有任務(wù)的集，任務(wù)間的偏序關(guān)系集合表示為 U = { (vi, vj)| i ＜j} ，(vi, vj)表示先執(zhí)行任務(wù)vi，然后再執(zhí)行任務(wù)vj.圖1為批處理科學(xué)工作流DAG圖.

圖1 批處理科學(xué)工作流DAG圖Fig.1 DAG diagram of batch scientific workflow

在云環(huán)境中進行任務(wù)調(diào)度，假設(shè)任務(wù)集合為T = { t1, t2, … ,tn}，虛擬機的集合為 V M = {v m1, v m2,… ,vmm}，有n個相互獨立的子任務(wù)將它們分配給m個虛擬機執(zhí)行，其中m＜n.第 j個子任務(wù)用 tj=(j=1,2,…,n}表示，第i個虛擬機用 v mi(i = 1 ,2,… ,m)表示.每個任務(wù)只能由一個虛擬機運行.任務(wù)集合與虛擬機集合的調(diào)度關(guān)系用矩陣X表示為

參考給出的矩陣 X，每一列代表任務(wù)分配，每一行代表分配給虛擬機的任務(wù).在每一列中，數(shù)值 1表示虛擬機被分配給一個任務(wù)時，每個任務(wù)只能由一個虛擬機來執(zhí)行，數(shù)值 0表示沒有被分配任務(wù).例如，表1為 3個虛擬機上有 5個任務(wù)的調(diào)度方案.與位置矩陣相似，每個粒子速度也以m×n矩陣的形式表示，其元素的范圍為[0，1].每行都只有一個 1，表示每個任務(wù)只能分配給一個虛擬機進行計算，但一個虛擬機可能不只計算一個任務(wù).

表1 調(diào)度方案圖示例Tab.1 Sample scheduling scheme diagram

2 改進二進制粒子群的批處理科學(xué)工作流任務(wù)調(diào)度算法

2.1 生成初始種群

初始種群的生成關(guān)系到算法能否快速找到最優(yōu)解，確定合理的初始種群對二進制粒子群算法至關(guān)重要.本文的初始種群采用計算機隨機生成，它的優(yōu)點是具有充分的隨機性，分布比較均勻，同時也保證了粒子的豐富性.

2.2 適應(yīng)度函數(shù)

處理優(yōu)化問題的關(guān)鍵在于構(gòu)造出合理的適應(yīng)度函數(shù)，它是判斷一個解好壞的標(biāo)準(zhǔn).適應(yīng)度函數(shù)的選取對二進制粒子群算法的效率尤為重要.本文以時間和成本為優(yōu)化目標(biāo).

當(dāng)任務(wù)節(jié)點為y，虛擬機使用類型為i類時，j個虛擬機執(zhí)行任務(wù)需要的時間為

其中：etcyi表示當(dāng)虛擬機類型為i時，在第y個任務(wù)節(jié)點執(zhí)行任務(wù)時所需的估測時間，tb為虛擬機啟動的時間與執(zhí)行軟件安裝的時間之和.

任務(wù)調(diào)度總時間是在關(guān)鍵路徑進行任務(wù)調(diào)度時所需要的時間總和.

當(dāng)任務(wù)節(jié)點為y，虛擬機使用類型為i類時，j個虛擬機執(zhí)行任務(wù)需要的總費用為

其中：a為虛擬機的租用周期，ci為虛擬機使用類型為i類時單個租用周期的單價.

總費用Ctotal為每個任務(wù)節(jié)點的費用的累加之和.

由上所述，適應(yīng)度函數(shù)fitness定義為

其中：w1+ w2=1，w1與w2為實數(shù)；Tdeadline為用戶所提供的調(diào)度該批任務(wù)所要求的截止時間與任務(wù)批開始進行調(diào)度的時間差值.Max代表取括號內(nèi)的兩數(shù)中較大的數(shù).

2.3 二進制粒子群算法及其改進

在粒子群算法中，每個優(yōu)化問題的最優(yōu)解可以通過搜索粒子的位置得到，由優(yōu)化的函數(shù)決定它們的適應(yīng)度函數(shù)值，粒子們依據(jù)當(dāng)前的最優(yōu)粒子狀態(tài)進行更新.標(biāo)準(zhǔn)粒子群算法根據(jù)式(6)進行解的迭代更新，在每一次迭代過程中，每個粒子根據(jù)兩個值更新它們的位置.其中一個值是粒子自身所找到的最優(yōu)解，這個解稱為個體極值；另一個極值是整個群體找到的最優(yōu)解，這個解稱為全局極值.

其中：w為慣性權(quán)重，rand()為均勻分布在(0，1)之間的隨機數(shù)，c1和 c2為學(xué)習(xí)因子.粒子的速度vi被最大速度vmax所限制，即若vi＞vmax，則令vi＝vmax，而若vi＜-vmax，也令vi＝vmax.為了處理離散型優(yōu)化問題，需對公式進行修改，提出了二進制粒子群算法.它的速度公式保持不變，位置的迭代公式修正為

為了防止sigm函數(shù)飽和，通常給vi+1的取值規(guī)定一個區(qū)間范圍為{－4.0，4.0]，sigm函數(shù)與速度vi的關(guān)系如圖2所示.需指出的是：sigm函數(shù)值不表示某位變化的概率，而是表示某位取1的概率.

圖2 sigm函數(shù)與vi關(guān)系Fig.2 Relationship between sigm function and vi

根據(jù)式(7)，粒子改變是一種根據(jù)概率進行的改變.位為 1的概率為sigm(vid)，而位為 0的概率為1-sigm(vid).如果位已經(jīng)是 0，則表示位發(fā)生變化的概率為sigm(vid)；如果位已經(jīng)是 1，則表示位發(fā)生變化的概率為1-sigm(vid).在速度vid值已知的前提下，位發(fā)生改變的絕對概率為

結(jié)合式(8)和式(9)，得

式(7)表示位速度與位改變的絕對概率之間關(guān)系，其關(guān)系如圖3所示.由圖3可以看出，當(dāng)位速度是 0時，位的絕對改變概率最大.經(jīng)分析得出以下結(jié)論：當(dāng)二進制粒子群算法的粒子速度是 0時，位最有可能發(fā)生改變，不利于全局最優(yōu)解的搜索，此時的算法具有更強的隨機性，缺乏方向性.二進制粒子群算法隨著迭代次數(shù)的增多，其隨機性更強了，不能收斂到全局最優(yōu)解.本文針對二進制粒子群算法的這種情況進行了改進.

圖3 位速度與位改變的絕對概率之間關(guān)系Fig.3 Relationship between bit velocity and bit change absolute probability

在粒子群算法尋優(yōu)的過程中用vi表示速度，能夠?qū)αＷ拥奈恢煤头较蛴幸欢ㄓ绊懀顾惴ㄔ谥付ǖ乃阉鞣秶鷥?nèi)進行搜索.假設(shè)算法的進化迭代視為一個自適應(yīng)過程，則不斷的會有新粒子替代粒子xi的位置，并且根據(jù)vi進行自我調(diào)節(jié).在進行每一次迭代時，群體經(jīng)驗的最優(yōu)解是粒子移動的方向，粒子群算法是有目的的尋找最優(yōu)解.而二進制粒子群算法中，vi表示一種可能的概率性，粒子的每維分量的位置取值可能以 s igm(vi+1)的概率取 1，或者以 1 -sigm(vi+1)的概率取0，其位發(fā)生變化概率為

分析得出，當(dāng)速度越趨近于 0時，其位發(fā)生改變的概率越高.粒子在尋找最優(yōu)解的過程中，粒子越來越靠近最優(yōu)粒子，即速度在不斷趨近于 0時，此時位發(fā)生改變的概率應(yīng)該越小，而二進制粒子群算法反而越來越大，如此必然影響算法的尋優(yōu)能力.

本文提出的算法基于二進制粒子群算法的尋找最優(yōu)解模式進行改進，粒子速度作為粒子位置的修正項，應(yīng)當(dāng)充分考慮粒子之間的此種導(dǎo)向作用，所以在對二進制粒子群算法進行改進中，速度迭代公式維持不變，速度歸一化公式sigm函數(shù)以及位置迭代公式改進為

改進后的新sigm函數(shù)與vi關(guān)系如圖4所示，當(dāng)速度的絕對值越來越大時，位改變的概率也越來越大；反之，當(dāng)速度趨近于 0時，位改變的概率越來越小.由此得出，改進后的函數(shù)遵循二進制粒子群算法的尋優(yōu)模式，更有利于全局最優(yōu)解的搜索.

圖4 新sigm函數(shù)與vi的關(guān)系Fig.4 New relationship between sigm function and vi

3 仿真實驗

為了驗證本文所提模型以及算法的有效性，選擇開源的云仿真CloudSim平臺對優(yōu)化算法進行仿真驗證.采用 Montage和 CyberShake作為測試用例.軟件安裝時間為 10s，帶寬 B為 10MB/s，虛擬機的加載時間為 30s，采用 Amazon EC2提供的虛擬機價格，它是基于按小時計費原則.本文提出的改進二進制粒子群算法與基本二進制粒子群算法分別進行任務(wù)完成時間和花費兩方面的比較與分析.

Montage 100測試用例隨迭代次數(shù)增加完成時間的變化趨勢測試結(jié)果如圖5所示.測試用例為 100時，與未經(jīng)改進的算法相比，改進的二進制粒子群算法的趨勢平緩，時間變化比較穩(wěn)定，且所用時間相對少.當(dāng)?shù)螖?shù)為90次時，開始收斂.

圖5 Montage測試用例任務(wù)數(shù)為100時算法的完成時間Fig.5 Algorithm completion time for the Montage test case with 100 tasks

Montage 100測試用例隨迭代次數(shù)增加所需費用的變化趨勢測試結(jié)果如圖6所示.當(dāng)任務(wù)數(shù)為 100時，與未經(jīng)改進的算法相比，改進的二進制粒子群算法的趨勢較平緩，且費用相對少.

圖6 Montage測試用例任務(wù)數(shù)為100時算法所需費用Fig.6 Algorithm completion cost for the Montage test case with 100 tasks

CyberShake 100測試用例隨迭代次數(shù)增加完成時間的變化趨勢和隨迭代次數(shù)增加所需費用的變化趨勢測試結(jié)果如圖7和圖8所示.與未經(jīng)改進的算法相比，改進的二進制粒子群算法所需的完成時間和費用都優(yōu)于未改進的算法.

圖7 CyberShake測試用例任務(wù)數(shù)為 100時算法的完成時間Fig.7 Algorithm completion time for the CyberShake test case with 100 tasks

圖8 CyberShake測試用例任務(wù)數(shù)為100時算法所需費用Fig.8 Algorithm completion cost for the CyberShake test case with 100 tasks

綜合分析，本算法對不同的工作流具有普適性，在不同的工作流上都體現(xiàn)了優(yōu)化作用.本算法對租賃成本的優(yōu)化效果更為明顯，而對于完成時間的優(yōu)化略微不明顯.分析原因是由于本算法對租賃成本的優(yōu)化是越低越好，而對完成時間的優(yōu)化是盡量小于截止時間.

Montage 100測試用例在迭代次數(shù)相同且任務(wù)數(shù)不同時，時間和費用的變化趨勢如圖9和圖10所示.當(dāng)?shù)螖?shù)相同時，改進的二進制粒子群算法隨著任務(wù)數(shù)量的增加，完成時間和費用都優(yōu)于未經(jīng)改進的二進制粒子群算法.

圖9 不同任務(wù)數(shù)對應(yīng)的完成時間Fig.9 Completion time for different tasks

圖10 不同任務(wù)數(shù)對應(yīng)的所需費用Fig.10 Costs of different tasks

4 結(jié) 語

針對二進制粒子群算法不能收斂于粒子的全局最優(yōu)位置的問題，本文對粒子的更新公式進行了修改，提出了一種基于改進的二進制粒子群的任務(wù)調(diào)度算法.實驗結(jié)果表明，經(jīng)過改進的二進制粒子群算法能得到很好的收斂，具有普適性，所得最優(yōu)解具有更低的調(diào)度時間和費用，提高了資源利用率.在相同的條件設(shè)置下，該算法優(yōu)于傳統(tǒng)的二進制粒子群算法.

致謝：本研究獲得天津教委項目(2017KJ035，2018KJ105)資助.