云環(huán)境下基于聚簇的科學工作流執(zhí)行優(yōu)化策略

1、云環(huán)境下基于聚簇的科學工作流執(zhí)行優(yōu)化策略 摘要：基于云環(huán)境下的科學工作流，以提高處理機利用率、降低費用為目標，提出了一種基于聚簇的執(zhí)行優(yōu)化策略。該策略首先基于合理的任務復制和分簇，以實現(xiàn)關鍵任務的盡早調度；在此基礎上，對任務簇再次進行聚集，以充分利用任務簇中任務間可能的空閑時間。實驗表明，該策略能夠提高任務的并行度，提前工作流的最早完成時間，并且在提高處理機的利用率和降低科學工作流的執(zhí)行費用方面有顯著效果。 關鍵詞：云計算；科學工作流；任務復制；聚簇；任務調度 中圖分類號： tp301.6 文獻標志碼：a 英文摘要 abstract：focusing on the higher ratio o

2、f processor utilization and lower execution cost of a scientific workflow in cloud， a policy of execution optimization based on task cluster aggregation was proposed. first， the tasks were reasonably replicated and aggregated into several clusters. therefore， the key tasks could be scheduled as earl

3、y as possible. then， the task clusters were aggregated again to facilitate the spare time among the tasks in the task cluster. the experimental results show that the proposed policy can improve the parallelism of workflow tasks， advance the earliest finish time of the whole workflow and it has a sig

4、nificant effect in improving the utilization ratio of processors and lowering the cost of workflow execution. 英文關鍵詞 key words：cloud computing； scientific workflow； task replication； cluster aggregation； task scheduling 0 引言 科學工作流（scientific workflow）是近年來出現(xiàn)的一種新的應用泛型，可支持科學研究人員集成、構造和協(xié)同分布異構的數(shù)據(jù)、服務和軟件工具，提

5、高科學實驗過程的自動化程度。隨著科學技術的發(fā)展，科學工作流逐漸變成數(shù)據(jù)密集型和計算密集型1，例如：生物信息領域廣泛使用的下一代dna測序技術，每輪測序便可以產生600gb的基因數(shù)據(jù)，一次蛋白質仿真實驗的計算時間就達到幾cpu年2（1cpu年是1gflop處理器不停歇地工作一年的計算量的總和。1gflop處理器一秒十億次浮點運算）。可見，常規(guī)的計算環(huán)境已經很難滿足科學工作流的需要，云計算環(huán)境因其理論上可提供無窮的計算和存儲能力以及經濟、可伸縮和payasyougo的支付方式等特點3，成為了科學工作流計算環(huán)境的理想選擇。 雖然理論上云環(huán)境可以提供無窮的計算能力，用戶可以按需使用其計算資源，但是計算

6、資源的提供方案的變化可能涉及到實例的創(chuàng)建和分配以及數(shù)據(jù)移動，需要付出一定的代價，并可能影響科學工作流的執(zhí)行效率和費用4。因此，生成一個合理的初始執(zhí)行計劃是非常重要的5。實現(xiàn)工作流任務到計算資源的合理映射是工作流執(zhí)行的基礎，也與工作流的執(zhí)行效率和執(zhí)行代價密切相關，該過程被稱為工作流的執(zhí)行計劃生成。 生成工作流執(zhí)行計劃的關鍵是把任務調度到合適的資源6上，包括資源的數(shù)量及類型?？茖W工作流任務調度算法已經有很多，目前基于啟發(fā)式的調度算法得到了廣泛應用，主要包括基于任務復制的調度、基于優(yōu)先級列表的調度和基于簇的調度。異態(tài)最早結束時間（heterogeneous earliest finish time，

7、heft）算法和可靠性動態(tài)水平調度（hierarchical reliabilitydriven scheduling，hrds）算法7屬于基于優(yōu)先級列表的調度。heft調度算法是根據(jù)平均計算量和平均通信量計算任務的rrank值，排列任務的rrank值得到任務調度隊列；hrds算法是對heft算法的改進，考慮了處理器和網絡鏈路都有一定的故障率而加入了可靠性因素。heft算法和hrds算法執(zhí)行性能較高，但是目標單純以最早完成時間為調度依據(jù)，沒有考慮任務調度中資源的空閑時間的有效利用及類型的差異。 一般來說，基于任務復制的調度要優(yōu)于基于優(yōu)先級列表調度和基于簇的調度8，因為基于任務復制的調度可以消除

8、任務間的通信開銷保留任務最初的并行性，從而減少總的執(zhí)行時間。 已有的任務復制算法主要有：多處理器任務調度（task duplication based scheduling，tds）算法9將有向無環(huán)圖（directed acyclic graph，dag）中的join節(jié)點與其友好前驅節(jié)點分配到同一處理機上來降低執(zhí)行時間，但是沒有考慮處理機個數(shù)優(yōu)化問題；基于任務復制的最優(yōu)調度（optimal task duplication based scheduling algorithm，osa）算法10將盡量多的父節(jié)點與子節(jié)點分配到同一個處理機上，使得當前任務能獲得最小的最早開始時間，但是著眼于局部沒有

9、從全局出發(fā)，制約了整個工作流的調度長度優(yōu)化；基于關鍵路徑和任務復制的單任務調度（critical path and task duplicationbased single scheduling，cptd）算法11把任務圖轉化為相應的產品加工樹，查找關鍵路徑，通過縮短關鍵路徑中節(jié)點的完成時間來縮短整個工作流的完成時間，但是算法復雜；縮略語與全稱首字母不對應，核實lwb（lower bound）算法12能得到最優(yōu)調度且處理機的使用個數(shù)也較少，但是要滿足后繼節(jié)點的最小計算時間大于最大通信時間，約束條件過于苛刻；基于任務復制的聚集調度（task duplicationbased clustering

10、 scheduling，tdcs）算法13是針對最早完成時間的算法，目標是最小化科學工作流的執(zhí)行時間，該算法簡單、時間復雜度更小并且約束條件寬松，實用性強，但是該算法沒有考慮處理機的使用數(shù)目、空閑時間的利用，也沒有涉及處理機類型、執(zhí)行費用。 因此，本文基于tdcs算法在滿足科學工作流執(zhí)行時間的基礎上，為了提高處理機資源的利用率，充分挖掘處理機的空閑時間，從而減少所需處理機數(shù)目降低執(zhí)行費用，提出了一種云環(huán)境下基于聚簇的科學工作流執(zhí)行優(yōu)化（execution optimization of scientific workflow based on cluster aggregation，eoswc

11、a）策略。該策略是在任務層對工作流的執(zhí)行進行優(yōu)化，文獻14是在服務層對工作流的執(zhí)行進行優(yōu)化，提出了云服務副本放置策略。 本文的主要工作包括：1）確定對哪些任務進行復制可以使工作流的完成時間最早；2）在不增加完成時間的前提下對生成的任務隊列進行聚簇，可減少任務簇的個數(shù)進而減少處理機的使用個數(shù)；3）為任務簇選擇合適的資源進行調度；4）對本文算法eoswca與tdcs算法在處理機使用數(shù)目、利用率以及執(zhí)行費用方面進行了比較。 本文的主要研究是：所提出的策略能夠提高任務的并行度，縮短科學工作流完成時間的同時，可充分利用處理機的閑置時間，并最終提高處理機的利用率，降低工作流的執(zhí)行費用。 1 科學工作流執(zhí)行

12、計劃的生成 eoswca算法的一個目的是盡量提早工作流的最早完成時間，而整個工作流的最早完成時間依賴于結束任務的最早完成時間，根據(jù)任務間的約束關系可知，只有父任務執(zhí)行完成后子任務才能執(zhí)行，所以結束任務的最早開始時間依賴于父任務的最早完成時間。類似地，父任務的最早開始時間依賴于其父任務的最早完成時間。以此類推，只有每一個任務都最早完成整個工作流才能最早完成。要想盡早完成任務就要盡量減少等待時間盡早開始執(zhí)行任務，所以要計算每一個任務的最早開始時間。 1.1 相關定義 1.2 任務集分簇 科學工作流的執(zhí)行通?？缍鄠€集群，這里假設不同集群間的通信速率相同，同一個集群的任務間的通信時間往往很小，文中忽略

13、不計。 子任務的最早開始時間取決于父任務的最早完成時間和它們之間的通信時間，為了提前子任務的最早開始時間，要消除與父任務之間的通信時間。為此，要把子任務和其父任務放在一起，即劃分到一個任務簇。同一個簇中的任務調度到同一個集群中執(zhí)行時，同一個簇中的任務間的通信時間就可以被消除。 對于只有一個父任務的情況，直接把子任務加入即可；對于是關鍵節(jié)點的任務，要讓到達關鍵節(jié)點最晚的前驅任務產生的數(shù)據(jù)盡早到達，為此把關鍵節(jié)點加入到其數(shù)據(jù)最晚到達的前驅所在的簇，這樣關鍵節(jié)點的開始時間得以提前，從而使最早完成時間提前。 分簇的過程中會出現(xiàn)一個任務有多個后繼的情況，即outdegreei2，其多個后繼的最早開始時間

14、可能都是它的最早完成時間，為了保證其后繼能在最早開始時間開始執(zhí)行，就要對部分主任務進行復制，如圖1中的t1、t5、t7。復制的規(guī)則如下： 1）若其后繼的前驅只有主任務一個，則復制主任務。 2）若其后繼的前驅有多個，即這一任務是關鍵任務，有兩種情況：主任務是關鍵任務的數(shù)據(jù)最晚到達的前驅，則復制主任務；主任務不是關鍵任務的數(shù)據(jù)最晚到達的前驅，則不復制主任務。 任務集分簇結束后，一般情況下，為了保證任務并行性則有幾個簇就要占用幾個處理機來執(zhí)行任務。對于圖1則要6個處理機，數(shù)目較多。為了減少處理機的使用個數(shù)、提高處理機空閑時間的利用率、降低費用，本文并不立即把任務簇調度到處理機上執(zhí)行而是對任務簇進行處

15、理。下面是對科學工作流初生成的執(zhí)行計劃的優(yōu)化。 2 科學工作流執(zhí)行計劃的優(yōu)化 定義4 聚簇是對分簇得到的任務簇進行合理的合并，以充分利用任務簇中的空閑時間來減少任務簇的個數(shù)，進而減少處理機的使用個數(shù)。 eoswca算法的另一個目的是在不改變工作流最早完成時間的前提下，盡量減少處理機的使用個數(shù)。上面分簇后的結果可以直接映射到處理機上執(zhí)行，為了滿足每個任務的最早完成時間，要為每個簇分配一個處理機，但是這樣占用的處理機資源較多，造成資源的浪費。分簇結束時就可以得到工作流的最早完成時間，在不改變工作流最早完成時間的前提下對任務簇作聚簇處理。 也就是說在保證整個工作流最早完成時間不增加的前提下，可以通過

16、改變中間某些任務的最早開始時間，進行聚簇處理來減少處理機的使用個數(shù)，只要保證任務節(jié)點在其后繼節(jié)點開始之前完成即可。 對于任務簇c（i），查找在c（j）（i>j）中沒有出現(xiàn)過的任務和c（j）的空閑時間，在空閑時間段中為沒有出現(xiàn)過的任務查找合適的時間段，時間段應滿足兩個條件：1）時間段的大小要大于或等于任務的計算時間；2）時間段的結束時間要在任務的后繼節(jié)點開始之前。若c（i）中所有未出現(xiàn)過的任務都能在c（j）的多個空閑時間段中找到滿足1）2）的時間段，則c（i）與c（j）聚簇。 2.1 聚簇算法 在分簇的過程中，已經計算出了每個任務的參數(shù)及整個工作流的最早完成時間makespan，根據(jù)參數(shù)進

17、行聚簇處理。以含有結束任務的簇開始向前聚簇： 1）記錄c（i）的空閑時間段（i=0，1，n，n是簇的個數(shù)）； 2）在 c（i+1）中查找沒有出現(xiàn)過的任務； 3）查看未出現(xiàn)過的任務的計算時間和后繼的最早開始時間，在c（j）（j=0，1，i）的空閑時間段里查找滿足空閑時間大于或等于是否要加上或等于加上或等于計算時間并且結束時間在最早開始時間之前的空閑時間段，若有就聚簇，把任務加入c（j）簇，否則不聚簇； 4）聚簇后，修改c（j）的空閑時間段，i=i+1，轉到步驟2），i>n-1結束； 5）不能聚簇的任務簇，i=i+1，轉到步驟1）， i>n-1結束。 根據(jù)聚簇算法對圖1分簇結果進行聚簇

18、，c（0）空閑時間段1720，c（1）中沒出現(xiàn)過的任務t9，c9=2，后繼est（t11）=20，則聚簇，即c（0）= t1，t5，t7，t10，t9，t11，c（0）的空閑時間段修改為1920；轉到步驟2），c（2）中沒有出現(xiàn)過的任務t8，c8=2，后繼est（t10）=13，則不能聚簇，根據(jù)步驟5）轉到步驟1）；直到結束。圖1的聚簇結果為： t1，t5，t7，t10，t9，t11、 t1，t5，t8、 t1，t4，t3，t6、 t1，t2，與是否1.2節(jié)？還是第1章？是1.2小節(jié)1.2節(jié)的分簇結果對比，發(fā)現(xiàn)少了兩個任務簇而整個工作流的最早完成時間不會被改變。 2.2 任務簇分配策略 經過聚

19、簇后進行任務調度，要根據(jù)科學工作流的類型和用戶的要求選擇處理機的類型，因為處理機的類型不同，性能和價格也不同。雖然減少處理機的使用個數(shù)、提高利用率可以降低執(zhí)行費用，但是根據(jù)需求選擇合適的處理機也很重要。 任務簇分配過程如下： 1）根據(jù)科學工作流的類型和用戶的需求選定處理機類型，初始化count=0。 2）統(tǒng)計處理機空閑時間段，也就是查看處理機空閑時間的開始時間和結束時間，并計算出時間段的大小，設置flag=0，放入隊列。 3）從隊列中為任務簇查找合適的處理機空閑時間段，如果有且flag=0，則count=count+1；然后修改flag=1。 4）如果沒有合適的空閑時間段則把任務簇劃分成小的任

20、務簇，執(zhí)行步驟3）。 5）修改處理機的空閑時間段，重復執(zhí)行步驟3）4）直到所有的任務簇分配完畢。 6）結束時，輸出占用的處理機個數(shù)count值和flag=1的處理機的空閑時間段。 聚簇算法的主要目的是減少處理機的使用個數(shù)，同時提高處理機空閑時間的利用率，而任務調度的主要目的是利用處理機的空閑時間進而提高處理機的利用率。圖1的科學工作流任務簇最終調度到4個處理機上執(zhí)行，與tdcs算法相比，處理機的使用個數(shù)減少了2個。 3 實驗與分析 為了驗證本文提出的云環(huán)境下基于聚簇的科學工作流執(zhí)行優(yōu)化策略的有效性，使用當前主流的開源云計算仿真平臺cloudsim進行仿真實驗，對cloudsim平臺進行了擴展，

21、利用ant工具通過對cloudsim仿真平臺源代碼中的datacenterbroker類、cloudlet類和virtualmachine類等分別進行重寫，實現(xiàn)了本文算法eoswca、tdcs算法和tds算法，然后對cloudsim重新編譯發(fā)布新生成的平臺，在新的平臺上進行仿真實驗。本文采用的編程工具是myeclipse 8.0。 本文從不同的方面對三種算法進行了比較，從工作流的執(zhí)行時間方面對eoswca算法和tds算法進行了比較，從處理機的使用個數(shù)及利用率方面對eoswca算法、tdcs算法和tds算法進行了比較。工作流的執(zhí)行時間用調度長度makespan來度量。為了更好地體現(xiàn)算法的比較結果

22、本文選用的任務數(shù)分別為 10，20，30，40，50，60，70，80，90，100的10種類型的工作流，每種類型的工作流隨機產生10個，計算它們的平均調度長度makespan、處理機個數(shù)、處理機利用率。任務的計算時間ci和通信時間mij是在1，20內隨機產生的。 由圖2可以看出，在工作流任務數(shù)小于50時，eoswca算法與tds算法的調度長度相差不大，但隨著任務數(shù)的增加，eoswca算法的優(yōu)勢越來越明顯。從圖中曲線的走勢也可以觀察出，隨著任務數(shù)的增加eoswca算法的makespan增長緩慢，可知eoswca算法適用于多任務的工作流。 圖3中，很明顯eoswca算法的處理機使用個數(shù)要少于td

23、s算法，并且隨著任務數(shù)的增加這種優(yōu)勢越來越突出；雖然eoswca算法相對于tdcs算法的優(yōu)勢沒有相對于tds算法的明顯，但是仍然絕對地優(yōu)于tdcs算法。整體來說，隨著任務數(shù)的增加，tds算法處理機使用個數(shù)增加較快尤其是任務數(shù)多于70以后，任務數(shù)每增加10個所需處理機的個數(shù)增幅很大，而后兩種算法沒有太大的起伏。 在任務數(shù)相同的情況下，使用處理機個數(shù)越少意味著處理機的利用率越高，如圖4所示。圖4是以eoswca算法的處理機空閑時間為分子，分別計算eoswca算法處理機空閑時間與tdcs算法、tds算法的處理機空閑時間的比值得到的。由圖可以看出tdcs算法與eoswca算法的比值在0.8左右，并且隨

24、著任務數(shù)的增加呈下降趨勢；tds算法與eoswca算法的比值總體來看在0.8以下，雖然有起伏但是整體呈下降趨勢。 結合圖24可知：tdcs算法不但調度長度小于tds算法，而且處理機的使用個數(shù)和利用率上也優(yōu)于tds算法；由于eoswca算法和tdcs算法的調度長度相差不大，所以只比較了處理機的個數(shù)和利用率，從哪里看出？把文中的圖2修改為附件中的圖2.實驗結果表明在調度長度基本一致的情況下，本文算法在處理機的個數(shù)和利用率上都絕對地優(yōu)于tdcs算法，并且隨著工作流任務數(shù)的增加本文算法的優(yōu)勢越明顯。 科學工作流執(zhí)行費用與處理機的個數(shù)和類型有關，若用戶沒有特殊要求，則根據(jù)科學工作流的類型選擇不同類型的處

25、理機；反之則要考慮用戶的需求選擇合適的處理機類型。無論在什么情況下，使用的處理機個數(shù)越少意味著執(zhí)行費用越低，所以本文采用聚簇的方法，在不增加執(zhí)行時間的前提下盡量減少任務簇的個數(shù)從而減少占用處理機的個數(shù)，達到降低執(zhí)行費用的目的。 處理機利用率相對值應說明本文算法的優(yōu)勢，為何只對比tdcs和tds，無eoswca？文中已說明圖4為eoswca處理機空閑時間分別與tdcs、tds的比值，eoswca看作單位1，所以沒有eoswca。 4 結語 針對科學工作流執(zhí)行過程中所涉及到的執(zhí)行時間、資源利用以及執(zhí)行費用問題，本文探討了一種云環(huán)境下科學工作流的執(zhí)行優(yōu)化策略，該策略通過任務復制來減少任務間的通信時間

26、，進而使科學工作流的最早完成時間最小化，在保證科學工作流最早完成時間不增加的前提下，對任務簇進一步進行聚簇，從而減少處理機的使用個數(shù)。實驗結果表明，本文提出的策略對于縮短科學工作流的完成時間、充分利用處理機的閑置時間并最終提高處理機的利用率和降低工作流的執(zhí)行費用有明顯的效果。下一步將針對混合并行科學工作流，探討其在云環(huán)境中的執(zhí)行優(yōu)化。 參考文獻： 1zhao y， li y， tian w， et al. scientificworkflowmanagementasaservice in the cloud c/ proceedings of the 2012 second internati

27、onal conference on cloud and green computing. piscataway： ieee， 2012： 97-104. 2chen w， altintas i， wang j， et al. enhancing smart rerun of kepler scientific workflows based on near optimum provenance caching in cloud c/ proceedings of the 2014 ieee world congress on services. piscataway： ieee， 2014：

28、 378-384. 3vaquero l m， roderomerino l， caceres j， et al. a break in the clouds： towards a cloud definition j. acm sigcomm computer communication review， 2008， 39（1）： 50-55. 4dejun j， pierre g， chi c h. ec2 performance analysis for resource provisioning of serviceoriented applications c/ proceedings

29、 of icsoc/servicewave 2009 workshops serviceoriented computing， lncs 6275. berlin：springer， 2010： 197-207. 5kim h， elkhamra y， rodero i， et al. autonomic management of application workflows on hybrid computing infrastructurej. scientific programmingsciencedriven cloud computing， 2011， 19（2/3）： 75-89

30、. 6shi x， xu k. utility maximization model of virtual machine scheduling in cloud environment j. chinese journal of computers， 2013， 36（2）： 252-262.（ 師雪霖，徐恪.云虛擬機資源分配的效用最大化模型j.計算機學報，2013，36（2）：252-262.）. 7yan g， yu j， yang x. twostep task scheduling strategy for scientific workflow on cloud computing

31、 platform j. journal of computer applications， 2013， 33（4）： 1006-1009.（閆歌，于炯，楊興耀.云計算環(huán)境下科學工作流兩階段任務調度策略j. 計算機應用，2013，33（4）：1006-1009.） 8bajaj r， agrawal d p. improving scheduling of tasks in a heterogeneous environment j. ieee transactions on parallel and distributed systems， 2004， 15（2）： 107-118. 9darbha s， agrawal d p. optimal scheduling algorithm for distributedmemory machinesj. ieee transactions on parallel and distributed systems， 1998，