張新華

(太原學(xué)院計(jì)算機(jī)系,山西 太原 030012)

?

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

張新華

(太原學(xué)院計(jì)算機(jī)系,山西 太原 030012)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

其他

(2)

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

(3)

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

(4)

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

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

(5)

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

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

(6)

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

2.1Sarsa算法

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

(7)

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

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

(8)

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

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

算法為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

初始化：t=1.

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

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

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

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

(9)

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

(10)

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

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

others

(11)

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

(12)

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

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

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

4實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

4.3CPU利用率

圖3　CPU利用率對比

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

4.4負(fù)載均衡度

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

(13)

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

圖4　負(fù)載均衡離差

5結(jié)語

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

參考文獻(xiàn)：

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

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

[4]王觀玉．網(wǎng)格計(jì)算中任務(wù)調(diào)度算法的研究和改進(jìn)[J].計(jì)算機(jī)工程與科學(xué)，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]. 計(jì)算機(jī)測量與控制，2013, (2):470-479.

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

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

(責(zé)任編校：晴川)

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

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

收稿日期：2015-12-31