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

1、云環(huán)境下基于聚簇的科學(xué)工作流執(zhí)行優(yōu)化策略 摘要：基于云環(huán)境下的科學(xué)工作流，以提高處理機利用率、降低費用為目標(biāo)，提出了一種基于聚簇的執(zhí)行優(yōu)化策略。該策略首先基于合理的任務(wù)復(fù)制和分簇，以實現(xiàn)關(guān)鍵任務(wù)的盡早調(diào)度；在此基礎(chǔ)上，對任務(wù)簇再次進(jìn)行聚集，以充分利用任務(wù)簇中任務(wù)間可能的空閑時間。實驗表明，該策略能夠提高任務(wù)的并行度，提前工作流的最早完成時間，并且在提高處理機的利用率和降低科學(xué)工作流的執(zhí)行費用方面有顯著效果。 關(guān)鍵詞：云計算；科學(xué)工作流；任務(wù)復(fù)制；聚簇；任務(wù)調(diào)度 中圖分類號： tp301.6 文獻(xiàn)標(biāo)志碼：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. 英文關(guān)鍵詞 key words：cloud computing； scientific workflow； task replication； cluster aggregation； task scheduling 0 引言 科學(xué)工作流（scientific workflow）是近年來出現(xiàn)的一種新的應(yīng)用泛型，可支持科學(xué)研究人員集成、構(gòu)造和協(xié)同分布異構(gòu)的數(shù)據(jù)、服務(wù)和軟件工具，提

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

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

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

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

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

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

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

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

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

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

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

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

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

18、，c（0）空閑時間段1720，c（1）中沒出現(xiàn)過的任務(wù)t9，c9=2，后繼est（t11）=20，則聚簇，即c（0）= t1，t5，t7，t10，t9，t11，c（0）的空閑時間段修改為1920；轉(zhuǎn)到步驟2），c（2）中沒有出現(xiàn)過的任務(wù)t8，c8=2，后繼est（t10）=13，則不能聚簇，根據(jù)步驟5）轉(zhuǎn)到步驟1）；直到結(jié)束。圖1的聚簇結(jié)果為： 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é)的分簇結(jié)果對比，發(fā)現(xiàn)少了兩個任務(wù)簇而整個工作流的最早完成時間不會被改變。 2.2 任務(wù)簇分配策略 經(jīng)過聚

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

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

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

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

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

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

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

26、，進(jìn)而使科學(xué)工作流的最早完成時間最小化，在保證科學(xué)工作流最早完成時間不增加的前提下，對任務(wù)簇進(jìn)一步進(jìn)行聚簇，從而減少處理機的使用個數(shù)。實驗結(jié)果表明，本文提出的策略對于縮短科學(xué)工作流的完成時間、充分利用處理機的閑置時間并最終提高處理機的利用率和降低工作流的執(zhí)行費用有明顯的效果。下一步將針對混合并行科學(xué)工作流，探討其在云環(huán)境中的執(zhí)行優(yōu)化。 參考文獻(xiàn)： 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.計算機學(xué)報，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)境下科學(xué)工作流兩階段任務(wù)調(diào)度策略j. 計算機應(yīng)用，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，