鄧碧林，王云嵐

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

0 引言

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

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

云計算的興起也給科學(xué)計算提供了一種與傳統(tǒng)的高性能科學(xué)計算不同的計算平臺。在科學(xué)計算領(lǐng)域，復(fù)雜的計算過程通常使用工作流來組織。這些工作流通常涉及大量的數(shù)據(jù)和計算，被部署在超級計算機(jī)、分布式集群系統(tǒng)或者網(wǎng)格系統(tǒng)。然而，構(gòu)造和維護(hù)這樣的系統(tǒng)需要大量的資金。云計算出現(xiàn)后，研究人員對科學(xué)工作流部署在云端進(jìn)行了研究，肯定了在云端部署科學(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ù)中心的負(fù)載不平衡，從而影響整個云平臺的資源利用率，降低工作流的執(zhí)行效率，增加用戶開銷。

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

1 相關(guān)研究

雖然云平臺中的調(diào)度算法已有了大量研究，但仍然存在不少問題。文獻(xiàn)［2］提出了一種基于圖割的調(diào)度算法，該算法充分考慮了減少各個數(shù)據(jù)中心間數(shù)據(jù)的傳輸量，卻并沒有考慮各個數(shù)據(jù)中心的計算能力和負(fù)載情況。在實際情況中，即使各個數(shù)據(jù)中心的計算能力是相同的，由于工作流中任務(wù)的不同，系統(tǒng)運行一段時間后，各個數(shù)據(jù)中心的負(fù)載情況也有可能出現(xiàn)較大的差別。文獻(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ù)中心負(fù)載不平衡的情況。文獻(xiàn)［5］提出了一種云工作流中間數(shù)據(jù)的存放策略以降低工作流的執(zhí)行開銷。該文中的算法首先根據(jù)中間數(shù)據(jù)的起源生成一個中間數(shù)據(jù)關(guān)系圖(IDG)，IDG記錄了云工作流系統(tǒng)中所有存在過的數(shù)據(jù)的信息。系統(tǒng)可以通過IDG知道中間數(shù)據(jù)的生成代價，再將生成代價和存儲代價進(jìn)行比較來決定是否存儲該中間數(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進(jìn)行更新以反映當(dāng)前各數(shù)據(jù)中心的負(fù)載情況。

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

3 MCGRP算法

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

3.1 收縮階段

在收縮階段將由圖G生成一系列子圖。該階段可以使用兩種算法:RM(Random Matching)、HEM(Heavy Edge Matching)。RM算法:以隨機(jī)的方式對圖G中的頂點進(jìn)行訪問，對于訪問到的某一頂點V，如果該頂點在該輪收縮中沒有被訪問過，則將該頂點隨機(jī)地和一個與其有邊相連并在該輪未被訪問過的頂點收縮。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)值較大的邊進(jìn)行收縮，可以最大限度地減少收縮后圖中邊的權(quán)值。根據(jù)上述原理，HEM算法改進(jìn)了RM算法:

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

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

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

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

3.2 初始劃分階段

初始劃分階段將收縮后的圖劃分為K個部分，并使得每個部分包含的節(jié)點的權(quán)值和大致相等?？梢允褂?種方式得到圖的初始劃分:(1)在第一階段不停地對圖進(jìn)行收縮，直到圖中只剩下K個頂點。(2)采用貪婪算法，首先選擇起始任務(wù)作為初始節(jié)點對圖進(jìn)行深度優(yōu)先遍歷;當(dāng)已遍歷過的節(jié)點的權(quán)值大致等于W(V)/K時停止;將已遍歷過的節(jié)點從圖中分割，對剩下的圖重復(fù)上述操作，直至圖被分割為K個部分。第一種方式有2個主要的缺點:(1)在對圖進(jìn)行收縮的最后階段，整個圖可能收縮得很慢;(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é)點被標(biāo)記為可移動，如果這些節(jié)點位于被劃分的子圖的邊界，算法就按一定的規(guī)則判斷該節(jié)點是屬于該子圖還是與其相鄰的子圖。由于在收縮過程中各子節(jié)點包含圖G中的節(jié)點數(shù)目逐漸增大，所以在優(yōu)化階段移動的節(jié)點包含圖G中的節(jié)點數(shù)目逐漸減小，即優(yōu)化的粒度由粗到細(xì)。

在優(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ù)中心的拓?fù)鋱D。式(2)表示Gi+1中任意一個子圖中的節(jié)點的權(quán)值和都不能超出對應(yīng)的數(shù)據(jù)中心的容量。

優(yōu)化階段的具體步驟如下:在第i輪優(yōu)化過程中，仍然以隨機(jī)的方式訪問圖中的節(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é)點將被標(biāo)記為可自由移動，然后重復(fù)上述過程。

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

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

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

本文的實驗對比了RR、MCGP、MCGRP算法的調(diào)度效果。為了保證算法輸出的準(zhǔn)確度，對于算法的每個輸入，都重復(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ù)中心的負(fù)載情況，造成了部分?jǐn)?shù)據(jù)中心的過載，大大增加了工作流的執(zhí)行時間。

5 結(jié)束語

本文首先分析了制約云環(huán)境中科學(xué)工作流的執(zhí)行效率的因素，指出各個數(shù)據(jù)中心間負(fù)載的不平衡是影響工作流執(zhí)行過程的一個主要因素，進(jìn)而提出了調(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］.計算機(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.