基于圖割的云環(huán)境中工作流調(diào)度改進算法

鄧碧林，王云嵐

(西北工業(yè)大學(xué)計算機學(xué)院，陜西 西安 710072)

0 引言

隨著人們對計算能力需求的不斷提升，在繼分布式計算、網(wǎng)格計算后，云計算模型首先由商業(yè)界提出。云計算使用虛擬化技術(shù)將大規(guī)模的計算和存儲資源虛擬成一個資源池。用戶可以在需要的時候通過服務(wù)的方式獲取這些資源，并為所使用的資源支付費用。

相對于傳統(tǒng)的計算模型，云計算有以下兩點優(yōu)勢:(1)使用云計算的成本低。通過使用云計算，用戶避開了高昂的數(shù)據(jù)中心建設(shè)和維護費用，并且由于云計算按需獲取資源的方式，用戶不用擔(dān)心因為業(yè)務(wù)量的增長或者數(shù)據(jù)量的增長帶來的升級費用。(2)使用方便快捷。在云計算環(huán)境中，用戶的程序、數(shù)據(jù)的管理都由云端來完成。數(shù)據(jù)中心的負載均衡、安全等因素由提供云計算服務(wù)企業(yè)的IT人員負責(zé)。用戶只需要有較快的互聯(lián)網(wǎng)接入就可以通過PC方便快捷地處理數(shù)據(jù)和享受服務(wù)。

云計算的興起也給科學(xué)計算提供了一種與傳統(tǒng)的高性能科學(xué)計算不同的計算平臺。在科學(xué)計算領(lǐng)域，復(fù)雜的計算過程通常使用工作流來組織。這些工作流通常涉及大量的數(shù)據(jù)和計算，被部署在超級計算機、分布式集群系統(tǒng)或者網(wǎng)格系統(tǒng)。然而，構(gòu)造和維護這樣的系統(tǒng)需要大量的資金。云計算出現(xiàn)后，研究人員對科學(xué)工作流部署在云端進行了研究，肯定了在云端部署科學(xué)工作流的可行性［1］。

雖然云計算的出現(xiàn)解決了科學(xué)工作流執(zhí)行所需的計算資源問題，但同時也引入了一些新問題。云計算平臺通常由地理上分布的數(shù)據(jù)中心組成，或者由幾個組織的私有云通過互聯(lián)網(wǎng)連接成一個更大的云計算平臺。工作流引擎在執(zhí)行工作流的時候通常需要將數(shù)據(jù)分配到不同的數(shù)據(jù)中心或者私有云中。同時，工作流中不同階段的任務(wù)之間也需要交換數(shù)據(jù)。不合理的任務(wù)調(diào)度方法不僅會增加各數(shù)據(jù)中心間的通信量，而且會導(dǎo)致各數(shù)據(jù)中心的負載不平衡，從而影響整個云平臺的資源利用率，降低工作流的執(zhí)行效率，增加用戶開銷。

本文提出了一種基于圖割的科學(xué)工作流調(diào)度策略MCGRP(Multi Constraint Graph Ratio Partitioning)，其過程如下:科學(xué)工作流管理系統(tǒng)在運行時會維護一張云平臺數(shù)據(jù)中心的拓撲圖，圖中的頂點表示某個數(shù)據(jù)中心在某一時刻的空閑slot數(shù)目，圖中的邊表示各數(shù)據(jù)中心的通信能力;當(dāng)調(diào)度新的工作流時，工作流的調(diào)度器首先對工作流的DAG使用MCGRP算法進行分割，然后根據(jù)分割結(jié)果將DAG中的任務(wù)調(diào)度到對應(yīng)的數(shù)據(jù)中心。

1 相關(guān)研究

雖然云平臺中的調(diào)度算法已有了大量研究，但仍然存在不少問題。文獻［2］提出了一種基于圖割的調(diào)度算法，該算法充分考慮了減少各個數(shù)據(jù)中心間數(shù)據(jù)的傳輸量，卻并沒有考慮各個數(shù)據(jù)中心的計算能力和負載情況。在實際情況中，即使各個數(shù)據(jù)中心的計算能力是相同的，由于工作流中任務(wù)的不同，系統(tǒng)運行一段時間后，各個數(shù)據(jù)中心的負載情況也有可能出現(xiàn)較大的差別。文獻［3-4］將MCGP(Multi-Constraint Graph Partitioning)算法應(yīng)用到了科學(xué)工作流的調(diào)度中。與普通的圖割算法只給圖中頂點賦一個權(quán)值不同，MCGP算法中圖的頂點的權(quán)值使用向量表示，分割后的結(jié)果不僅可以使被切割的邊的權(quán)值和較小，同時各個子圖中頂點的權(quán)值向量中各分量和盡量相似(equi-partition)。實驗結(jié)果表明，相對于傳統(tǒng)的RR(Round Robin)算法，MCGP算法平均減少了31%的工作流執(zhí)行時間。然而，MCGP算法中的equi-partition并不適用于由計算能力不同的數(shù)據(jù)中心組成的云平臺的情況或者各個數(shù)據(jù)中心負載不平衡的情況。文獻［5］提出了一種云工作流中間數(shù)據(jù)的存放策略以降低工作流的執(zhí)行開銷。該文中的算法首先根據(jù)中間數(shù)據(jù)的起源生成一個中間數(shù)據(jù)關(guān)系圖(IDG)，IDG記錄了云工作流系統(tǒng)中所有存在過的數(shù)據(jù)的信息。系統(tǒng)可以通過IDG知道中間數(shù)據(jù)的生成代價，再將生成代價和存儲代價進行比較來決定是否存儲該中間數(shù)據(jù)。

2 問題闡述

在調(diào)度問題中，工作流一般使用有向非循環(huán)圖DAG=(V，E)表示。圖中的頂點 V=(v1，v2，…，vn)表示工作流中的任務(wù)。圖中的邊E=(e1，e2，…，em)表示各個任務(wù)間的關(guān)系，圖中的某一條邊Eij表示vi是vj的父任務(wù)。每個子任務(wù)可以開始執(zhí)行當(dāng)且僅當(dāng)它所有的父任務(wù)已經(jīng)執(zhí)行完畢。每個頂點都有一個相應(yīng)的權(quán)值來表示任務(wù)的屬性(如執(zhí)行任務(wù)所需的計算量或者任務(wù)所需的存儲量)。

運行工作流的云平臺也可以使用圖G表示，圖中的頂點表示構(gòu)成云平臺的數(shù)據(jù)中心。圖中的邊表示各個數(shù)據(jù)中心間的通信開銷。圖中的每個頂點也都有一個權(quán)值，表示當(dāng)前該數(shù)據(jù)中心的空閑計算資源。工作流運行時，假設(shè)同一個數(shù)據(jù)中心中任務(wù)間的通信開銷為零，工作流管理系統(tǒng)需要不斷對圖G進行更新以反映當(dāng)前各數(shù)據(jù)中心的負載情況。

根據(jù)以上假設(shè)，云環(huán)境中工作流的調(diào)度問題可以簡化為圖割(Graph Cut)問題:使用圖割算法對工作流的DAG圖進行分割，分割到同一子圖中的任務(wù)將被調(diào)度到同一數(shù)據(jù)中心執(zhí)行。因此，圖割的目標就是使被切割的圖中邊的權(quán)值和最小(對應(yīng)工作流執(zhí)行過程中各數(shù)據(jù)中心間的通信量最小)，并且各個子圖中頂點的權(quán)值和與云平臺構(gòu)成的圖盡量相似(對應(yīng)于各數(shù)據(jù)中心都不會因為任務(wù)分配的不平衡而造成該數(shù)據(jù)中心的負載過重)?？梢允褂酶鱾€數(shù)據(jù)中心的slot數(shù)目和對應(yīng)的子圖中虛擬機的數(shù)目之差的絕對值的和SUM來表示兩個圖的相似度。SUM越小表示兩個圖的相似度越高。在下文中，將使用 M(DAG，G)來表示兩個圖的相似度。

3 MCGRP算法

MCGRP算法是對MCGP算法的改進。MCGP算法包含3個階段:(1)收縮階段;(2)初始劃分階段;(3)優(yōu)化階段。MCGRP算法主要在優(yōu)化階段對MCGP算法進行改進。下文中只簡要闡述MCGRP使用的第1、第2階段的算法，具體過程見文獻［6］。

3.1 收縮階段

在收縮階段將由圖G生成一系列子圖。該階段可以使用兩種算法:RM(Random Matching)、HEM(Heavy Edge Matching)。RM算法:以隨機的方式對圖G中的頂點進行訪問，對于訪問到的某一頂點V，如果該頂點在該輪收縮中沒有被訪問過，則將該頂點隨機地和一個與其有邊相連并在該輪未被訪問過的頂點收縮。HEM算法:考慮圖Gi=(Vi，Ei)和對其收縮后的圖Gi+1，使用W(Ei)表示圖Gi中所有邊的權(quán)值和;容易得出W(Ei)=W(Ei+1)+W(E)，其中W(E)表示在第i輪收縮過程中被收縮的邊的權(quán)值和;由上式可知，如果在每次收縮過程中選擇權(quán)值較大的邊進行收縮，可以最大限度地減少收縮后圖中邊的權(quán)值。根據(jù)上述原理，HEM算法改進了RM算法:

步驟1 將圖G中所有的節(jié)點標記為未被訪問。

步驟2 隨機地選擇一個未被標記的節(jié)點V并標記V為已訪問。

步驟3 選擇與V有邊相連且邊的權(quán)值最大的節(jié)點與V合并。如果不能找到這樣的節(jié)點，回到步驟2。

步驟4 判斷圖中是否還有未被訪問過的節(jié)點。沒有則該輪收縮結(jié)束，有則回到步驟2。

3.2 初始劃分階段

初始劃分階段將收縮后的圖劃分為K個部分，并使得每個部分包含的節(jié)點的權(quán)值和大致相等。可以使用2種方式得到圖的初始劃分:(1)在第一階段不停地對圖進行收縮，直到圖中只剩下K個頂點。(2)采用貪婪算法，首先選擇起始任務(wù)作為初始節(jié)點對圖進行深度優(yōu)先遍歷;當(dāng)已遍歷過的節(jié)點的權(quán)值大致等于W(V)/K時停止;將已遍歷過的節(jié)點從圖中分割，對剩下的圖重復(fù)上述操作，直至圖被分割為K個部分。第一種方式有2個主要的缺點:(1)在對圖進行收縮的最后階段，整個圖可能收縮得很慢;(2)由于在收縮的過程中只考慮圖中的邊的權(quán)值，并沒有考慮頂點的權(quán)值，將整個圖直接收縮為K個節(jié)點可能會導(dǎo)致K個節(jié)點的權(quán)值和極不平衡。在本文的算法中圖的初始劃分使用的是貪婪算法。

3.3 優(yōu)化階段

優(yōu)化階段是收縮階段的逆過程。在優(yōu)化階段，經(jīng)過初始劃分的圖將會由 Gm，Gm－1，…，G1變回 G。在由 Gi變到 Gi－1的過程中，由圖 Gi－1收縮到 Gi過程中被收縮的節(jié)點被標記為可移動，如果這些節(jié)點位于被劃分的子圖的邊界，算法就按一定的規(guī)則判斷該節(jié)點是屬于該子圖還是與其相鄰的子圖。由于在收縮過程中各子節(jié)點包含圖G中的節(jié)點數(shù)目逐漸增大，所以在優(yōu)化階段移動的節(jié)點包含圖G中的節(jié)點數(shù)目逐漸減小，即優(yōu)化的粒度由粗到細。

在優(yōu)化階段需要計算邊界節(jié)點在各個子圖間移動的利益函數(shù)以確定是否移動該節(jié)點。對于圖Gi=(Vi，Ei)中的某一節(jié)點V，定義V的鄰居N(V)為與該頂點有邊相連的子圖的并集。如果節(jié)點V是一個內(nèi)部節(jié)點，定義N(V)為空。對于子圖中的某一個邊界節(jié)點V，定義它對于N(V)中某一子圖的出度ED(V)為V與該子圖相連的邊的權(quán)值和。定義V的入度ID(V)為節(jié)點V與當(dāng)前V所在的子圖相連的邊的權(quán)值和。例如，在圖1中，節(jié)點V對子圖a的出度為4，它對于子圖c的入度為3。由于節(jié)點在2個子圖間移動并不改變該節(jié)點對于其他子圖的出度，可以定義在某一輪優(yōu)化過程中節(jié)點V從子圖a移動到子圖b的收獲為:G(V)=ED(V)-ID(V)。

圖1 示例流程圖

在邊界節(jié)點的移動過程中，如果只單純考慮利益函數(shù)的最小化，可能會導(dǎo)致劃分得到的圖與數(shù)據(jù)中心組成的圖極不相符(使用上文提出的衡量算法)。因此，節(jié)點在移動的過程中必須符合下面2個公式。

式(1)表示在第i輪優(yōu)化后，圖Gi+1要比圖Gi更符合數(shù)據(jù)中心的拓撲圖。式(2)表示Gi+1中任意一個子圖中的節(jié)點的權(quán)值和都不能超出對應(yīng)的數(shù)據(jù)中心的容量。

優(yōu)化階段的具體步驟如下:在第i輪優(yōu)化過程中，仍然以隨機的方式訪問圖中的節(jié)點。對于訪問到的節(jié)點V，如果該節(jié)點在子圖的內(nèi)部，則不移動。對于子圖邊界上的節(jié)點V，如果節(jié)點的移動不違反式(1)和式(2)，并且節(jié)點滿足下面2個條件中的任意一個，則將V移動到對應(yīng)的子圖。

(1)移動節(jié)點V到該子圖的收獲G(V)在所有子圖中是最大的。

(2)M(DAGi+1，G)在所有可能的移法中是最大的。

條件(1)表明在不違反平衡性條件下，優(yōu)化算法會將節(jié)點V移動到能使整個圖的邊割最小的子圖。條件(2)表明對于某一節(jié)點V，當(dāng)沒有對應(yīng)的子圖滿足條件(1)時，優(yōu)化算法將選擇能使移動后的圖更平衡的子圖將V移動過去。如果沒有子圖能滿足條件(1)和(2)，那么該節(jié)點不移動。在移動某一節(jié)點后，優(yōu)化算法更新該節(jié)點的ED(V)等數(shù)據(jù)結(jié)構(gòu)。當(dāng)圖中所有的節(jié)點都被訪問過或者不能在圖中找到滿足上述條件的節(jié)點時，該輪迭代結(jié)束。

在下一輪(第i+1輪)迭代中，在第i輪被收縮的節(jié)點將被標記為可自由移動，然后重復(fù)上述過程。

4 實驗結(jié)果及分析

為了驗證本文算法的有效性，在CPU為Intel?CoreTMi5，內(nèi)存為4 GB的PC機上進行了模擬實驗。

由于實際的工作流程圖只能反映一部分實際問題的情況，對其優(yōu)化的結(jié)果不能說明算法對所有的工作流程圖都有較好的加速效果。因此，為了全方位地檢測本文提出的調(diào)度算法的效果，采用了文獻［2］中的試驗方法，即使用模擬、可定制的工作流程圖作為算法的輸入。

本文的實驗對比了RR、MCGP、MCGRP算法的調(diào)度效果。為了保證算法輸出的準確度，對于算法的每個輸入，都重復(fù)10次計算，取結(jié)果的平均值作為算法的最終輸出。

數(shù)據(jù)中心的數(shù)量固定為4，工作流中的任務(wù)數(shù)增加時3種調(diào)度策略的調(diào)度效果比較如圖2所示。

圖2 任務(wù)數(shù)不同時3種調(diào)度算法的比較

從實驗結(jié)果來看，當(dāng)工作流中任務(wù)較少時，MCGRP算法對工作流執(zhí)行的加速效果并不十分明顯。而隨著任務(wù)數(shù)目的增加，MCGRP算法的調(diào)度效果明顯優(yōu)于RR算法和MCGP算法的調(diào)度效果。這是因為隨著任務(wù)數(shù)目的增多，由于RR算法和MCGP算法并未考慮數(shù)據(jù)中心的負載情況，造成了部分數(shù)據(jù)中心的過載，大大增加了工作流的執(zhí)行時間。

5 結(jié)束語

本文首先分析了制約云環(huán)境中科學(xué)工作流的執(zhí)行效率的因素，指出各個數(shù)據(jù)中心間負載的不平衡是影響工作流執(zhí)行過程的一個主要因素，進而提出了調(diào)度算法MCGRP。實驗結(jié)果表明，MCGRP算法相對于其他兩種算法(RR，MCGP)有較明顯的優(yōu)勢。

為了讓MCGRP算法更有應(yīng)用價值，將深入研究制約科學(xué)工作流執(zhí)行效率的因素，并在Eucalyptus平臺上實現(xiàn)一種科學(xué)工作流的調(diào)度平臺。

［1］Hoffa C，Mehta G，F(xiàn)reeman T，et al.On the use of cloud computing for scientific workflows［C］//Proceedings of the 4th IEEE International Conference on eScience.2008:640-645.

［2］劉少偉，孔令梅，任開軍，等.云環(huán)境下優(yōu)化科學(xué)工作流執(zhí)行性能的兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略［J］.計算機學(xué)報，2011，34(11):2121-2130.

［3］Tanaka M，Tatebe O.Workflow scheduling to minimize data movement using multi-constraint graph partitioning［C］//Proceedings of the 12th IEEE/ACM International Symposium on Cluster，Cloud and Grid Computing.2012:65-72.

［4］Karypis G，Kumar V.Multilevel k-way Partitioning Scheme for Irregular Graphs［R］.University of Minnesota，1995.

［5］Yuan D，Yang Y，Liu X，et al.A cost-effective strategy for intermediate data storage in scientific cloud workflow systems［C］//Proceedings of the 2010 IEEE International Symposium on Parallel＆ Distributed Processing.2010.

［6］Karypis G，Kumar V.Multilevel algorithms for multi-constraint graph partitioning［C］//Proceedings of the 1998 ACM/IEEE Conference on Supercomputing.1998:64-76.

［7］Deng K，Song J，Ren K，et al.Graph-cut based coscheduling strategy towards efficient execution of scientific workflows in collaborative cloud environments［C］//Proceedings of the 12th IEEE/ACM International Conference on Grid Computing.2011:34-41.

［8］Foster I，Zhao Y，Raicu I，et al.Cloud computing and grid computing 360-degree compared［C］//Proceedings of the 2008 IEEE Workshop on Grid Computing Environments.2008:60-69.

［9］Armbrust M，F(xiàn)ox A，Griffith R，et al.A view of cloud computing［J］.Communications of the ACM，2010，53(4):50-58.

［10］Ostermann S，Iosup A，Yigitbasi N，et al.A performance analysis of EC2 cloud computing services for scientific computing［M］//Cloud Computing.Springer，Berlin，Heidelberg，2010，34:115-131.

［11］Nurmi D，Wolski R，Grzegorczyk C，et al.The eucalyptus open-source cloud-computing system［C］//Proceedings of the 9th IEEE/ACM International Symposium on Cluster Computing and the Grid.2009:124-131.

［12］Youseff L，Butrico M，Da Silva D.Toward a unified ontology of cloud computing［C］//Proceedings of the 2008 IEEE Workshop on Grid Computing Environments.2008:42-51.

［13］Velte T，Velte A，Elsenpeter R.Cloud Computing:A Practical Approach［M］.McGraw-Hill，2009.

［14］Marinos A，Briscoe G.Community cloud computing［C］//Proceedings of the 1st International Conference on Cloud Computing.2009:472-484.