基于強化學習和蟻群算法的協同依賴多任務網格集群調度

張新華

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

?

基于強化學習和蟻群算法的協同依賴多任務網格集群調度

張新華

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

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

關鍵詞：集群調度；資源分配；蟻群算法；強化學習

網格計算[1]是將各類資源連接而形成的共享資源系統，能整合網絡異構資源，實現動態和多制度的虛擬組織的資源共享，并采用共享資源協同工作的形式為用戶提供服務[2,3].

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

網格任務資源調度已被證明是一個NP難題，經典的網格調度方法主要是：Min-min方法[6]和Max-min方法[7].

相比Min-min方法，Max-min方法的優勢在于：每次選擇具有最大最小完成時間的任務進行調度，能較大程度地改善網絡負載均衡和提高資源利用率.

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

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

1網格依賴任務模型

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

當任務集無統一的入口任務時，可以建立一個虛擬的入口任務，并將其指向所有入度為0的節點.

當任務集無統一的出口任務時，可以建立一個虛擬的出口任務，并將出度為0的節點都指向虛擬的出口任務.

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

圖1　依賴型任務對應的DAG

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

(1)

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

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

其他

(2)

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

(3)

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

(4)

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

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

(5)

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

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

(6)

2基于Sarsa算法的網格資源分配

2.1Sarsa算法

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

(7)

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

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

(8)

2.2基于Sarsa算法的網格資源分配

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

算法為：

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

(2)當前情節數et=1；

(3)當前步數s=0；

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

(5)根據ε-greedy選擇狀態x'的動作u'；

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

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

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

如果情節結束，則當前情節數et=et+1，并轉入(4)繼續執行.

否則，算法迭代次數t=t+1，判斷t的值，如果當前迭代次數小于T，則轉入(4)繼續執行； 否則算法結束，根據學習的Q值獲取最優的任務動作分配方案.

(9) t=t+1，根據情節數作判斷：

如果情節數達到最大值，則算法結束，輸出結果.

否則轉入(4)繼續開始運行.

3基于并行蟻群算法的網格資源分配

3.1傳統的蟻群算法

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

3.2基于并行蟻群算法的集群調度

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

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

初始化：t=1.

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

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

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

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

(9)

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

(10)

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

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

others

(11)

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

(12)

步驟6：判斷任務等待隊列是否為空，如果為空，則轉入步驟7，否則保存當前K個任務的調度方案，并轉入步驟2.

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

如果等于則算法結束，則輸出所有任務對應的節點調度方案；否則，轉入步驟2繼續運行.

4實驗分析

4.1實驗環境和參數設置

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

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

蟻群中的螞蟻數量K=10，最大迭代次數T=50，b=0.4，信息素揮發率η=0.3，調節因子μ=0.6，權值α和β分別為0.6和 0.4，最大迭代次數設置為50次，信息素的揮發率η=0.4，調節因子μ=2.

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

4.2調度時間比較

三種方法對應的任務調度時間仿真結果如圖1所示：

圖2　任務調度時間對比

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

4.3CPU利用率

圖3　CPU利用率對比

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

4.4負載均衡度

負載均衡離差反應了系統的負載均衡程度，其值可以通過下式計算：

(13)

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

圖4　負載均衡離差

5結語

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

參考文獻：

[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]馬艷,龔斌,鄒立達. 網格環境下基于復制的能耗有效依賴任務調度研究[J].計算機研究與發展,2013,(2):420-429.

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

[4]王觀玉．網格計算中任務調度算法的研究和改進[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]卜憲憲. 基于小生境和自適應遺傳算法的網格任務調度優化研究[J]. 計算機測量與控制，2013, (2):470-479.

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

[10]蒲汛,彭喜化,于顯平,等.基于均勻離散PSO算法的多QoS網格任務調度策略[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— ),女,山西太原人, 太原學院計算機系講師，碩士.研究方向:計算機應用技術.

收稿日期：2015-12-31