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

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

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

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

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

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

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

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

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

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

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

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

2.1 生成初始種群

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

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

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

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

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

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

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

其中：a為虛擬機(jī)的租用周期，ci為虛擬機(jī)使用類型為i類時(shí)單個(gè)租用周期的單價(jià).

總費(fèi)用Ctotal為每個(gè)任務(wù)節(jié)點(diǎn)的費(fèi)用的累加之和.

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

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

2.3 二進(jìn)制粒子群算法及其改進(jìn)

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

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

為了防止sigm函數(shù)飽和，通常給vi+1的取值規(guī)定一個(gè)區(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ù)概率進(jìn)行的改變.位為 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時(shí)，位的絕對改變概率最大.經(jīng)分析得出以下結(jié)論：當(dāng)二進(jìn)制粒子群算法的粒子速度是 0時(shí)，位最有可能發(fā)生改變，不利于全局最優(yōu)解的搜索，此時(shí)的算法具有更強(qiáng)的隨機(jī)性，缺乏方向性.二進(jìn)制粒子群算法隨著迭代次數(shù)的增多，其隨機(jī)性更強(qiáng)了，不能收斂到全局最優(yōu)解.本文針對二進(jìn)制粒子群算法的這種情況進(jìn)行了改進(jìn).

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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

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