基于交換改進粒子群算法的云計算任務調度

陳俊仁 郭一晶

(廈門大學嘉庚學院信息科學與技術學院 福建 漳州 363105)

0 引 言

云計算作為一種新型的計算模式,已被互聯網用戶廣泛使用。它是按需為用戶動態整合不同計算機虛擬資源以提供數據處理的計算服務系統。對用戶而言,其關注的是云計算的服務質量。調查發現,云計算的服務質量最大程度取決于計算服務系統完成用戶所提交的任務的耗費時間。所以,提高任務的處理速度是用戶最關心的問題。此問題的關鍵就是尋找一種高效的調度方案使得用戶提交的任務處理時間盡量短,實質為云計算的任務調度,屬于一種組合優化問題。文獻[1]已證明云計算任務調度問題是一個非確定性多項式(Non-deterministic Polynomial,NP)難題。近年來一些學者已采用群體智能算法對該問題進行求解。文獻[2]采用遺傳算法并結合啟發式規則求解多優先隊列分布式計算系統的任務調度問題,實驗證明該方法可以有效獲得可行解,但算法過于復雜,實現難度較大。文獻[3]針對基本蟻群算法自身存在的缺陷,設計一種改進蟻群算法,該算法可以減少云計算中任務執行的總完成時間,但算法的迭代過程過于繁雜,其空間復雜度增加。文獻[4]提出了一種改進螢火蟲算法的云計算作業調度機制,實驗證明該方法可以有效減少作業的執行時間,但其目標僅僅針對作業的完成時間,并未考慮資源的使用情況。然而,隨著云計算的需求量日益增多,調度方案不僅要考慮如何快速完成多用戶提交的云任務,而且還應該關注計算資源的利用率。文獻[5]設計一種改進的負載均衡蜜蜂算法,仿真實驗說明該算法可以有效減少任務的執行時間并提升資源的負載均衡,但蜜蜂算法自身存在進化后期收斂速度慢、共享機制低效等缺點。文獻[6]結合資源的負載均衡和任務的執行時間,設計出一種改進的禁忌搜索啟發式調度策略,但算法的整體啟發規則較為復雜,操作相對煩瑣。文獻[7]提出了一種以任務總完成時間、任務平均完成時間和資源負載均衡為目標的遺傳算法,實驗結果證明算法有效,但因為編碼問題,算法進化過程的操作過于繁雜,且可能陷入局部最優。與此同時,粒子群算法(PSO)在多個領域已被證明具有記憶能力、參數少、收斂速度快、實現簡單等特點[8-10],并且在云計算任務調度問題上也得到了應用。文獻[11]設計了一種針對云任務調度問題的小生境粒子群算法,實驗結果表明該算法可縮短任務執行時間并使資源負載均衡。

基于以上考慮,本文根據云計算任務資源分配問題的特點,對基本的交換粒子群算法進行改進。引入進制編碼,在其基礎上重新定義運算法則,加入自適應概率調整,改進其適應度函數,綜合考慮任務完成時間和資源負載均衡等指標,提出了一種新的云計算任務調度算法。

1 云計算任務調度描述

1.1 問題定義

現今,主流的云計算平臺大部分采用Map/Reduce的工作方式。該方式適用于處理大規模的數據,可將用戶請求的大任務拆分成若干個子任務,再根據指定的策略去調度合適的資源來處理計算這些子任務。換言之,云計算任務調度問題可理解為調度中心調度p個虛擬資源來處理計算q個子任務,即建立虛擬資源與任務之間的映射,使其完成后達到任務總處理時間最少,資源利用率最高。

為簡化調度處理流程,現對云計算平臺中用戶提交的任務及其提供的資源作如下假設:

1) 拆分后的子任務之間無前后執行依賴關系,并且各子任務是相互獨立;

2) 一個子任務只由一個虛擬資源連續處理,不考慮中斷;

3) 拆分后的子任務數量遠遠多于平臺所提供的資源數量,并且資源處理任務的成本可知。

云計算任務調度的過程如圖1所示。

圖1 云計算任務調度過程

1.2 任務調度模型

云計算任務調度是由子任務集合、虛擬資源集合以及子任務與虛擬資源之間分配關系的集合構成。可表示為:

D=(ST,VR,MAP)

式中:D表示一個云計算任務調度方案,ST為調度方案D中子任務的集合,VR是調度方案D中虛擬資源的集合,MAP是調度方案D中子任務與虛擬資源之間分配關系的集合。

子任務集合ST表示為ST={st1,st2,…,stq},其中第i個任務表示為sti(1≤i≤q,i∈Z)。虛擬資源集合VR表示為VR={vr1,vr2,…,vrp},vrj(1≤j≤p,j∈Z)表示第j個虛擬資源。子任務與虛擬資源之間分配關系的集合MAP表示為MAP={…,, …},其中,(1≤i≤q,1≤j≤p,i∈Z,j∈Z)表示第i個子任務分配到第j個虛擬資源處理。

另外,任務的衡量指標一般采用MI(百萬條指令數),本文令Numberi表示子任務sti的待執行機器指令條數,即子任務的大小。資源的指令執行速度采用MIPS(每秒執行的百萬條指令數)衡量,Speedj代表虛擬資源vrj的計算性能。ti,j代表子任務sti在虛擬資源vrj上的執行時間。

ti,j=Numberi/Speedj

1≤i≤q,1≤j≤p,i∈Z,j∈Z

(1)

再者,p個虛擬資源處理計算q個子任務的期望計算時間ETC(Expeeted Time to Compute)[12-13]可用矩陣T表示,該矩陣是一個q×p的矩陣,如下:

虛擬資源vrj的執行時間ExeTime為該資源處理計算其分配的所有任務的執行時間之和。

(2)

式中:sti→vrj,sti∈ST表示虛擬資源vrj處理的所有任務,k代表在該資源上執行的任務總數。根據上文的假設,以及各虛擬資源并行計算的特點,可得任務調度方案D的完成時間為最晚完成任務的虛擬機的執行時間[13],表示方式如下:

Makespan=max{ExeTime(j)|j∈Z,1≤j≤p}

(3)

云計算任務調度追求的目標應是尋找一種使總完成時間Makespan最小的調度方案。

2 改進粒子群算法

2.1 離散粒子群算法

粒子群算法(PSO)是由Eberhart和Kennedy在1995年模擬鳥類群體覓食設計出的一種自適應全局優化搜索算法。基本粒子群算法較適合于求解連續空間優化問題,但對于離散空間優化問題,該算法并不適用。2000年Clerc[14]提出了一種以交換離散值向量為基礎的粒子群算法,用于求解離散空間優化問題,已被證明成功求解旅行商問題(TSP)。對于本文研究的云計算任務調度問題來說,其結果亦分散在解空間,本質上也屬于離散空間組合優化問題,性質與TSP問題相似,但又有區別。TSP問題的解為所有城市訪問順序的排列組合,而云計算任務調度問題的解則為子任務與虛擬資源的映射組合。另外,云計算任務調度求解過程需要考慮資源的負載均衡指標。因此,本文將結合所研究的調度問題特點在基本的交換粒子群算法上做了相應的改進。

2.2 粒子編碼

在基本的交換粒子群算法中,粒子是采用整數編碼方式,用不同的整數代表不同的城市,并且每個城市只被訪問一次,即訪問次序與城市是一一對應。然而,在本文研究的問題中,同一個虛擬資源可以執行多個不同的子任務,為一對多的關系。由此可見,整數編碼并不適合本文的問題,因此本文結合云計算任務調度的特點,采用“進制編碼”對粒子的編碼方式進行改進。

對于任何包含q個待處理子任務的云環境來說,本文按1～q的順序對這q個子任務進行編號。現假設數據中心代理有p個虛擬資源,且有q個子任務待計算處理,則本文按表1所示的方式進行p進制編碼。

表1 粒子的進制編碼

其中,虛擬資源的編號為1至p的整數。一組1至p的組合序列代表該問題解空間里的一個解,即表示一種云計算任務調度方案。

2.3 基于交換的運算法則

傳統粒子群算法中的粒子速度和位移更新公式并不適合求解離散空間組合優化問題,故本文采用基于交換的運算。然而,運用原始的交換操作求解本文的問題會存在一定缺陷。因為,不同編號的子任務可能被分配到同一個虛擬資源上執行,此時編碼序列中兩個任務對應位置上的進制數相同,所以互換位置后編碼序列未發生任何改變,即粒子保持不動,從而降低算法的收斂速度。為解決此問題,本文提出的改進算法將重新定義交換子和交換序,并用其來表示粒子的飛行速度。其中,交換子表示在一種調度方案中互換兩個子任務的處理虛擬資源,且要求虛擬資源不為同一個,即交換子對應的兩個虛擬資源編號不能相等;交換序則由一個或多個交換子組成。為了實現離散值向量間的交換且同時保留粒子群算法思想,本文采用如式(4)所示的粒子速度更新公式,式(5)為粒子的位置更新公式。

(Pi-Xi)⊕β×(Gb-Xi)

(4)

(5)

2.4 適應度函數

在粒子群算法中,適應度函數是衡量粒子離目標遠近的標準,一般稱之為粒子的適應值。種群中第i個粒子的適應值記為f(Xi)。

由于實際的云計算環境中,不同虛擬資源的計算能力存在一定差異,經常出現算力高的虛擬資源負載過高,其任務隊列中等待任務數量過多,而其他虛擬資源則處于空閑狀態,因此造成資源使用率不高且負載不均衡,甚至任務的總完成時間較長。為了避免該現象發生,本文對適應度函數做了相應改進,在評價粒子適應值時引進負載均衡指標,即給虛擬資源分配任務時既要追求完成時間短,同時要考慮各虛擬資源的負載情況。

虛擬資源vrj的負載Loadj此處定義為預分配到其上所有子任務的預期執行時間,Loadj越大,表明虛擬資源vrj的負載越高,結合式(2)可得:

Loadj=ExeTime(j)

(6)

定義所有虛擬資源的預期執行時間均值為Loadavg,公式如下所示:

(7)

式中:p為虛擬資源的個數。

對任意云計算任務調度方案的負載均衡評價指標LB定義為所有虛擬資源的預期執行時間的標準差,公式如下:

(8)

其中,調度方案的負載均衡評價指標LB越大,表明該調度方案的負載均衡情況越差。

結合式(3)和式(8),本文定義的適應度函數為:

f(X)=ω1Makespan+ω2BL

(9)

式中:ω1和ω2為權重值,ω1+ω2=1。適應度函數f(X)越小,說明粒子X對應的調度方案越好。

4.1.1 餐飲服務單位的食品安全管理制度齊全，確保食品原料新鮮、加工過程生熟分開，食品燒熟煮透，其加工時食品中心溫度應不低于70℃。主要食品安全管理制度應包括但不僅限于以下各項：食品安全崗位責任制；從業人員健康管理制度；從業人員培訓管理制度；加工經營場所清潔制度；設施設備清潔、消毒和維修保養制度；食品采購索證索票制度；食品進貨查驗和臺賬記錄制度；餐廚廢棄物處置管理制度；食品安全突發事件應急處置方案；投訴受理制度等相關制度。

2.5 自適應概率調整

云計算任務調度的求解比TSP問題復雜很多。首先,要求各個虛擬資源保持負載均衡;其次,子任務在不同算力的虛擬資源中執行時間差別較大,執行子任務的虛擬資源更換后,可能引起任務的總完成時間發生變化,導致尋找負載均衡且時間短的調度方案難度加大。與此同時,基本交換粒子群算法容易出現粒子聚集現象,導致算法在進化后期陷入局部最優的可能性增加。為此本文引進一種自適應的調整概率對粒子群算法做了改進。算法根據此概率值決定是否對粒子當前所處的位置序列做調整操作。調整過程如下:在粒子的位置序列中隨機挑選兩個不在同一臺虛擬機上計算的子任務,然后互換這兩個子任務的處理虛擬機。若互換后該粒子的適應值低于當前種群最優值,則認為此次調整操作有效并把該位置標記成種群當前最優位置。此外,該概率值是根據算法迭代次數、前一代調整概率以及前一代調整的成功次數動態變化,公式如下:

λ=b·[1-nsuc/(apt·m)]

(10)

apt+1=r^(1-t/G)λ

(11)

式中:ap表示調整概率;m表示種群大小;nsuc表示前一代調整的成功次數;b是常數,本文取值為3;λ為調整權重;t為當前的迭代數;G為總迭代次數(進化代數);r∈[0.2,0.5]。從式(10)和式(11)可以看出,迭代初期ap值較小以保持算法的收斂速度;迭代后期ap值增大,交換操作的次數將逐步增多,以此保持粒子的多樣性,從而降低陷入局部最優的概率。

2.6 算法流程

本文提出的基于交換的改進粒子群算法,主要包括初始化種群、粒子移動、選擇和自適應調整四個過程。具體操作步驟如下。

Step1初始化:輸入算法參數,并在問題解空間里隨機產生m個粒子的位置序列和速度交換序。

Step2評價粒子:通過適應度函數評價每一個粒子的適應值。

Step3更新極值:1) 比較粒子的適應值和個體本身歷史最優值,若前者優于后者,則將個體自身歷史最優位置替換成粒子當前的位置序列;2) 比較粒子的適應值和種群當前最優值,如果前者好于后者,則將群體最優位置替換成粒子當前的位置序列。

Step5調整:根據調整概率調整粒子的位置序列,如果新的適應值比種群當前最優值更優,則把種群最優位置設為粒子調整后的位置序列。

Step6終止:重復Step2～Step5,直至滿足算法終止條件。

Step7輸出:輸出種群最優位置對應的調度方案。

3 仿真實驗與分析

為了驗證基于交換的改進粒子群算法(Improved Discrete PSO,IDPSO)對云計算任務調度的有效性和可行性,本文使用開源的CloudSim云仿真平臺進行實驗,并在同等實驗條件下與Min-Min調度算法、基本的離散粒子群算法(PSO)和基于交換運算法則的粒子群算法(Discrete PSO,DPSO)進行對比實驗。

3.1 實驗環境

仿真實驗環境具體信息如下:處理器為Inter(R) Core(TM) i5-6267U CPU @ 2.90 GHz,內存為8 GB,操作系統為Windows 10,軟件平臺為Eclipse、CloudSim,編程語言為Java。

CloudSim是一款由Java編寫的基于事件的仿真框架,可在一臺主機上模擬大規模的集群及任務調度,只需在框架中實現其調度算法并重寫相關類,即可完成仿真工作。另外,IDPSO本身具有粒子群算法參數少、迭代流程簡便的特點,并且本文采用的進制編碼、交換子、交換序及交換操作均可使用基本類型數組存儲與運算,總體上實現相對簡便。

3.2 參數設置

在云仿真平臺中設置虛擬資源的個數為10,其計算能力參數范圍為1 024～2 048。子任務數量范圍為[100,400],子任務的待執行機器指令條數范圍為1 000～10 000。

上述算法中設置的主要參數有,種群大小m為50,慣性權重ω為0.85,學習因子c1和c2均為2,ω1和ω2分別為0.6和0.4。

3.3 結果分析

實驗分為4種不同子任務數,任務數分別為100、200、300和400,與之對應的迭代數分別為500、700、1 000和1 500。每組各做50次獨立重復實驗,取其平均值。實驗結果如圖2和圖3所示。

圖2 不同任務數的適應度函數值對比

圖3 不同任務數在不同迭代次數下取得的適應值對比

圖2為Min-Min算法、PSO、DPSO和IDPSO在相同仿真環境和參數下的適應度函數值對比圖。由圖可知,在任務數為100和200的情況下,IDPSO取得的結果最好,但其優勢仍不夠明顯。在任務數為300和400時,IDPSO體現出更好的性能,其得到的適應度函數值比DPSO低更多,且都好于Min-Min算法和PSO。特別在400個任務時,其優勢更加突出。因此可得,IDPSO總體上取得的結果都優于其他算法,隨著任務數增加,其效果越明顯,即更適合任務數較多的場景。換句話說,IDPSO在任務數較多時更能找到任務總完成時間短、資源負載均衡的調度方案。

圖3中的實驗是針對基于交換運算法則的粒子群算法改進前后的收斂對比。可以看出,不同任務數的求解過程中,IDPSO的收斂速度均比DPSO快,在任務數較少時效果較為明顯。由此可見,本文采用的進制編碼和重新定義的粒子更新運算法則具有一定的優勢。同時可得,算法在迭代初期自適應調整概率較小時,不會導致收斂速度變慢。還有,從算法取得的結果來看,DPSO尋優過程較易陷入局部最優,加入自適應概率調整后,IDPSO收斂速度在任務數多的情況下與DPSO相當,但其得到的適應度函數更優,可見自適應概率調整可有效促使IDPSO跳出局部最優。另外,從圖3亦可發現IDPSO在不同任務數下的收斂適應值均更小,可見具有魯棒性。由此可得,IDPSO在云計算任務調度中表現出更快的收斂速度,以及更強的全局搜索能力。

4 結 語

本文在交換的粒子群算法基礎上,通過重新定義交換子及粒子的運算法則,引入自適應概率調整,并且以任務調度的總完成時間和資源的負載情況為適應度函數來衡量調度方案的優劣,以此進行云計算任務調度方案優化。仿真實驗采用開源的CloudSim平臺,并在此平臺上進行實例分析。實驗結果表明本文提出的算法能夠有效地找出云計算任務調度結果,以完成較好的任務調度。通過多組實驗對比,可以得出改進后的算法具有收斂速度快和魯棒性強等特點。然而,本文提出的算法并未對速度更新公式中的幾個參數做動態調整,后續的工作中可以對這些參數進行自適應改進,以期更好地提升算法性能,尋找到更優的調度方案。另外,在實際云計算應用中,不僅要考慮任務的總完成時間,還應綜合考慮計算成本、帶寬、能耗等因素,這將是今后研究的重點。