馬飛

摘要：科學(xué)工作流應(yīng)用是一種復(fù)雜且數(shù)據(jù)密集型的應(yīng)用，常應(yīng)用于結(jié)構(gòu)生物學(xué)、高能物理學(xué)和神經(jīng)學(xué)等涉及分布式數(shù)據(jù)源的學(xué)科。數(shù)據(jù)分散存儲在基于互聯(lián)網(wǎng)的云計(jì)算平臺上，致使科學(xué)工作流在執(zhí)行時(shí)伴隨著大量的數(shù)據(jù)傳輸。云計(jì)算是一種按使用量付費(fèi)的模式，數(shù)據(jù)傳輸產(chǎn)生傳輸費(fèi)用，尤其在多個(gè)工作流相互協(xié)同的情況下，將產(chǎn)生更高的傳輸成本。該文從全局的角度建立基于多工作流數(shù)據(jù)依賴圖的傳輸成本模型，研究基于二進(jìn)制粒子群算法（BPSO）的數(shù)據(jù)布局優(yōu)化策略，從而減少對云計(jì)算傳輸資源的租賃費(fèi)用。

關(guān)鍵詞：云計(jì)算；工作流系統(tǒng)；云工作流；數(shù)據(jù)布局；二進(jìn)制粒子群算法

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）10-2418-03

Abstract：Scientific workflow is a complex and data-intensive application. It often used in disciplines related to distributed data sources， such as structural biology， highenergy physics and neurology. Data distribute in Internet-based cloud computing platform， resulting in transferring mass of data by scientific workflow running.Because cloud computing is a pay-per-use model，so data transfer costs incurred.Especiallyin the case of multiplecooperative workflows， datatransmissionwill produce higher costs.Firstly， this paper based on multiple workflow data dependence graphestablish transmissioncost model. Secondly， this paperproposed anew particle swarm optimization-based strategy for cost-effective data layout in multiple scientific cloud workflows.The experimental results show that the strategy is much better than its traditional counterparts.

Key words： cloud computing；workflow system；cloud workflow；data layout；binary particle swarm optimization algorithm

1 概述

科學(xué)工作流應(yīng)用是一種復(fù)雜且數(shù)據(jù)密集型的應(yīng)用，常應(yīng)用于結(jié)構(gòu)生物學(xué)、高能物理學(xué)和神經(jīng)學(xué)等涉及分布式數(shù)據(jù)源的學(xué)科，這些學(xué)科通常都要處理海量的數(shù)據(jù)。因此，科學(xué)工作流的數(shù)據(jù)的表示和結(jié)構(gòu)值得深入研究[1]。隨著科學(xué)工作流的發(fā)展，越來越多的科學(xué)工作流研究者認(rèn)識到在云環(huán)境中運(yùn)行科學(xué)工作流比在其他分布式等環(huán)境中有更好的成本效益[2-3]。

云計(jì)算技術(shù)的出現(xiàn)提供了一種新的方式來部署科學(xué)工作流，云計(jì)算是分布式計(jì)算的新范式，以付費(fèi)的方式向用戶提供基礎(chǔ)設(shè)施、平臺和軟件等服務(wù)[4-5]。當(dāng)前已有一些部署在云計(jì)算環(huán)境上科學(xué)工作流項(xiàng)目，例如Nimbus[6]和Cumulus[7]項(xiàng)目。Deelman等人[8]提出云計(jì)算能為科學(xué)工作流提供一個(gè)十分經(jīng)濟(jì)的部署方案[9]。此外，云計(jì)算基于互聯(lián)網(wǎng)Internet，因此全世界的科學(xué)家可以通過云計(jì)算在一起進(jìn)行研究、分享數(shù)據(jù)。當(dāng)科學(xué)工作流在執(zhí)行任務(wù)時(shí)，需要將分布在互聯(lián)網(wǎng)上不在本地的數(shù)據(jù)集傳輸?shù)奖镜夭拍苓M(jìn)行相應(yīng)的計(jì)算，因云計(jì)算環(huán)境以付費(fèi)的方式提供存儲、傳輸、計(jì)算等服務(wù)，所以云計(jì)算環(huán)境下的工作流在執(zhí)行過程中因會產(chǎn)生大量的傳輸費(fèi)用，如何減少傳輸費(fèi)用則成為了一個(gè)在云計(jì)算環(huán)境下部署科學(xué)工作流的挑戰(zhàn)。

本文將提出一種基于二進(jìn)制粒子群算法的多工作流數(shù)據(jù)布局策略，在全面考慮數(shù)據(jù)集大小，數(shù)據(jù)集之間的依賴關(guān)系，網(wǎng)絡(luò)間的傳輸價(jià)格的基礎(chǔ)，通過二進(jìn)制粒子群算法對多工作流的數(shù)據(jù)布局進(jìn)行優(yōu)化，優(yōu)化多工作流的傳輸成本。

2 相關(guān)工作

科學(xué)工作流的數(shù)據(jù)集按照來源可分為輸入數(shù)據(jù)集和生成數(shù)據(jù)集，輸入數(shù)據(jù)集作為工作流任務(wù)的輸入，生成數(shù)據(jù)集作為工作流任務(wù)的輸出，然后該生成數(shù)據(jù)集又作為另一個(gè)工作流任務(wù)的輸入，所以工作流數(shù)據(jù)集之間存在著非常重要的依賴關(guān)系[10]。當(dāng)前已有一些有關(guān)云計(jì)算環(huán)境下的數(shù)據(jù)布局研究，例如Google File System[11]和Hadoop[12]，都對用戶隱藏了存儲數(shù)據(jù)的基礎(chǔ)設(shè)施，數(shù)據(jù)在Google File System或Hadoop系統(tǒng)內(nèi)部的數(shù)據(jù)中心上移動不會產(chǎn)生費(fèi)用，但是云計(jì)算環(huán)境下的科學(xué)工作流主要應(yīng)用與跨學(xué)科的科學(xué)研究，意味著存在多個(gè)分布式的應(yīng)用程序分布在不同的數(shù)據(jù)中心上執(zhí)行，不同學(xué)科的數(shù)據(jù)在云環(huán)境下存放的位置也將不同。科學(xué)工作流在云計(jì)算環(huán)境下執(zhí)行時(shí)，將會產(chǎn)生大量的數(shù)據(jù)移動，也將會產(chǎn)生很多的時(shí)間消耗以及大量的傳輸成本，所以通過合理科學(xué)的數(shù)據(jù)布局則顯得尤為重要。

文獻(xiàn)[13]提出了一種減少數(shù)據(jù)集移動次數(shù)的數(shù)據(jù)布局策略，利用BEA算法對數(shù)據(jù)集之間的依賴矩陣進(jìn)行聚類變換，再根據(jù)聚類變換得到的聚類矩陣進(jìn)行K均值聚類劃分得到數(shù)據(jù)局的布局方案。文獻(xiàn)[14]提出了一種包含3個(gè)階段的降低移動數(shù)據(jù)集傳輸時(shí)間的數(shù)據(jù)布局策略，但是減少移動數(shù)據(jù)集次數(shù)，降低移動數(shù)據(jù)集的傳輸時(shí)間并不代表降低傳輸成本，因?yàn)槊看蝹鬏數(shù)臄?shù)據(jù)集大小的不同，不同的數(shù)據(jù)中心之間的傳輸價(jià)格不同，導(dǎo)致傳輸?shù)某杀静煌?文獻(xiàn)[15]提出了一種基于粒子群算法的啟發(fā)算法來降低工作流執(zhí)行的傳輸費(fèi)用和計(jì)算費(fèi)用的總和，該算法主要分為2個(gè)階段，首先根據(jù)粒子群算法對數(shù)據(jù)集進(jìn)行布局，接著任務(wù)調(diào)度算法根據(jù)粒子群算法提供的數(shù)據(jù)布局對工作流的任務(wù)進(jìn)行調(diào)度，該算法在降低工作流執(zhí)行的傳輸費(fèi)用和計(jì)算費(fèi)用總和的基礎(chǔ)上，在均衡數(shù)據(jù)中心的負(fù)載，加快收斂速度等方面都有很好的效果。當(dāng)多個(gè)工作流相互協(xié)同工作時(shí)，文獻(xiàn)[15]僅從單個(gè)工作流的局部角度考慮降低工作流的傳輸成本和計(jì)算成本并沒有從全局角度考慮。

3 多工作流數(shù)據(jù)布局問題建模

本節(jié)將對云計(jì)算環(huán)境下多科學(xué)工作流應(yīng)用的數(shù)據(jù)布局問題的相關(guān)概念進(jìn)行建模，具體包括云計(jì)算數(shù)據(jù)庫、科學(xué)工作流應(yīng)用、單次數(shù)據(jù)傳輸成本和全局?jǐn)?shù)據(jù)傳輸成本.

定義1：在數(shù)據(jù)中心集合[DC=j=1，2，..，|DC|dcj]已知的云計(jì)算環(huán)境中，[G1]表示一個(gè)科學(xué)工作流，集合[DS=i=1，2，..，ndsi]表示多個(gè)工作流系統(tǒng)[MWS=G1，G2，…，Gn]中的數(shù)據(jù)集合。多個(gè)工作流系統(tǒng)[MWS]的數(shù)據(jù)布局可表示為[Mmulti=i=1，2，…，|DS|di→dcj]。對[?di∈DS]，存在唯一[dcj∈DC]與之對應(yīng)。

定義2：在數(shù)據(jù)布局[Mmulti]中，單個(gè)任務(wù)[Tj]執(zhí)行時(shí)的傳輸成本為：

[CostMmultiTj=mindck∈DCdi∈Tj.IDSCostdi ， Mmultidi，dck] （1）

其中[di]為任務(wù)[Tj]的輸入數(shù)據(jù)集，[Tj.IDS]表示[Tj]的所有輸入數(shù)據(jù)集，[Mmultidi]表示數(shù)據(jù)集[di]在數(shù)據(jù)布局[Mmulti]中的存放位置，[Costdi ， Mmultidi，dck]表示數(shù)據(jù)集[di]從布局位置[Mmultidi]傳輸?shù)綌?shù)據(jù)中心[dck]的費(fèi)用。

定義3：多個(gè)工作流系統(tǒng)[MWS]在數(shù)據(jù)布局[Mmulti]中的全局傳輸費(fèi)用為：

其中[Gi]表示多工作流系統(tǒng)[MWS]中編號為i的工作流，[Vi]表示工作流[Gi]中的所有任務(wù)。

4 基于BPSO的數(shù)據(jù)布局策略

本節(jié)提出了一個(gè)包含2個(gè)算法的數(shù)據(jù)布局策略，文獻(xiàn)[16]所示的BPSO算法被CDP（Cost-effective Data placement）算法調(diào)用。BPSO算法對數(shù)據(jù)集和數(shù)據(jù)中心進(jìn)行編碼，并產(chǎn)生數(shù)據(jù)集和數(shù)據(jù)中心的映射。根據(jù)第3章的公式1和2計(jì)算全局傳輸費(fèi)用。最后返回傳輸費(fèi)用最小的數(shù)據(jù)布局方案。CDP算法根據(jù)返回的結(jié)果找到所有工作流的最優(yōu)數(shù)據(jù)布局方案。

初始化設(shè)置輸入數(shù)據(jù)集都準(zhǔn)備好的任務(wù)隊(duì)列[ExTask]為空（輸入數(shù)據(jù)集都準(zhǔn)備好的任務(wù)指該任務(wù)所需的輸入數(shù)據(jù)集都布局好的任務(wù)），待調(diào)度的任務(wù)集合[SchTask]為空，設(shè)置待布局的數(shù)據(jù)集合[placeDS]為空，步驟3-14，遍歷工作流系統(tǒng)[MWS=G1，G2，…，Gn]中的每一個(gè)工作流[Gi]，從[Gi]中獲取工作流的第一個(gè)任務(wù)節(jié)點(diǎn)[t]，加入隊(duì)列[ExTask]中，當(dāng)[ExTask]不為空進(jìn)入循環(huán)，從隊(duì)列[ExTask]獲取一個(gè)任務(wù)節(jié)點(diǎn)[t']，將[t']加入集合[SchTask]中，并將[t']的后繼任務(wù)都加入隊(duì)列[ExTask]中，獲取[t']的輸入數(shù)據(jù)集合[inputDS]和輸出數(shù)據(jù)集合[outputDS]，將其加入待布局?jǐn)?shù)據(jù)集合[placeDS]中，調(diào)用[BPSO]，對[placeDS]中的數(shù)據(jù)集進(jìn)行布局。

5 實(shí)驗(yàn)評價(jià)

本節(jié)將本文的全局?jǐn)?shù)據(jù)布局策略和傳統(tǒng)的局部數(shù)據(jù)布局策略進(jìn)行對比試驗(yàn)，從2個(gè)方面闡述全局?jǐn)?shù)據(jù)布局策略的優(yōu)越性，我們將隨機(jī)生成多工作流模型進(jìn)行數(shù)據(jù)布局，然后記錄上述2種數(shù)據(jù)布局策略的傳輸費(fèi)用，進(jìn)行對比評價(jià)。下圖均是進(jìn)行100組實(shí)驗(yàn)的平均結(jié)果。

圖1所示是在數(shù)據(jù)集大小在700MB-800MB，數(shù)據(jù)中心個(gè)數(shù)為4，共享數(shù)據(jù)集百分比為30%的情況下隨著數(shù)據(jù)集個(gè)數(shù)的增加，傳統(tǒng)算法和本文算法的傳輸費(fèi)用的變化趨勢?？梢姳疚乃惴ǖ男Ч黠@優(yōu)于傳統(tǒng)算法，隨著數(shù)據(jù)集個(gè)數(shù)的增加差距越來越明顯。

圖2所示為在數(shù)據(jù)中心個(gè)數(shù)為4，和共享數(shù)據(jù)集百分比為25%的情況下的實(shí)驗(yàn)結(jié)果?？梢园l(fā)現(xiàn)，隨著數(shù)據(jù)集大小的增加，傳統(tǒng)算法和本文算法的傳輸成本都呈現(xiàn)上升的趨勢。但本文算法比傳統(tǒng)算法的傳輸成本低，且隨著數(shù)據(jù)集大小的增加越來越低。

6 結(jié)論

云工作流數(shù)據(jù)布局問題關(guān)乎云工作流發(fā)展的核心問題。該文將提出的基于二進(jìn)制粒子群算法的多工作流數(shù)據(jù)布局策略，在全面考慮數(shù)據(jù)集大小，數(shù)據(jù)集之間的依賴關(guān)系，網(wǎng)絡(luò)間的傳輸價(jià)格的基礎(chǔ)，通過二進(jìn)制粒子群算法對多工作流的數(shù)據(jù)布局進(jìn)行優(yōu)化，優(yōu)化多工作流的傳輸成本。

參考文獻(xiàn)：

[1] Gil Y.Examining the challenges of scientific workflows. Ieee computer， 2007，40（12）： 26-34.

[2] Adams I F.Maximizing efficiency by trading storage for computation[C].Proceedings of the 2009 conference on Hot topics in cloud computing，2009.

[3] Yuan D，et al. A cost-effective strategy for intermediate data storage in scientific cloud workflow systems. in Parallel & Distributed Processing （IPDPS）[C].2010 IEEE International Symposium 2010.

[4] Fox A，et al.Above the clouds： A Berkeley view of cloud computing. Dept. Electrical Eng. and Comput. Sciences， University of California， Berkeley， Rep. UCB/EECS， 2009. 28： 13.

[5] Buyya R，Pandey S，Vecchiola C.Cloudbus toolkit for market-oriented cloud computing[J].Cloud Computing. 2009：24-44.

[6] Keahey K，et al. Science clouds： Early experiences in cloud computing for scientific applications[J].Cloud computing and applications， 2008：825-830.

[7] Wang L， et al. Scientific Cloud Computing： Early Definition and Experience[J].HPCC，2008.

[8] Deelman E， et al. The cost of doing science on the cloud： the montage example[C].Proceedings of the 2008 ACM/IEEE conference on Supercomputing. 2008.

[9] Hoffa C，et al. On the use of cloud computing for scientific workflow[C].eScience， 2008. eScience'08. IEEE Fourth International Conference on. 2008.

[10] Simmhan Y L， B. Plale， D. Gannon.A survey of data provenance in e-science[C].ACM Sigmod Record， 2005，34（3）： 31-36.

[11] Ghemawat S，H. Gobioff， S.-T. Leung. The Google file system[J].ACM SIGOPS Operating Systems Review，2003.

[12] White T.Hadoop： The Definitive Guide： The Definitive Guide[J].2009： O'Reilly Media.

[13] Yuan D，et al.A data placement strategy in scientific cloud workflows[J].Future Generation Computer Systems， 2010，26（8）： 1200-1214.

[14] 鄭湃.云計(jì)算環(huán)境下面向數(shù)據(jù)密集型應(yīng)用的數(shù)據(jù)布局策略與方法[J].計(jì)算機(jī)學(xué)報(bào)， 2010，33（8）：1472-1480.

[15] Pandey S，et al.A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments. in Advanced Information Networking and Applications （AINA） [C].2010 24th IEEE International Conference on. 2010.

[16] Kennedy J，R C Eberhart. A discrete binary version of the particle swarm algorithm[C].Systems， Man， and Cybernetics， 1997. Computational Cybernetics and Simulation， 1997 IEEE International Conference on. 1997. IEEE.