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

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

1(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)2(安徽大學(xué)計(jì)算智能與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室 安徽 合肥 230039)

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

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

1(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)2(安徽大學(xué)計(jì)算智能與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室 安徽 合肥 230039)

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

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

0 引 言

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

云計(jì)算環(huán)境下的數(shù)據(jù)中心都有它獨(dú)特的特征，例如存儲(chǔ)空間和計(jì)算能力。由于這些特征的限制，將科學(xué)工作流中大量的數(shù)據(jù)集存放在某個(gè)數(shù)據(jù)中心是不合理的[10]。因此，將科學(xué)工作流部署在云計(jì)算平臺(tái)上面臨著數(shù)據(jù)布局方面的挑戰(zhàn)。數(shù)據(jù)布局問題是在滿足數(shù)據(jù)中心容量要求的前提下，將數(shù)據(jù)集布局到數(shù)據(jù)中心上。顯然，它是NP難問題，因此可以簡(jiǎn)化成背包問題。目前存在的數(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)系強(qiáng)的數(shù)據(jù)集布置在同一個(gè)數(shù)據(jù)中心上，從而減少科學(xué)工作流執(zhí)行過程中數(shù)據(jù)傳輸時(shí)間。但它們忽略了數(shù)據(jù)中心間負(fù)載均衡，導(dǎo)致數(shù)據(jù)集被布局在少量的數(shù)據(jù)中心上，從而影響了整個(gè)數(shù)據(jù)中心的計(jì)算能力，進(jìn)而降低了科學(xué)工作流的執(zhí)行效率。因此，一個(gè)高效的數(shù)據(jù)布局策略應(yīng)同時(shí)兼顧到數(shù)據(jù)傳輸時(shí)間和數(shù)據(jù)中心間的負(fù)載均衡。

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

1 相關(guān)工作

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

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

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

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

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

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

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

2.1 相關(guān)定義

定義1 云計(jì)算環(huán)境表示為多個(gè)分布式數(shù)據(jù)中心組成的集合DC={dc1,dc2,…,dcm}。單個(gè)數(shù)據(jù)中心dci可表示為dci={size,cap},其中size表示數(shù)據(jù)中心dci的容量,cap表示數(shù)據(jù)中心dci的計(jì)算能力，并用執(zhí)行同一任務(wù)所需的時(shí)間的倒數(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。對(duì)?di∈DSfix，記di指定存放的數(shù)據(jù)中心編號(hào)為fix_loc(di)。DS中所有非固定數(shù)據(jù)集組成的集合記為DSflex。

2.2 問題分析

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

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

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

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

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

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

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

3.1 數(shù)據(jù)布局評(píng)價(jià)指標(biāo)

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

Time(dk,dci,dcj)表示dk從源數(shù)據(jù)中心dci傳輸?shù)侥繕?biāo)數(shù)據(jù)中心dcj所需要的時(shí)間,如式(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時(shí)，ti所需的輸入數(shù)據(jù)集不在dci時(shí)，要從其他數(shù)據(jù)中心傳輸數(shù)據(jù)集所需的時(shí)間之和。如式(2)所示。

(2)

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

(3)

(4)

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

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

3.2.1 編碼規(guī)則

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

3.2.2 算法描述

本文的數(shù)據(jù)布局策略是首先將固定數(shù)據(jù)集布局到相應(yīng)的數(shù)據(jù)中心得到固定數(shù)據(jù)集布局方案DPfix，然后運(yùn)用多目標(biāo)進(jìn)化算法(KnEA)對(duì)非固定數(shù)據(jù)集進(jìn)行布局得到非固定數(shù)據(jù)集布局方案DPflex，最后，對(duì)兩者進(jìn)行合并，得到全局?jǐn)?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);

//隨機(jī)生成N個(gè)個(gè)體

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)

//選出最佳的個(gè)體

11.DP=DPfix+DPflex;

12.ReturnDP;

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

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

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

4 實(shí) 驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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

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

TP393

A

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