朱曉虹

（福建對(duì)外經(jīng)濟(jì)貿(mào)易職業(yè)技術(shù)學(xué)院　信息技術(shù)系，福建　福州　350012）

一種面向通信開銷的網(wǎng)格工作流調(diào)度算法

朱曉虹

（福建對(duì)外經(jīng)濟(jì)貿(mào)易職業(yè)技術(shù)學(xué)院信息技術(shù)系，福建福州350012）

摘要：采用任務(wù)—資源分配圖定義了網(wǎng)格任務(wù)調(diào)度模型，運(yùn)用動(dòng)態(tài)規(guī)劃的方法提出了面向通信開銷的工作流任務(wù)調(diào)度算法。采用擴(kuò)展的拓?fù)渑判蛩惴▽?duì)具有依賴關(guān)系的工作流任務(wù)進(jìn)行劃分，根據(jù)劃分的任務(wù)子集得到相應(yīng)的調(diào)度階段，在每一階段選擇滿足約束條件和以計(jì)算開銷、通信開銷以及任務(wù)執(zhí)行成功率為最優(yōu)目標(biāo)函數(shù)的資源節(jié)點(diǎn)進(jìn)行任務(wù)分配，從而使工作流任務(wù)調(diào)度目標(biāo)函數(shù)最優(yōu)。應(yīng)用GridSim工具包實(shí)現(xiàn)了該調(diào)度算法，并與Min-Min算法進(jìn)行對(duì)比分析。仿真結(jié)果表明，基于動(dòng)態(tài)規(guī)劃的網(wǎng)格工作流調(diào)度算法具有良好的適應(yīng)性，且能較好地處理不同網(wǎng)絡(luò)環(huán)境下任務(wù)間存在大量數(shù)據(jù)傳輸?shù)木W(wǎng)格調(diào)度問(wèn)題。

關(guān)鍵詞：網(wǎng)格計(jì)算；工作流；動(dòng)態(tài)規(guī)劃；通信開銷

0　引言

移動(dòng)互聯(lián)網(wǎng)的發(fā)展使得地理位置上分散的計(jì)算資源可以協(xié)同工作，從而組成一個(gè)計(jì)算網(wǎng)格，實(shí)現(xiàn)資源共享［1-2］。由多個(gè)相互之間存在數(shù)據(jù)依賴或時(shí)序關(guān)系的網(wǎng)格任務(wù)組成的網(wǎng)格作業(yè)稱為網(wǎng)格工作流作業(yè)。對(duì)于通信密集型的應(yīng)用，在網(wǎng)格調(diào)度時(shí)僅僅考慮計(jì)算能力是不夠的，還需要考慮通信需求。在海量數(shù)據(jù)的網(wǎng)格計(jì)算應(yīng)用中，服務(wù)站點(diǎn)需要處理的數(shù)據(jù)量較為龐大，此時(shí)計(jì)算開銷對(duì)于服務(wù)站點(diǎn)來(lái)說(shuō)是影響性能的關(guān)鍵因素，為了保證網(wǎng)格計(jì)算性能，必須對(duì)分布的數(shù)據(jù)資源進(jìn)行合理的調(diào)度管理［3］。文獻(xiàn)［4］針對(duì)現(xiàn)有的網(wǎng)格工作流調(diào)度算法的不足，提出了AWSA算法，該算法充分考慮了節(jié)點(diǎn)的負(fù)載和服務(wù)能力，通過(guò)對(duì)任務(wù)的優(yōu)先級(jí)進(jìn)行排序來(lái)選擇具有最大截止時(shí)間約束的站點(diǎn)作為最優(yōu)的候選，然后根據(jù)動(dòng)態(tài)負(fù)載變化情況來(lái)完成從資源到服務(wù)站點(diǎn)的映射。文獻(xiàn)［5-6］提出了一種混合環(huán)境下的科學(xué)工作流執(zhí)行系統(tǒng)架構(gòu)并對(duì)其核心組件進(jìn)行了闡述。針對(duì)其中的工作流調(diào)度問(wèn)題，利用隨機(jī)服務(wù)模型建模已有網(wǎng)格系統(tǒng)中資源的動(dòng)態(tài)服務(wù)能力，以任務(wù)違約風(fēng)險(xiǎn)作為是否租借外部虛擬資源的判斷指標(biāo)，提出了一個(gè)科學(xué)的工作流調(diào)度算法HCA_SASWD。文獻(xiàn)［7］提出一種用于解決具有截止時(shí)間約束的工作流調(diào)度算法（Min-Min），該算法在保證任務(wù)調(diào)度實(shí)時(shí)性的同時(shí)，有效地實(shí)現(xiàn)了服務(wù)站點(diǎn)的負(fù)載均衡。然而上述算法均沒(méi)有考慮具有依賴關(guān)系的任務(wù)執(zhí)行，并且通信開銷已經(jīng)給定，沒(méi)有具體考慮通信開銷對(duì)任務(wù)調(diào)度的影響。針對(duì)以上問(wèn)題，筆者提出了一種面向通信開銷的網(wǎng)格工作流調(diào)度算法，這一算法采用動(dòng)態(tài)規(guī)劃的思想，先用擴(kuò)展的拓?fù)渑判蛩惴▽?duì)工作流任務(wù)進(jìn)行劃分，分為若干個(gè)任務(wù)子集，每一個(gè)任務(wù)子集構(gòu)成一個(gè)階段。在每一個(gè)階段綜合考慮任務(wù)的計(jì)算開銷和通信開銷以及任務(wù)的執(zhí)行成功率，使得每一階段的任務(wù)在節(jié)點(diǎn)上的分配最優(yōu)，從而得到任務(wù)完成時(shí)間最少的任務(wù)分配策略。

1　動(dòng)態(tài)規(guī)劃與任務(wù)調(diào)度模型

網(wǎng)格調(diào)度中，很多大規(guī)模應(yīng)用有嚴(yán)格的截止時(shí)間約束，動(dòng)態(tài)規(guī)劃是用空間換時(shí)間的一種方法。建立動(dòng)態(tài)規(guī)劃模型主要有以下幾個(gè)步驟［8］：①階段劃分；②確定狀態(tài)變量Sk的含義及取值范圍；③明確決策變量xk的含義及取值范圍；④確定各階段的狀態(tài)轉(zhuǎn)移方程Sk+1=T(Sk, xk(Sk))；⑤確定階段指標(biāo)vk(Sk, xk)和最優(yōu)指標(biāo)函數(shù)fk(Sk)；⑥推導(dǎo)出遞推關(guān)系式。

本文所討論的網(wǎng)格工作流是由一組有約束關(guān)系（如控制依賴，數(shù)據(jù)依賴）的子任務(wù)組合而成。由于網(wǎng)格的動(dòng)態(tài)性和不確定性，任務(wù)分配到資源以后，資源在某些情況下可能會(huì)失效，因此在任務(wù)調(diào)度時(shí)引入了資源執(zhí)行的成功率。

定義11網(wǎng)絡(luò)工作流任務(wù)圖（task graph）TG = < X, D, E, C>。其模型如圖1所示，X是h個(gè)子任務(wù)的集合X = { x1, x2,…, xh}；Di=d(xi)表示每個(gè)子任務(wù)的計(jì)算量，D = { di| 0

圖1　網(wǎng)格工作流任務(wù)圖模型Fig.1 Grid task graph model

定義2網(wǎng)格資源分配圖（grid resource）GR=(M, Q, B, P)。其模型如圖2所示，M是網(wǎng)格計(jì)算資源的集合M={mi| 0≤i≤n}，m(xi)=Mj，Mj∈M表示給任務(wù)xi分配的資源節(jié)點(diǎn)；qi=q (mi)表示單位時(shí)間內(nèi)資源mi的計(jì)算能力，即mi的執(zhí)行速度，Q= { qi| 0≤i≤n }；bij=b ( mi, mj)為n個(gè)資源之間網(wǎng)絡(luò)連接帶寬組成的矩陣B= { bij| 0≤i, j≤n }；pi=p (mi)表示資源執(zhí)行任務(wù)的成功率，P ={ pi| 0≤i≤n }。

網(wǎng)格調(diào)度的目標(biāo)就是在滿足給定的QoS約束條件下，按照某種策略選擇最優(yōu)的節(jié)點(diǎn)來(lái)對(duì)其進(jìn)行任務(wù)分配。

圖2　網(wǎng)格資源分配圖模型Fig.2 Task resource assignment graph

本文討論任務(wù)調(diào)度問(wèn)題的前提是：①在工作流任務(wù)的調(diào)度中，當(dāng)且僅當(dāng)前驅(qū)任務(wù)執(zhí)行完畢，后繼任務(wù)才參與調(diào)度；②各資源節(jié)點(diǎn)之間可以相互通信，且bij=bji。當(dāng)i=j時(shí)，bij=∞；③一個(gè)子任務(wù)只能由一個(gè)資源節(jié)點(diǎn)執(zhí)行，一個(gè)節(jié)點(diǎn)只能同時(shí)執(zhí)行一個(gè)任務(wù)，并且在一段時(shí)間內(nèi)節(jié)點(diǎn)的計(jì)算性能相對(duì)穩(wěn)定，即qi相對(duì)穩(wěn)定；④每個(gè)子任務(wù)xi分配到資源節(jié)點(diǎn)m(xi)=mj，mj∈M。任務(wù)的完成時(shí)間ti包括兩部分：計(jì)算時(shí)間tpi和通信時(shí)間tci，即ti=tpi+tci（i=1, 2,…, h）；⑤任務(wù)完成的計(jì)算時(shí)間由子任務(wù)的計(jì)算量和任務(wù)分配到的資源節(jié)點(diǎn)的計(jì)算性能決定，即tpi=d(xi)/ q (m(xi))；⑥任務(wù)完成的通信時(shí)間包括兩部分，即數(shù)據(jù)傳輸時(shí)間和傳輸延長(zhǎng)時(shí)間。數(shù)據(jù)傳輸時(shí)間由前驅(qū)任務(wù)和后繼任務(wù)之間的數(shù)據(jù)傳輸量和所在網(wǎng)格資源之間的帶寬決定；傳輸延長(zhǎng)時(shí)間指的是由于當(dāng)前網(wǎng)絡(luò)系統(tǒng)負(fù)載存在不確定性，如網(wǎng)格跳數(shù)可能不同致使網(wǎng)絡(luò)使用高峰期時(shí)傳輸速度的下降，用td表示。故通信時(shí)間tci=c(pre(xi),xi)/ b(m(pre(xi)),m(xi))+td。

每個(gè)子任務(wù)的目標(biāo)函數(shù)包括兩部分：任務(wù)的完成時(shí)間和任務(wù)的執(zhí)行成功率。在調(diào)度中應(yīng)優(yōu)先選擇任務(wù)完成時(shí)間最少，任務(wù)執(zhí)行成功率最高的資源，使得子任務(wù)的目標(biāo)函數(shù)最小，從而使整個(gè)網(wǎng)格工作流應(yīng)用調(diào)度的目標(biāo)函數(shù)最小。

2　基于動(dòng)態(tài)規(guī)劃的網(wǎng)格工作流調(diào)度算法

基于文獻(xiàn)［8］建立的動(dòng)態(tài)規(guī)劃模型和本文所定義的任務(wù)調(diào)度模型，筆者提出了基于動(dòng)態(tài)規(guī)劃的網(wǎng)格工作流調(diào)度算法（workflow scheduling alogrithm based on dynamic programming，DPW）。DPW算法的主要思想是：首先用擴(kuò)展的拓?fù)渑判蛩惴▽?duì)工作流任務(wù)進(jìn)行劃分得到任務(wù)子集，根據(jù)任務(wù)子集得到不同的執(zhí)行階段。然后采用動(dòng)態(tài)規(guī)劃方法對(duì)每一階段的任務(wù)進(jìn)行最優(yōu)規(guī)劃和資源分配，使得每一階段任務(wù)的目標(biāo)函數(shù)最小，從而使網(wǎng)格系統(tǒng)的效益最大。具體步驟如下：

Step 1根據(jù)擴(kuò)展的拓?fù)渑判蛩惴▽?duì)網(wǎng)格工作流進(jìn)行任務(wù)劃分。算法描述如下：

A）在任務(wù)圖中選擇無(wú)前驅(qū)的任務(wù)頂點(diǎn)，形成一個(gè)集合；

B）從任務(wù)圖中刪除該頂點(diǎn)和所有以它為尾的依賴關(guān)系，然后轉(zhuǎn)步驟A繼續(xù)執(zhí)行；

C）重復(fù)執(zhí)行步驟A和B，直至所有的任務(wù)頂點(diǎn)均已輸出，或者任務(wù)圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止；

D）根據(jù)以上算法得到k個(gè)任務(wù)子集，每一個(gè)任務(wù)子集用Sk表示。具體過(guò)程如圖3所示，根據(jù)擴(kuò)展的拓?fù)渑判蛩惴傻玫絳( x1, x2, x3)，( x4, x7)，( x5, x6)，( x8, x9)}4個(gè)任務(wù)子集，如S1為( x1, x2, x3)。

Step 2建立動(dòng)態(tài)規(guī)劃模型。過(guò)程描述如下：

A）根據(jù)Step1得到了k個(gè)任務(wù)子集，將調(diào)度過(guò)程劃分為k個(gè)階段；

B）狀態(tài)變量Sk：當(dāng)前k階段應(yīng)分配的任務(wù)集Sk；

C）決策變量Uk：xi任務(wù)( xi∈Sk)分配到相應(yīng)的資源節(jié)點(diǎn)mj的效益函數(shù)；

E）最優(yōu)目標(biāo)函數(shù)遞推關(guān)系：fk+1(Si+1)=min{gk+1(Sk,Uk)+fk(Sk)}。表示本階段的目標(biāo)函數(shù)是根據(jù)任務(wù)所在資源節(jié)點(diǎn)選擇本階段任務(wù)分配目標(biāo)函數(shù)最小的資源。gk+1(Sk, Uk)表示當(dāng)前階段任務(wù)的完成時(shí)間與任務(wù)執(zhí)行成功率的綜合函數(shù)即

F）邊界條件：初始任務(wù)沒(méi)有前驅(qū)任務(wù)，沒(méi)有前階段，所以為0，即f1(S1)=0。

綜上所述，網(wǎng)格中面向通信開銷的工作流任務(wù)調(diào)度算法描述如下：

{while一個(gè)工作流應(yīng)用被提交do

利用的拓?fù)渑判蛩惴▽⒐ぷ髁魅蝿?wù)分成任務(wù)子集Sk；

for每一階段的子任務(wù)Sk選擇滿足動(dòng)態(tài)規(guī)劃約束條件和最優(yōu)目標(biāo)函數(shù)的網(wǎng)格資源節(jié)點(diǎn)進(jìn)行調(diào)度；

endwhile }

圖3　一個(gè)簡(jiǎn)單的工作流應(yīng)用Fig.3 A simple workflow application

3　實(shí)驗(yàn)及分析

為了驗(yàn)證算法的性能，將本文中提出的DPW算法與Min-Min算法進(jìn)行比較。利用GridSim仿真實(shí)驗(yàn)來(lái)模擬網(wǎng)格中需要被調(diào)度的計(jì)算任務(wù)和擁有的資源，整個(gè)實(shí)驗(yàn)步驟分為兩個(gè)步驟：①網(wǎng)格任務(wù)的提交，負(fù)責(zé)模擬泊松分布提交待處理的計(jì)算任務(wù)；②任務(wù)分配，負(fù)責(zé)依據(jù)給定的調(diào)度算法來(lái)為任務(wù)指定合適的服務(wù)站點(diǎn)。

圖4給出了資源同構(gòu)環(huán)境下DPW算法與Min-Min算法對(duì)調(diào)度時(shí)間的影響。實(shí)驗(yàn)結(jié)果表明，DPW算法在資源同構(gòu)時(shí)使網(wǎng)格具有更好的容錯(cuò)性并減少了整體的調(diào)度時(shí)間。

圖4　兩種算法在同構(gòu)環(huán)境下調(diào)度時(shí)間的比較Fig.4 Comparison of scheduling time between two algorithms in a homogeneous environment

圖5給出了資源異構(gòu)環(huán)境下DPW算法與Min-Min算法對(duì)調(diào)度時(shí)間的影響。實(shí)驗(yàn)結(jié)果表明，隨著數(shù)據(jù)傳輸量的加大以及資源能力差異的變大，數(shù)據(jù)傳輸時(shí)間所占的比例也越來(lái)越大，因而造成的影響也越來(lái)越明顯，DPW算法與Min-Min算法相比調(diào)度長(zhǎng)度明顯減少。

圖5　兩種算法在異構(gòu)環(huán)境下調(diào)度時(shí)間的比較Fig.5 Comparison of scheduling time between two algorithms in a heterogeneous environment

上述實(shí)驗(yàn)結(jié)果表明筆者提出的面向通信開銷的網(wǎng)格工作流任務(wù)調(diào)度算法具有良好的適應(yīng)性，且能較好地解決計(jì)算能力及網(wǎng)絡(luò)帶寬不同時(shí)，任務(wù)間存在大量數(shù)據(jù)傳輸?shù)那闆r下DPW算法更優(yōu)。

4　結(jié)語(yǔ)

網(wǎng)格計(jì)算中的工作流調(diào)度問(wèn)題是目前的研究熱點(diǎn)，針對(duì)現(xiàn)有的調(diào)度算法沒(méi)有考慮通信開銷對(duì)任務(wù)調(diào)度的影響這一不足，筆者提出了一種面向通信開銷的網(wǎng)格工作流調(diào)度算法，其以擴(kuò)展的拓?fù)渑判蛩惴▽?duì)工作流任務(wù)進(jìn)行劃分為基礎(chǔ)，充分考慮了計(jì)算開銷和通信開銷對(duì)于任務(wù)調(diào)度性能的影響，從而使工作流任務(wù)調(diào)度目標(biāo)函數(shù)最優(yōu)。最后的仿真實(shí)驗(yàn)也表明了該算法的有效性。

參考文獻(xiàn)（References）

［1］王觀玉.網(wǎng)格計(jì)算中任務(wù)調(diào)度算法的研究和改進(jìn)［J］.計(jì)算機(jī)工程與科學(xué)，2011，33（10）：186-190.

［2］IOSUP A，EPEMA D.Grid computing workloads［J］.Internet Computing，IEEE，2011，15（2）：19-26.

［3］KUMAR P，RASTOGI R，GUPTA S K，et al.Performance parameters for load balancing algorithm in grid Computing［M］.Berlin：Springer，2012：333-336.

［4］王大偉，姜參.網(wǎng)格計(jì)算中一種改進(jìn)的工作流調(diào)度算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2014，24（2）：71-75.

［5］閻朝坤，胡志剛，羅慧敏.混合計(jì)算環(huán)境中截止期約束下的科學(xué)工作流調(diào)度策略［J］.計(jì)算機(jī)工程與科學(xué)，2012，34 （9）：40-46.

［6］林偉偉，齊德昱，李擁軍，等.樹形網(wǎng)格計(jì)算環(huán)境下的獨(dú)立任務(wù)調(diào)度［J］.軟件學(xué)報(bào)，2006，17（11）：2352-2361.

［7］KOKILAVANI T，AMALARETHINAM D I G.Load balanced Min- Min algorithm for static meta- task scheduling in grid computing［J］.International Journal of Computer Applications，2011，20（2）：43-49.

［8］邵曉曙，楊艷軍.動(dòng)態(tài)規(guī)劃在消防增援調(diào)度中的應(yīng)用［J］.武警學(xué)院學(xué)報(bào)，2008，24（8）：36-38.

（責(zé)任編輯：胡燕梅）

Grid Workflow Scheduling Algorithm Based on Communication Cost

ZHU Xiaohong
（Department of Information Technology，F(xiàn)ujian International Business & Economic College，F(xiàn)uzhou 350012，F(xiàn)ujian，China）

Abstract：In this text，the author uses DAG graph and task-resource allocation graph to define the grid task scheduling model，and utilizes dynamic programming method to propose workflow task scheduling algorithm based on communication cost.By using extended topological sorting algorithm，dependent tasks are divided into subsets，according to them，obtains corresponding phases.At each stage，carries out task allocation of resource nodes which meet constraint conditions and optimal objective function based on computing cost，communication cost and the success rate of implementation，so it can get the most optimal workflow task scheduling.Uses the GridSim tool package to realize the scheduling algorithm，and compares with the Min- Min algorithm.Simulation results show that the proposed algorithm has good adaptability，and can solve grid scheduling problem better under different network environment and large number of data transmission circumstances.

Keywords：grid computing；workflow；dynamic planning；communication cost

作者簡(jiǎn)介：朱曉虹（1972—），女，副教授，碩士，研究方向：網(wǎng)格計(jì)算和信息安全。

基金項(xiàng)目：福建省教育廳A類科技項(xiàng)目（JA12403）

收稿日期：2015 - 03 - 18

DOI：10.16389/j.cnki.cn42-1737/n.2015.03.016

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-0143（2015）03-0278-05