程慧敏 李學(xué)俊,* 吳 洋 朱二周

1(安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)2(安徽大學(xué)計算智能與信號處理重點實驗室 安徽 合肥 230039)

云環(huán)境下基于多目標優(yōu)化的科學(xué)工作流數(shù)據(jù)布局策略

程慧敏1李學(xué)俊1,2*吳 洋1朱二周2

1(安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)2(安徽大學(xué)計算智能與信號處理重點實驗室 安徽 合肥 230039)

針對傳統(tǒng)科學(xué)工作流數(shù)據(jù)布局策略在減少數(shù)據(jù)傳輸時間的同時，不能兼顧數(shù)據(jù)中心間的負載均衡，提出一種基于多目標優(yōu)化的數(shù)據(jù)布局策略。首先生成固定數(shù)據(jù)集布局方案，然后利用多目標優(yōu)化算法KnEA對非固定數(shù)據(jù)集進行布局，最終得到全局布局方案。KnEA算法利用knee points比普通非支配個體有著更好的收斂性特征，并綜合考慮多個優(yōu)化目標間的平衡，因而可以取得數(shù)據(jù)傳輸時間和負載均衡都很好的數(shù)據(jù)布局方案。通過對比實驗證明了該數(shù)據(jù)布局策略的有效性。

云計算 科學(xué)工作流 數(shù)據(jù)布局 多目標優(yōu)化 負載均衡

0 引 言

在現(xiàn)代科學(xué)應(yīng)用領(lǐng)域中天文學(xué)[1]、高能物理學(xué)[2]、生物信息學(xué)[3]等通常都是計算密集型和數(shù)據(jù)密集型的應(yīng)用，它們往往包含成千上萬個任務(wù)，并且需要處理TB級或者PB量級的數(shù)據(jù)，因而需要大量的計算資源和存儲資源?？茖W(xué)工作流作為一種重要的機制可以幫助科學(xué)家自動執(zhí)行這些科學(xué)仿真和數(shù)據(jù)分析過程[4]。目前，許多科學(xué)家通常將科學(xué)工作流部署在網(wǎng)格和集群等分布式環(huán)境上。然而，建立這樣的系統(tǒng)是非常昂貴的，而且申請訪問這些系統(tǒng)也需要花費大量的時間[8]。云計算技術(shù)在2007年被提出[5]，由于它擁有全球性的分布式數(shù)據(jù)中心，因而能夠支持大規(guī)模的應(yīng)用的快速發(fā)展[6]。云計算能夠為用戶提供大量的存儲空間和高性能的計算資源，并以按量付費的方式收取費用。它的高效、靈活的特點為科學(xué)工作流的執(zhí)行提供了一種全新的方式[7]。

云計算環(huán)境下的數(shù)據(jù)中心都有它獨特的特征，例如存儲空間和計算能力。由于這些特征的限制，將科學(xué)工作流中大量的數(shù)據(jù)集存放在某個數(shù)據(jù)中心是不合理的[10]。因此，將科學(xué)工作流部署在云計算平臺上面臨著數(shù)據(jù)布局方面的挑戰(zhàn)。數(shù)據(jù)布局問題是在滿足數(shù)據(jù)中心容量要求的前提下，將數(shù)據(jù)集布局到數(shù)據(jù)中心上。顯然，它是NP難問題，因此可以簡化成背包問題。目前存在的數(shù)據(jù)布局策略主要是基于聚類算法[8,11]和智能算法[10]，包括k-means算法，數(shù)據(jù)集和任務(wù)協(xié)同調(diào)度算法，遺傳算法GA(Genetic Algorithm)和PSO(Particle Swarm Optimization)算法等，其中k-means算法[8]是最具代表性的算法。k-means算法和GA算法可以將依賴關(guān)系強的數(shù)據(jù)集布置在同一個數(shù)據(jù)中心上，從而減少科學(xué)工作流執(zhí)行過程中數(shù)據(jù)傳輸時間。但它們忽略了數(shù)據(jù)中心間負載均衡，導(dǎo)致數(shù)據(jù)集被布局在少量的數(shù)據(jù)中心上，從而影響了整個數(shù)據(jù)中心的計算能力，進而降低了科學(xué)工作流的執(zhí)行效率。因此，一個高效的數(shù)據(jù)布局策略應(yīng)同時兼顧到數(shù)據(jù)傳輸時間和數(shù)據(jù)中心間的負載均衡。

基于上述的分析，對數(shù)據(jù)集進行布局時，同時考慮數(shù)據(jù)傳輸時間和負載均衡是很困難的，傳統(tǒng)的數(shù)據(jù)布局方法很難獲取高效的數(shù)據(jù)布局方案。本文運用基于進化算法的多目標優(yōu)化方法[9]對數(shù)據(jù)集進行布局。多目標優(yōu)化方法即同時優(yōu)化多個目標的算法，它綜合考慮多個優(yōu)化目標間的權(quán)衡，并能夠最終獲得一組最優(yōu)解。故利用多目標優(yōu)化方法可以兼顧數(shù)據(jù)布局策略中的數(shù)據(jù)傳輸時間和負載均衡。解決多目標優(yōu)化問題通常采用的是基于進化算法的啟發(fā)式方法，它有著自適應(yīng)、避免局部最優(yōu)、黑盒式求解等諸多優(yōu)點[14]，可以有效解決科學(xué)工作流中數(shù)據(jù)布局問題。

1 相關(guān)工作

科學(xué)工作流的數(shù)據(jù)布局是一個非常重要且富有挑戰(zhàn)性的問題，它對于減少科學(xué)工作流的執(zhí)行費用和提高科學(xué)工作流的執(zhí)行效率有著重要的意義，因此，合理的數(shù)據(jù)布局策略至關(guān)重要。目前已有學(xué)者對此進行了探索和研究，主要包括聚類算法[8,11]和智能算法[10]的數(shù)據(jù)布局策略的相關(guān)研究。此外，我們將介紹基于進化算法的多目標優(yōu)化方法。

在聚類算法方面，文獻[8]提出了一種基于k-means算法的數(shù)據(jù)布局策略。該策略首先建立數(shù)據(jù)依賴矩陣，矩陣中每個元素表示兩個數(shù)據(jù)集的公共任務(wù)個數(shù)。然后利用BEA算法對依賴矩陣進行聚類變換得到聚類矩陣，然后將聚類矩陣劃分成若干個集合。最后將劃分的集合布局至相應(yīng)的數(shù)據(jù)中心，這樣就盡可能將依賴度高的數(shù)據(jù)集布局在同一個數(shù)據(jù)中心，從而減少了數(shù)據(jù)傳輸時間。文獻[11]提出了一種基于圖切割的任務(wù)和數(shù)據(jù)集協(xié)同調(diào)度策略。它根據(jù)數(shù)據(jù)集的固定存儲特征將數(shù)據(jù)起源圖切割成子圖，并不斷重復(fù)這個過程直到該子圖所包含的數(shù)據(jù)集能夠滿足數(shù)據(jù)中心的容量要求，最后將任務(wù)和數(shù)據(jù)集布局到合理的數(shù)據(jù)中心。在智能算法方面，文獻[10]在能夠反映負載均衡和數(shù)據(jù)傳輸時間兩目標的適應(yīng)值函數(shù)的基礎(chǔ)上，使用遺傳算法對科學(xué)工作流中數(shù)據(jù)集進行布局，該方法在負載均衡方面和負載均衡方面均取得了很好的效果。

上述的數(shù)據(jù)布局策略要么從單一目標(例如數(shù)據(jù)傳輸時間)來考慮科學(xué)工作流的數(shù)據(jù)布局問題，要么雖然考慮了數(shù)據(jù)傳輸時間和負載均衡兩個目標，但不能夠?qū)?shù)據(jù)傳輸時間和負載均衡兩個目標同時進行優(yōu)化，因而都不能夠有效地提高科學(xué)工作流的執(zhí)行效率?；谶M化算法的多目標優(yōu)化方法可同時優(yōu)化多個目標，因而，可以有效解決數(shù)據(jù)布局中數(shù)據(jù)傳輸時間和負載均衡不能同時兼顧的難題。多目標優(yōu)化問題在工程學(xué)，生物學(xué)和經(jīng)濟學(xué)等領(lǐng)域中非常普遍[12-15]。多目標優(yōu)化問題中各個目標間通常是互相矛盾的，目標函數(shù)可能具有多峰、不連續(xù)、不可導(dǎo)甚至離散等特點，無法通過傳統(tǒng)的最優(yōu)化方法或算法來解決。作為一種啟發(fā)式的智能搜索算法，進化算法能有效地解決多目標優(yōu)化問題并已經(jīng)得到了越來越多的研究證明[17]。

在多目標優(yōu)化方法方面，文獻[15]提出了一種基于非支配排序的多目標優(yōu)化算法(NSGA-II)，它利用非支配排序算法以及擁擠距離策略，從當(dāng)前父子代的聯(lián)合種群中選出參與下一代進化的種群，兼顧了種群的收斂性與分布性。文獻[9]在NSGA-II 研究和分析的基礎(chǔ)上，提出的一種基于knee points的多目標優(yōu)化算法(KnEA)。knee points是前沿面上具有更好收斂性的一些個體。該算法通過一種自適應(yīng)的方法識別出種群中的knee points，并在交配池選擇和環(huán)境選擇操作中優(yōu)先考慮它們，從而加速種群的收斂和維護種群的多樣性。與多個主流的多目標進化算法的實驗對比說明，KnEA能在多目標優(yōu)化問題上獲得更好的性能表現(xiàn)。

本文在對數(shù)據(jù)集進行布局時，將綜合考慮數(shù)據(jù)傳輸時間和負載均衡兩個重要因素。運用基于進化算法的多目標優(yōu)化方法(KnEA)對數(shù)據(jù)集進行布局，從數(shù)據(jù)傳輸時間和負載均衡兩個方面對數(shù)據(jù)布局方案進行同時優(yōu)化，取得了顯著的效果。

2 科學(xué)工作流的描述和問題分析

首先介紹云計算環(huán)境下科學(xué)工作流數(shù)據(jù)布局問題的相關(guān)定義，具體包括云環(huán)境、科學(xué)工作流、數(shù)據(jù)集、任務(wù)。然后對數(shù)據(jù)布局中所面臨的問題進行分析。

2.1 相關(guān)定義

定義1 云計算環(huán)境表示為多個分布式數(shù)據(jù)中心組成的集合DC={dc1,dc2,…,dcm}。單個數(shù)據(jù)中心dci可表示為dci={size,cap},其中size表示數(shù)據(jù)中心dci的容量,cap表示數(shù)據(jù)中心dci的計算能力，并用執(zhí)行同一任務(wù)所需的時間的倒數(shù)來量化表示。

定義2 科學(xué)工作流定義為G={T,C,DS}。其中T={t1,t2,…,tn}表示工作流G的所有任務(wù)，C表示任務(wù)之間控制流的鄰接矩陣，DS={d1,d2,…,dn}表示G中所有數(shù)據(jù)集的集合。

定義4 根據(jù)數(shù)據(jù)集存放位置是否受限，可以將數(shù)據(jù)集分為固定數(shù)據(jù)集和非固定數(shù)據(jù)集。將DS中所有固定數(shù)據(jù)集組成的集合記為DSfix。對?di∈DSfix，記di指定存放的數(shù)據(jù)中心編號為fix_loc(di)。DS中所有非固定數(shù)據(jù)集組成的集合記為DSflex。

2.2 問題分析

下面給出一個簡單的科學(xué)工作流的實例如圖1所示，假設(shè)云計算平臺有兩個數(shù)據(jù)中心dc1、dc2，該科學(xué)工作流有6個數(shù)據(jù)集d1、d2、d3、d4、d5、d6，每個數(shù)據(jù)集大小均為1GB,其中d2是存放在數(shù)據(jù)中心dc1上的固定數(shù)據(jù)集，d6是存放在數(shù)據(jù)中心dc2上的固定數(shù)據(jù)集。

圖1 科學(xué)工作流實例

對于圖1中科學(xué)工作流，基于k-means算法的數(shù)據(jù)布局策略得到數(shù)據(jù)布局方案，如圖2(a)所示。接著從優(yōu)化數(shù)據(jù)傳輸時間和負載均衡的多目標優(yōu)化角度出發(fā)，得到優(yōu)化后的數(shù)據(jù)布局方案如圖2(b)所示。

圖2 兩種數(shù)據(jù)布局方案

根據(jù)將數(shù)據(jù)集進行跨數(shù)據(jù)中心的傳輸代價比任務(wù)調(diào)度的代價大這一原則[8]，在上述兩種數(shù)據(jù)布局方案中，將任務(wù)t1、t2調(diào)度到數(shù)據(jù)中心dc1，任務(wù)t3、t4、t5調(diào)度到數(shù)據(jù)中心dc2。基于k-means算法的數(shù)據(jù)布局方案在科學(xué)工作流的執(zhí)行過程中，數(shù)據(jù)集d3、d4、d5,從數(shù)據(jù)中心dc2傳輸?shù)綌?shù)據(jù)中心dc1，需要的傳輸量為3GB；數(shù)據(jù)中心dc1的負載量為2GB,dc2的負載量為4GB,因此數(shù)據(jù)中心間負載不能保持均衡?；诙嗄繕藘?yōu)化的數(shù)據(jù)布局方案在科學(xué)工作流執(zhí)行過程中，數(shù)據(jù)集d3、d4從數(shù)據(jù)中心dc2傳輸?shù)綌?shù)據(jù)中心dc1，需要的傳輸量為2GB，同比減少33%；數(shù)據(jù)中心dc1和dc2的負載量均為3GB，因此數(shù)據(jù)中心間負載保持均衡。因而，基于k-means算法的數(shù)據(jù)布局策略不能很好地解決數(shù)據(jù)布局問題。

3 基于多目標優(yōu)化的數(shù)據(jù)布局算法

運用基于多目標優(yōu)化的數(shù)據(jù)布局算法對科學(xué)工作流中數(shù)據(jù)集進行布局，它在減少數(shù)據(jù)傳輸時間的同時，兼顧了數(shù)據(jù)中心間負載均衡。下面將首先介紹數(shù)據(jù)布局方案的數(shù)據(jù)傳輸時間和負載均衡兩種評價指標，然后給出數(shù)據(jù)布局算法。

3.1 數(shù)據(jù)布局評價指標

數(shù)據(jù)傳輸時間：采用將任務(wù)調(diào)度至執(zhí)行該任務(wù)所需數(shù)據(jù)傳輸時間最小的數(shù)據(jù)中心的任務(wù)調(diào)度策略。如果每個任務(wù)需要的數(shù)據(jù)集不在該任務(wù)存放的數(shù)據(jù)中心，則需要從其它數(shù)據(jù)中心進行傳輸。數(shù)據(jù)傳輸時間即科學(xué)工作流全部執(zhí)行時，所有任務(wù)需要的跨數(shù)據(jù)中心間數(shù)據(jù)集傳輸時間之和。

Time(dk,dci,dcj)表示dk從源數(shù)據(jù)中心dci傳輸?shù)侥繕藬?shù)據(jù)中心dcj所需要的時間,如式(1)所示。

Time(dk,dci,dcj)=dk·ds/bij

(1)

其中，bij表示數(shù)據(jù)中心dci和數(shù)據(jù)中心dcj間的帶寬。Time(ti,dci)表示當(dāng)任務(wù)ti調(diào)度到數(shù)據(jù)中心dci時，ti所需的輸入數(shù)據(jù)集不在dci時，要從其他數(shù)據(jù)中心傳輸數(shù)據(jù)集所需的時間之和。如式(2)所示。

(2)

工作流執(zhí)行過程中，數(shù)據(jù)中心計算能力動態(tài)變化，負載均衡是一個動態(tài)的均衡。然而本文研究靜態(tài)數(shù)據(jù)布局方案，假設(shè)每個數(shù)據(jù)中心的計算能力相同，負載均衡僅和數(shù)據(jù)中心的存儲情況有關(guān)。文獻[10,11]采用數(shù)據(jù)中心使用率的標準差來描述數(shù)據(jù)中心間負載均衡，但數(shù)據(jù)中心的容量非常大，數(shù)據(jù)集大小對于數(shù)據(jù)中心的容量的比例很小，故計算結(jié)果并不準確，本文使用數(shù)據(jù)中心使用量的標準差來描述數(shù)據(jù)中心間負載均衡，如式(3)所示。

(3)

(4)

3.2 數(shù)據(jù)布局算法

下面首先對數(shù)據(jù)布局方案的編碼規(guī)則進行介紹，然后給出本文的數(shù)據(jù)布局算法。

3.2.1 編碼規(guī)則

常見的編碼規(guī)則有二進制編碼、格雷碼編碼、符號編碼、浮點數(shù)編碼和整數(shù)編碼等[16]。本文采用整數(shù)編碼規(guī)則，每個個體代表一個數(shù)據(jù)布局方案。通過整數(shù)編碼規(guī)則，可以避免出現(xiàn)將數(shù)據(jù)集布局到編號不存在的數(shù)據(jù)中心上的無效個體。假設(shè)有m個數(shù)據(jù)中心和n個數(shù)據(jù)集，代表數(shù)據(jù)布局方案的個體由n個整數(shù)組成:(g1,g2,…,gn)1≤gj≤m(j=1,2,…,n)gj表示第j個數(shù)據(jù)集所在的數(shù)據(jù)中心編號。

3.2.2 算法描述

本文的數(shù)據(jù)布局策略是首先將固定數(shù)據(jù)集布局到相應(yīng)的數(shù)據(jù)中心得到固定數(shù)據(jù)集布局方案DPfix，然后運用多目標進化算法(KnEA)對非固定數(shù)據(jù)集進行布局得到非固定數(shù)據(jù)集布局方案DPflex，最后，對兩者進行合并，得到全局數(shù)據(jù)布局方案DP。

算法 基于KnEA的數(shù)據(jù)布局算法

輸入：數(shù)據(jù)中心集合DC，數(shù)據(jù)集合DS

輸出：數(shù)據(jù)布局方案DP

主要步驟：

1.DPfix=[DPfix,fix_loc(di)]?di∈DSfix;

2.P=random(DSflex,N);

//隨機生成N個個體

3.whilenottermination()do

4.Q=mating_selection(P,K,N);

//交配池選擇

5.Q=P∪variation(Q);

//子代交叉和變異處理

6.F=nondominated_sort(P);

//非支配排序

7. [K,r,t]=find_knee_point(F,T,r,t);

//查找kneepoints

8.P=environment_selection(F,K,N);

//自然選擇

9.end

10.DPflex=getbest(P)

//選出最佳的個體

11.DP=DPfix+DPflex;

12.ReturnDP;

第1行將固定數(shù)據(jù)集布局到該數(shù)據(jù)集指定存放的數(shù)據(jù)中心，得到固定數(shù)據(jù)集布局方案DPfix。

第2～12行得到非固定數(shù)據(jù)集布局方案DPflex，具體的，第2行隨機生成N個非固定數(shù)據(jù)集布局方案并記為P。第4～5行根據(jù)交配池選擇原則的三個準則即個體間的支配關(guān)系、個體是否為kneepoint以及個體的加權(quán)距離，則從P中選出N個個體記為Q,并對Q中個體進行交叉變異，然后和P中個體進行合并。第6行將P中個體進行非支配排序，并將排序后結(jié)果記為F。第7行將F中每個前沿面里符合kneepoint條件的個體放入到K中，其中r和t是自適應(yīng)參數(shù)，T是算法中預(yù)設(shè)參數(shù)。第8行綜合F和K的結(jié)果，選出N個優(yōu)秀的個體作為下一次迭代的輸入。算法的細節(jié)步驟參見文獻[9]。第10行表示從P中選出一個最佳的個體(即非固定數(shù)據(jù)集布局方案)DPflex。

第11行,將固定數(shù)據(jù)集布局方案DPfix和非固定數(shù)據(jù)布局方案DPflex進行合并，得到所有數(shù)據(jù)集的布局方案DP。

4 實 驗

將本文提出的基于多目標優(yōu)化的數(shù)據(jù)布局策略(KnEA)和基于聚類算法的數(shù)據(jù)布局策略(k-means)[8]、基于遺傳算法的數(shù)據(jù)布局策略(GA)[10]進行對比試驗。隨機生成仿真科學(xué)工作流，然后使用本文策略、聚類策略和基于遺傳算法的數(shù)據(jù)布局策略得到各自的數(shù)據(jù)布局方案，運行仿真的科學(xué)工作流，并記錄該過程中數(shù)據(jù)傳輸時間和負載均衡。采用控制變量法給出數(shù)據(jù)集個數(shù)，數(shù)據(jù)中心個數(shù)，固定數(shù)據(jù)集比例變化時的數(shù)據(jù)傳輸時間和負載均衡如圖3-圖5所示。實驗過程中,隨機生成10個任務(wù)，數(shù)據(jù)集大小為10～1 000MB的科學(xué)工作流，數(shù)據(jù)中心間帶寬為10MB/s。KnEA算法迭代次數(shù)為100次，種群初始個體為20個，自適應(yīng)參數(shù)r初始值設(shè)為1，t的初始值設(shè)為0，預(yù)設(shè)參數(shù)T設(shè)為0.5。遺傳算法的迭代次數(shù)為100次，種群初始個體為20個，變異概率為0.1。為了保證結(jié)果的可靠性，每一個科學(xué)工作流在保持實驗環(huán)境配置不變的情況下運行100次后取平均值作為測試結(jié)果。

4.1 數(shù)據(jù)集個數(shù)

圖3給出數(shù)據(jù)中心個數(shù)5個，固定數(shù)據(jù)集比例20%的情況下，隨著數(shù)據(jù)集個數(shù)的增加，數(shù)據(jù)傳輸時間和負載均衡的變化趨勢。在數(shù)據(jù)傳輸時間方面，本文的策略稍優(yōu)于k-means策略；和GA策略比較，本文策略效果略差。但在負載均衡方面，當(dāng)數(shù)據(jù)集個數(shù)大于30且不斷增加時，本文的策略優(yōu)于k-means策略和GA策略，且優(yōu)勢尤為明顯。

圖3 數(shù)據(jù)集個數(shù)

4.2 數(shù)據(jù)中心個數(shù)

圖4給出數(shù)據(jù)集個數(shù)40個，固定數(shù)據(jù)集比例20%的情況下，隨著數(shù)據(jù)中心個數(shù)的增加，數(shù)據(jù)傳輸時間和負載均衡的變化趨勢。本文的策略在數(shù)據(jù)傳輸時間方面介于k-means策略和GA策略之間。但在負載均衡方面，本文的策略要好于k-means策略，且相比GA策略，本文的策略優(yōu)勢十分明顯。

圖4 數(shù)據(jù)中心個數(shù)

4.3 固定數(shù)據(jù)集比例

圖5給出數(shù)據(jù)集個數(shù)40個，數(shù)據(jù)中心個數(shù)5個的情況下，隨著固定數(shù)據(jù)集比例的增加，數(shù)據(jù)傳輸時間和負載均衡的變化趨勢。在數(shù)據(jù)傳輸時間方面，本文的策略稍優(yōu)于k-means策略，和GA策略基本持平。但在負載均衡方面，本文的策略要明顯好于GA策略，但并不優(yōu)于k-means策略，這主要是由于隨著固定數(shù)據(jù)集比例的增大，更多的數(shù)據(jù)集存放在指定的數(shù)據(jù)中心，聚類的中心在增多，導(dǎo)致基于聚類的k-means數(shù)據(jù)布局策略更具優(yōu)勢。

圖5 固定數(shù)據(jù)集比例

綜上，k-means策略和GA策略是能將依賴性較強的數(shù)據(jù)集布局在一起，使得數(shù)據(jù)集集中在較少的數(shù)據(jù)中心上。實驗結(jié)果顯示，它可以減少數(shù)據(jù)傳輸時間，但它導(dǎo)致更多的數(shù)據(jù)中心處于未利用狀態(tài)，從而使數(shù)據(jù)中心間負載失去平衡。而本文的數(shù)據(jù)布局策略從多目標優(yōu)化思想出發(fā)，在數(shù)據(jù)傳輸時間方面與k-means策略和GA策略基本持平，具有同等的優(yōu)勢，但在負載均衡方面明顯優(yōu)于k-means策略和GA策略。因此，本文的數(shù)據(jù)布局策略可以有效提高科學(xué)工作流的執(zhí)行效率。

5 結(jié) 語

本文首先分析了科學(xué)工作流在云計算平臺上運行時所面臨的挑戰(zhàn)，特別是對數(shù)據(jù)集進行布局時，不能在減少數(shù)據(jù)傳輸時間的同時保持數(shù)據(jù)中心間負載均衡。然后對該問題進行分析，并運用基于多目標優(yōu)化的數(shù)據(jù)布局策略對數(shù)據(jù)集進行布局，并與聚類數(shù)據(jù)布局策略進行對比實驗。實驗結(jié)果表明，本文的策略不僅可以減少數(shù)據(jù)傳輸時間，而且在保持數(shù)據(jù)中心間負載均衡方面具有很大的優(yōu)勢。未來我們計劃運用多目標進化算法對數(shù)據(jù)布局的同時，對任務(wù)進行調(diào)度。在減少數(shù)據(jù)傳輸時間和保持數(shù)據(jù)中心負載均衡的情況下，減少任務(wù)的執(zhí)行時間，從而高效地提高科學(xué)工作流的執(zhí)行效率。

[1]DeelmanE,BlytheJ,GilY,etal.Pegasus:Mappingscientificworkflowsontothegrid[C]//inEuropeanAcrossGridsConference.Nicosia,Cypurs,2004:11-20.

[2]LudascherB,AltintasI,BerkleyC,etal.ScientificworkflowmanagementandtheKeplersystem[J].ConcurrencyandComputation:PracticeandExperience,2005,18(10):1039-1065.

[3]OinnT,AddisM,FerrisJ,etal.Taverna:Atoolforthecompositionandenactmentofbioinformaticsworkflows[J].Bioinformatics,2004,20(17):3045-3054.

[4]RenK,ChenJ,XiaoN,etal.BuildingQuickServiceQuerylist(QSQL)tosupportautomatedservicediscoveryforscientificworkflow[J].Concurrency&ComputationPractice&Experience,2009,21(16):2099-2117.

[5]AaronWeiss.Computinginthecloud.net[J].Worker,2007,11(4):16-25.

[6]ZhangRui,WuK,WangJ.Onlineresourceschedulingunderconcavepricingforcloudcomputing[C]//QualityofService(IWQoS),22ndInternationalSymposiumofIEEE,2014:51-60.

[7]ZhaoY,LiYF,LuSY.Aserviceframeworkforscientificworkflowmanagementinthecloud[C]//IEEETransactionsonServicesComputing,2014:1-14.

[8]YuanD,YangY,LiuX,etal.Adataplacementstrategyinscientificcloudworkflows[J].FutureGenerationComputerSystems,2010,26(8):1200-1214.

[9]ZhangXY,TianY,JinY.AKneePointDrivenEvolutionaryAlgorithmforMany-ObjectiveOptimization[C].IEEETransactionsonEvolutionaryComputation,2014:1-17.

[10]ErDunZ,XingxingX,YiC.Adataplacementstrategybasedongeneticalgorithmforscientificworkflows[C]//ComputationalIntelligenceandSecurity(CIS), 2012EighthInternationalConference,Guangzhou,2012.IEEE,146-149.

[11]DengKF,SongJQ,RenKJ,etal.Graph-CutBasedCoschedulingStrategyTowardsEfficientExecutionofScientificWorkflowsinCollaborativeCloudEnvironments[C]//Proceedingsofthe2011IEEE/ACM12thInternationalConferenceonGridComputing,Lyon,2011:34-41.

[12]HerreroJG,BerlangaA,LopezJMM.EffectiveEvolutionaryAlgorithmsforMany-SpecificationsAttainment:ApplicationtoAirTrafficControlTrackingFilters[J].IEEETransactionsonEvolutionaryComputation,2009,13(1):151-168.

[13]PonsichA,JaimesAL,CoelloCAC.ASurveyonMultiobjectiveEvolutionaryAlgorithmsfortheSolutionofthePortfolioOptimizationProblemandOtherFinanceandEconomicsApplications[J].IEEETransactionsonEvolutionaryComputation,2013,17(3):321-344.

[14]HandlJ,KellDB,KnowlesJ.MultiobjectiveOptimizationinBioinformaticsandComputationalBiology[J].IEEE/ACMTransactionsonComputationalBiology&Bioinformatics,2007,4(2):279-292.

[15]DebK,PratapA,AgarwalS,etal.AFastAndElitistMultiobjectiveGeneticAlgorithm:NSGA-II[J].IEEETransactionsonEvolutionaryComputation,2002,6(2):182-197.

[16] 吉根林.遺傳算法研究綜述[J].計算機應(yīng)用與軟件,2004,21(2):69-73.

[17]ZhouA,QuBY,LiH,etal.Multiobjectiveevolutionaryalgorithms:Asurveyofthestateoftheart[J].SwarmandEvolutionaryComputation,2011,1(1):32-49.

DATA PLACEMENT STRATEGY BASED ON MULTI-OBJECTIVE OPTIMIZATION FORSCIENTIFIC WORKFLOWS IN CLOUD COMPUTING ENVIRONMENT

Cheng Huimin1Li Xuejun1,2*Wu Yang1Zhu Erzhou2

1(SchoolofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)2(IntelligentComputingandSignalProcessingLaboratory,AnhuiUniversity,Hefei230039,Anhui,China)

The traditional data placement strategies for scientific workflows fail to monitor the load balancing between data centers while reducing the data transfer time. Thus, a data placement strategy based on multi-objective optimization is proposed. Firstly, the strategy generates the placement scheme of fixed datasets. Then it uses multi-objective optimization-based algorithm KnEA(Knee Point Driven Evolutionary Algorithm) to place flexible datasets, and then obtain the placement scheme of all datasets. The algorithm KnEA takes advantage of characteristic of knee points which can get good convergence comparing to other non-dominated sorting individuals, and comprehensively deals with the balance between multiple objectives. That’s why the data placement strategy is able to perform well in data transferring time and load balancing. The effectiveness of the proposed method is tested by comparison with two other strategies.

Cloud computing Scientific workflows Data placement Multi-objective optimization Load balancing

2015-10-16。國家自然科學(xué)

61300169)。程慧敏，碩士生，主研領(lǐng)域：云計算和科學(xué)工作流。李學(xué)俊，副教授。吳洋，碩士生。朱二周，講師。

TP393

A

10.3969/j.issn.1000-386x.2017.03.001