基于強化學習和蟻群算法的協(xié)同依賴多任務(wù)網(wǎng)格集群調(diào)度

張新華

(太原學院計算機系,山西 太原 030012)

?

基于強化學習和蟻群算法的協(xié)同依賴多任務(wù)網(wǎng)格集群調(diào)度

張新華

(太原學院計算機系,山西 太原 030012)

摘要：針對現(xiàn)有的網(wǎng)格集群資源調(diào)度方法所具有的任務(wù)調(diào)度時間長、系統(tǒng)負載不均衡和CPU利用率低的缺點，提出了一種基于強化學習和蟻群算法結(jié)合的協(xié)同依賴型任務(wù)調(diào)度方法.首先對調(diào)度目標模型進行了定義，然后采用改進的強化學習Sarsa算法實現(xiàn)集群資源的初始分配，以最小化任務(wù)調(diào)度時間為目標，尋求最優(yōu)調(diào)度方案，并保存調(diào)度方案對應(yīng)的Q值.在此基礎(chǔ)上，設(shè)計了一種改進的蟻群算法實現(xiàn)網(wǎng)格集群資源到任務(wù)分配的進一步尋優(yōu)，在不同資源節(jié)點上的概率選擇上考慮了Q值因素，從而實現(xiàn)網(wǎng)格環(huán)境下的協(xié)同依賴多任務(wù)集群調(diào)度.在Gridsim工具下進行仿真試驗，結(jié)果表明新方法能有效地實現(xiàn)協(xié)同依賴多任務(wù)網(wǎng)格集群調(diào)度，且較其他方法而言，具有任務(wù)調(diào)度時間少、CPU利用率高和負載均衡的優(yōu)點，是一種適合網(wǎng)格環(huán)境的可行任務(wù)調(diào)度方法.

關(guān)鍵詞：集群調(diào)度；資源分配；蟻群算法；強化學習

網(wǎng)格計算[1]是將各類資源連接而形成的共享資源系統(tǒng)，能整合網(wǎng)絡(luò)異構(gòu)資源，實現(xiàn)動態(tài)和多制度的虛擬組織的資源共享，并采用共享資源協(xié)同工作的形式為用戶提供服務(wù)[2,3].

網(wǎng)絡(luò)資源任務(wù)分配是網(wǎng)格計算研究的重點課題，主要是致力于實現(xiàn)在滿足用戶需求的前提下，將網(wǎng)格任務(wù)分配到合適的計算資源上，使得任務(wù)的執(zhí)行能盡可能快且資源利用率能足夠高[4,5].

網(wǎng)格任務(wù)資源調(diào)度已被證明是一個NP難題，經(jīng)典的網(wǎng)格調(diào)度方法主要是：Min-min方法[6]和Max-min方法[7].

相比Min-min方法，Max-min方法的優(yōu)勢在于：每次選擇具有最大最小完成時間的任務(wù)進行調(diào)度，能較大程度地改善網(wǎng)絡(luò)負載均衡和提高資源利用率.

為了克服Max-min方法和Min-min方法的不足，文獻[8]設(shè)計了一種基于小生境和遺傳算法的網(wǎng)格任務(wù)調(diào)度，首先描述了依賴型任務(wù)調(diào)度DAG模型，然后采用小生境預(yù)選擇機制對種群個體進行選擇，從而提高算法的全局尋優(yōu)能力.文獻[9]設(shè)計了一個單層樹型網(wǎng)格周期性調(diào)度方法，為網(wǎng)格獨立任務(wù)建立線性規(guī)劃模型，然后通過整數(shù)線性規(guī)劃求解，將大規(guī)模的任務(wù)調(diào)度問題轉(zhuǎn)換為一個周期內(nèi)的任務(wù)調(diào)度.文獻[10]設(shè)計了一種融合配方均勻設(shè)計與離散粒子群算法的任務(wù)調(diào)度策略，實現(xiàn)獨立任務(wù)優(yōu)化調(diào)度，產(chǎn)生分布均勻且較優(yōu)的Pareto解集.

上述工作在一定程度上克服了Max-min算法和Min-min算法的不足，具有重要的意義，但仍然存在著無法在線實時分配和分配效率不高的問題，為此，文中設(shè)計了基于強化學習和蟻群算法結(jié)合的任務(wù)在線分配算法，并通過實驗證明了其有效性.

1網(wǎng)格依賴任務(wù)模型

依賴型網(wǎng)格任務(wù)調(diào)度系統(tǒng)可以表示為一個六元組DAG={T,E}，T={t1,t2,…,tn}表示n個任務(wù)組成的任務(wù)集合，E={(ti,tj)}1≤i,j≤n表示任務(wù)依賴集，表明任務(wù)tj在ti執(zhí)行完成后才能執(zhí)行，無任何前驅(qū)的任務(wù)叫入口任務(wù)，無任何后繼任務(wù)的任務(wù)叫做出口任務(wù).每個任務(wù)ti對應(yīng)的指令數(shù)為ci，每條邊的數(shù)據(jù)傳輸量表示為dij，對于整個任務(wù)集都有一個入口任務(wù)tin和一個出口任務(wù)tout.

當任務(wù)集無統(tǒng)一的入口任務(wù)時，可以建立一個虛擬的入口任務(wù)，并將其指向所有入度為0的節(jié)點.

當任務(wù)集無統(tǒng)一的出口任務(wù)時，可以建立一個虛擬的出口任務(wù)，并將出度為0的節(jié)點都指向虛擬的出口任務(wù).

一個依賴型有向無環(huán)圖DAG可以表示為如圖1所示：

圖1　依賴型任務(wù)對應(yīng)的DAG

定義1 任務(wù)執(zhí)行時間：對于給定的任務(wù)ti∈T，其分配到某節(jié)點PEj上的運行時間為PE(ti)，可以通過下式計算：

(1)

其中，mi為任務(wù)ti的計算量，spe(j)為節(jié)點PEj的處理速度.

定義2 數(shù)據(jù)傳輸時間：采用ti j表示任務(wù)ti和tj的數(shù)據(jù)傳輸時間，當兩個任務(wù)分配在同一個處理節(jié)點上時，傳輸時間為0，否則為數(shù)據(jù)傳輸量與兩個處理節(jié)點通信帶寬的比值，如下所示：

其他

(2)

定義3 任務(wù)入口路徑：對于任意任務(wù)ti∈T，其任務(wù)入口路徑為入口任務(wù)tin到達當前任務(wù)ti的最長路徑長度，即為In_pathi，可以通過下式計算：

(3)

定義4 任務(wù)出口路徑：對于任意任務(wù)ti∈T，其任務(wù)出口路徑為當前任務(wù)ti到出口任務(wù)tout的最長路徑長度，即為Out_pathi，可以通過下式計算：

(4)

定義5 最早開始時間：對于任意任務(wù)ti∈T，其最早開始時間是指其所有前驅(qū)任務(wù)的最早完成時間或其所分配的節(jié)點的最早空閑時間，記為starti(ti,PE(ti))：

starti(ti,PE(ti))=max{startj+tij+ti,startPE+tPE}

(5)

定義6最早完成時間：對于任意任務(wù)ti∈T，其最早完成時間是指將任務(wù)ti分配到處理機PE(ti)的最早完成時間：

finishi(ti,PE(ti))=starti+ti

(6)

2基于Sarsa算法的網(wǎng)格資源分配

2.1Sarsa算法

Sarsa算法是一種時間差分算法，它將樣本表示為四元組，即：

(7)

在式(7)中state1表示當前狀態(tài)，action1表示在當前狀態(tài)下采取的動作，reward表示當前狀態(tài)動作下的立即回報，state2表示下一個狀態(tài)，action2表示在下一個狀態(tài)時根據(jù)當前策略應(yīng)采取的動作.根據(jù)一個樣本四元組，可以獲得讓任一狀態(tài)動作對的Q值：

Q(x,u)=Q(x,u)+α(r+γQ(x',u')-Q(x,u))

(8)

2.2基于Sarsa算法的網(wǎng)格資源分配

以最大化Q值為目標，當Agent每成功完成一次任務(wù)分配時，獲得立即獎賞為1，當Agent完成最后一個任務(wù)分配時，并且優(yōu)于所有已有方案時，立即獎賞為100，否則為1.

算法為：

(1)初始化：任務(wù)集合X，動作集合U，狀態(tài)動作空間X×U，對于?(x,u)∈X×U，初始化Q0(x,u)=0，探索因子ε，折扣因子γ，學習率α，最大迭代次數(shù)T，最大情節(jié)數(shù)ET，每個情節(jié)中的最大步數(shù)ETS，當前狀態(tài)為x；

(2)當前情節(jié)數(shù)et=1；

(3)當前步數(shù)s=0；

(4)根據(jù)ε-greedy選擇動作u，得到x'和r；

(5)根據(jù)ε-greedy選擇狀態(tài)x'的動作u'；

(6)采用式(8)計算Q值；

(7)對探索因子ε的值進行衰減，并將下一個狀態(tài)賦給當前狀態(tài)x←x'，將下一個動作賦給當前動作u←u'；

(8)s=s+1，判斷當前情節(jié)et是否已經(jīng)到達最大步數(shù)而結(jié)束情節(jié)：

如果情節(jié)結(jié)束，則當前情節(jié)數(shù)et=et+1，并轉(zhuǎn)入(4)繼續(xù)執(zhí)行.

否則，算法迭代次數(shù)t=t+1，判斷t的值，如果當前迭代次數(shù)小于T，則轉(zhuǎn)入(4)繼續(xù)執(zhí)行； 否則算法結(jié)束，根據(jù)學習的Q值獲取最優(yōu)的任務(wù)動作分配方案.

(9) t=t+1，根據(jù)情節(jié)數(shù)作判斷：

如果情節(jié)數(shù)達到最大值，則算法結(jié)束，輸出結(jié)果.

否則轉(zhuǎn)入(4)繼續(xù)開始運行.

3基于并行蟻群算法的網(wǎng)格資源分配

3.1傳統(tǒng)的蟻群算法

蟻群算法由意大利學者M.Dorigo等人于1991年創(chuàng)立，是一種基于種群尋優(yōu)的啟發(fā)式優(yōu)化算法，具有強大的并行分布式計算能力，目前已經(jīng)先后用于旅行商TSP問題(Traveling Salesman Problem)和資源二次分配問題等.

3.2基于并行蟻群算法的集群調(diào)度

算法輸入：任務(wù)隊列集TaskS、集群節(jié)點集P，蟻群Ant，蟻群中的螞蟻數(shù)量K，最大迭代次數(shù)T，任務(wù)緩存隊列Que，值α和β，信息素揮發(fā)率η，調(diào)節(jié)因子μ；

算法輸出：任務(wù)和資源分配的一個1*n的向量；

初始化：t=1.

步驟1：根據(jù)式(6)計算所有任務(wù)的最早完成時間，根據(jù)最早完成時間對所有任務(wù)排序，并按照從早到晚的順序依次加入等待隊列Que.

步驟2：K只螞蟻從任務(wù)等待隊列Que中選取個K個任務(wù)，如果Que中的任務(wù)數(shù)量小于K，則派出與隊列中任務(wù)數(shù)相同的螞蟻數(shù).

步驟3：根據(jù)式(9)對t+1時刻集群中資源節(jié)點進行信息素τij(t+1)更新.

τij(t+1)=(1-ρ)*τij(t)+ρΔτij(t)

(9)

在式(9)中，ρ表示信息素揮發(fā)因子和τij(t)分別表示t時刻時路徑ij上的信息素.Δτij(t)為信息素的局部增量：

(10)

在式(10)中，comij為路徑ij的通信時間.

步驟4：根據(jù)式(11) 選擇每個螞蟻的任務(wù)進行集群資源節(jié)點.

others

(11)

步驟5：對路徑的局部信息素按公式(12)進行更新.

(12)

步驟6：判斷任務(wù)等待隊列是否為空，如果為空，則轉(zhuǎn)入步驟7，否則保存當前K個任務(wù)的調(diào)度方案，并轉(zhuǎn)入步驟2.

步驟7：t=t+1，并判斷當前迭代次數(shù)t等于最大迭代次數(shù)T：

如果等于則算法結(jié)束，則輸出所有任務(wù)對應(yīng)的節(jié)點調(diào)度方案；否則，轉(zhuǎn)入步驟2繼續(xù)運行.

4實驗分析

4.1實驗環(huán)境和參數(shù)設(shè)置

采用GridSim進行仿真實驗，集群數(shù)為3，為Cluster1、Cluster2和Cluster3，三個集群對應(yīng)的初始節(jié)點數(shù)分別為8，10和13，每個節(jié)點的處理器數(shù)為4，因此，三個集群對應(yīng)的資源總數(shù)分別為32、40和52，用戶數(shù)分別為10、8和9，每個用戶的任務(wù)數(shù)分別為2、4和2.

參數(shù)設(shè)置如下：Sarsa算法中探索因子ε=0.01，折扣因子γ=0.8，學習率α=0.1，最大迭代次數(shù)T=00，最大情節(jié)數(shù)ET=50，每個情節(jié)中的最大步數(shù)ETS=1000.

蟻群中的螞蟻數(shù)量K=10，最大迭代次數(shù)T=50，b=0.4，信息素揮發(fā)率η=0.3，調(diào)節(jié)因子μ=0.6，權(quán)值α和β分別為0.6和 0.4，最大迭代次數(shù)設(shè)置為50次，信息素的揮發(fā)率η=0.4，調(diào)節(jié)因子μ=2.

將文中方法與文獻[9]和文獻[10] 進行比較，從所有任務(wù)的跨度、CPU的利用率以及負載均衡度三個方面進行比較.

4.2調(diào)度時間比較

三種方法對應(yīng)的任務(wù)調(diào)度時間仿真結(jié)果如圖1所示：

圖2　任務(wù)調(diào)度時間對比

從圖2中可以看出，文中在任務(wù)數(shù)從0增加到60個的過程中，文獻[9]方法獲得任務(wù)調(diào)度時間為104.29，文獻[10]方法獲得任務(wù)調(diào)度時間為87.86，文中方法得到的任務(wù)調(diào)度時間為72.43.文中方法較文獻[9]方法減少了30.55%，文中方法較文獻[10]方法減少了17.56%.

4.3CPU利用率

圖3　CPU利用率對比

從圖3中可以看出，文中方法的資源利用率在前20個任務(wù)時候基本與文獻[10]方法相同，但是在20個任務(wù)后，資源利用率顯著提高，較文獻[9]方法提高了28.41%，較文獻[10]方法提高了8.92%.

4.4負載均衡度

負載均衡離差反應(yīng)了系統(tǒng)的負載均衡程度，其值可以通過下式計算：

(13)

從圖4可以看出，文中方法的φ平均值為0.383，而文獻[9]方法對應(yīng)的負載均衡離差為0.590，文獻[10]方法對應(yīng)的負載均衡離差為0.434.

圖4　負載均衡離差

5結(jié)語

針對網(wǎng)格復(fù)雜環(huán)境下的傳統(tǒng)調(diào)度算法具有的任務(wù)調(diào)度時間長和CPU利用率不高的缺點，提出了一種基于強化蟻群算法的網(wǎng)格資源分配算法.首先采用Sarsa算法實現(xiàn)網(wǎng)格任務(wù)資源分配，然后采用并行的蟻群算法進行尋優(yōu)，實現(xiàn)了網(wǎng)格任務(wù)的集群資源節(jié)點調(diào)度.通過仿真實驗證明，文中方法能有效地實現(xiàn)任務(wù)的調(diào)度，具有CPU利用率高、調(diào)度時間短和負載均衡能力強的優(yōu)點，具有較強的可行性.

參考文獻：

[1]Foster I, Kesselman C, Tuecke S. The anatomy of the grid: Enabling scalable virtual organizations [J]. International J Super Computer Application, 2001,(3):200-222.

[2]馬艷,龔斌,鄒立達. 網(wǎng)格環(huán)境下基于復(fù)制的能耗有效依賴任務(wù)調(diào)度研究[J].計算機研究與發(fā)展,2013,(2):420-429.

[3]NettoMAS,BuyyaB.Reschedulingco-allocationrequestsbasedonflexibleadvancereservationsandprocessorremapping[A].Proceedingsof9thGridComputingConference[C]. 2008:144-150.

[4]王觀玉．網(wǎng)格計算中任務(wù)調(diào)度算法的研究和改進[J].計算機工程與科學，2011，(10):186-187.

[5]LiJY，QiuMK，MingZ，etal．OnlineoptimizationforschedulingpreemptabletasksonIaaScloudsystems[J]．JournalofParallelandDistributedComputing，2012,(2):666 -677.

[6]BraunTD,SiegelHJ,BeckN.Acomparisonofelevenstaticheuristicsformappingaclassofindependenttasksontoheterogeneousdistributedcomputingsystems[J].JournalofParallelanddistributedcomputing, 2001,(6):810-837.

[7]MorenoRJ.Schedulingandresourcemanagementtechniquesindynamicsgridenvironment[A].Proceedingsof8thInt’lConfonAdvancedComputingandCommunications[C].Cochin:ADCOM, 2000.

[8]卜憲憲. 基于小生境和自適應(yīng)遺傳算法的網(wǎng)格任務(wù)調(diào)度優(yōu)化研究[J]. 計算機測量與控制，2013, (2):470-479.

[9]王振宇, 李照瑜. 單層樹型網(wǎng)格下獨立任務(wù)的周期性調(diào)度[J]. 軟件學報, 2013,(2):378-390.

[10]蒲汛,彭喜化,于顯平,等.基于均勻離散PSO算法的多QoS網(wǎng)格任務(wù)調(diào)度策略[J]. 控制與決策,2013，(6):808-814.

(責任編校：晴川)

Grid Cluster Cooperative Dependent Multi Task Scheduling Method Based on Reinforcement Learning and Ant Colony Algorithm

ZHANG Xinhua

(Department of Computer Science，Taiyuan College，Taiyuan Shanxi 030012，China)

Abstract：Current grid cluster resource scheduling method has the disadvantages of long scheduling time, unbalance system load and low CPU utilization rate. A cooperative dependent task scheduling method is proposed, which is based on reinforcement learning and ant colony algorithm. Firstly, the scheduling goal model is defined, then the improved reinforcement learning Sarsa algorithm is used to allocate the task resource, with minimizing the task scheduling time as the goal to get the optimal scheduling method and save the Q value of scheduling method. Then an improved ant colony algorithm is introduce to realize the task allocation to the resource node. The experiment is operated in the Gridsim environment, and the result shows that the method in this paper can realize the cooperative dependent task cluster scheduling, and compared with other methods, it has less task scheduling time, higher CPU usage rate and higher load balance. Therefore, it is a feasible scheduling method suitable for grid environment.

Key Words：cluster scheduling; resource allocation; ant colony algorithm; reinforcement learning

中圖分類號:TP393

文獻標識碼：A

文章編號：1008-4681(2016)02-0050-04

作者簡介：張新華(1982— ),女,山西太原人, 太原學院計算機系講師，碩士.研究方向:計算機應(yīng)用技術(shù).

收稿日期：2015-12-31