云計算環(huán)境下基于關(guān)聯(lián)量的數(shù)據(jù)部署與任務(wù)調(diào)度＊

郭力爭，趙曙光，姜長遠(yuǎn)

（1.東華大學(xué)信息學(xué)院，上海201620；2.河南城建學(xué)院計算機(jī)科學(xué)與工程系，河南 平頂山467036）

1 引言

研究人員依賴于一定的平臺來執(zhí)行科學(xué)工作流，解決數(shù)據(jù)密集型、計算復(fù)雜型等問題，如天文學(xué)、高能物理、地震監(jiān)測［1］和生物信息學(xué)［2］，這樣的科學(xué)工作流通常在本地集群和數(shù)據(jù)網(wǎng)格平臺上執(zhí)行［3］。云計算的出現(xiàn)為科研人員提供了執(zhí)行科學(xué)工作流的又一個優(yōu)秀平臺［4］。在學(xué)術(shù)界，文獻(xiàn)［5，6］探討了在云計算平臺上運(yùn)行科學(xué)工作流的可行性，文獻(xiàn)［7］總結(jié)了云計算平臺運(yùn)行科學(xué)工作流的優(yōu)點(diǎn)?？茖W(xué)工作流的特點(diǎn)是要處理和傳輸?shù)臄?shù)據(jù)量通常巨大，達(dá)TB甚至PB級，另外科學(xué)工作流運(yùn)行過程中也會產(chǎn)生大量的中間數(shù)據(jù)和一些最終的處理結(jié)果，因此，在利用云計算時遇到了一些新的挑戰(zhàn)性問題，如數(shù)據(jù)部署和任務(wù)調(diào)度，主要表現(xiàn)為數(shù)據(jù)中心的不同集群處理能力不同，集群間網(wǎng)絡(luò)性能有所不同，而且數(shù)據(jù)密集型應(yīng)用所處理的數(shù)據(jù)量巨大，所以如何減少數(shù)據(jù)中心不同集群間的數(shù)據(jù)傳輸量、傳輸時間和數(shù)據(jù)傳輸次數(shù)就成為數(shù)據(jù)密集型應(yīng)用的一個難題。一個科學(xué)工作流有一定數(shù)量的任務(wù)，每個任務(wù)要處理特定的文件，每個文件有不同的數(shù)據(jù)量和復(fù)雜性，并且這些文件間有一定的依賴關(guān)系，所以數(shù)據(jù)中心應(yīng)合理分析這種關(guān)系，盡量減少流程執(zhí)行過程中數(shù)據(jù)的移動和傳輸，提高數(shù)據(jù)中心的性能。

一些研究者在網(wǎng)格環(huán)境下致力于數(shù)據(jù)依賴性的研究，并應(yīng)用到大規(guī)模科學(xué)工作流中。Filecules項目［8］基于數(shù)據(jù)的依賴對文件進(jìn)行分組，結(jié)果顯示了其分組策略在科學(xué)網(wǎng)格環(huán)境中對數(shù)據(jù)管理的有效性。BitDew［9］是一個基于桌面網(wǎng)格的分布式數(shù)據(jù)管理系統(tǒng)，不同于云計算中向用戶提供服務(wù)，桌面網(wǎng)格的目的在于使用桌面計算機(jī)閑置的計算和存儲資源。在BitDew中數(shù)據(jù)依賴被定義為數(shù)據(jù)的一個屬性，該屬性由用戶預(yù)先定義。但是，在云計算環(huán)境下，所有的數(shù)據(jù)都存儲在數(shù)據(jù)中心，供所有的用戶使用，讓用戶預(yù)先定義數(shù)據(jù)的依賴關(guān)系是不切實際的。一些研究者研究了云計算環(huán)境下的數(shù)據(jù)部署和任務(wù)調(diào)度問題，Agarwal等人［10］考慮到在分布式環(huán)境下的數(shù)據(jù)部署問題，提出了一個自動的模式來處理存儲限制和數(shù)據(jù)相互依賴問題。Cope等人［11］提出了啟發(fā)式算法來獲得對科學(xué)工作流存儲超限的問題。Pandey等人［12］和 Ramakrishnan等人［13］討論了數(shù)據(jù)敏感的科學(xué)工作流中的調(diào)度問題。但是，在這些研究中，文件在多個站點(diǎn)進(jìn)行復(fù)制，這樣會帶來數(shù)據(jù)的傳輸問題。張春燕等人［14］提出了一種基于蟻群優(yōu)化算法的云計算任務(wù)分配方法，該方法減少了處理請求任務(wù)的平均完成時間，提高了任務(wù)處理的效率；曾志等人［15］提出了海量數(shù)據(jù)集群環(huán)境計算的四叉樹任務(wù)分配策略，該策略能有效地提高整體計算速度。但是，這些方法沒有對數(shù)據(jù)關(guān)聯(lián)進(jìn)行分析，不能減少數(shù)據(jù)的傳輸。

針對上述問題，本文通過分析云計算環(huán)境下面向流程的數(shù)據(jù)密集型應(yīng)用的特點(diǎn)，在全面考慮數(shù)據(jù)傳輸次數(shù)、數(shù)據(jù)傳輸量以及工作流執(zhí)行性能的基礎(chǔ)上，提出云計算環(huán)境下面向數(shù)據(jù)密集型應(yīng)用的基于最大關(guān)聯(lián)量的數(shù)據(jù)部署和任務(wù)調(diào)度策略。該策略一方面對數(shù)據(jù)集間數(shù)據(jù)依賴關(guān)系進(jìn)行建模，并依此模型對數(shù)據(jù)進(jìn)行聚類；然后通過K分割算法對聚類后的數(shù)據(jù)進(jìn)行分割，數(shù)據(jù)中心的任務(wù)分配器根據(jù)分割結(jié)果進(jìn)行部署和調(diào)度。

2 基本概念與問題描述

2.1 基本概念

定義2 數(shù)據(jù)集為工作流的任務(wù)需要處理的文件集：FS ＝ ｛f1，f2，…，fm｝。這些數(shù)據(jù)文件有的是輸入數(shù)據(jù)，有的是輸出數(shù)據(jù)。

定義3 T ＝ ｛t1，t2，t3，…｝表示科學(xué)工作流中任務(wù)的集合，ti＝ 〈runtime，fi〉，runtime表示每個任務(wù)運(yùn)行的時間，fi表示i任務(wù)要處理的文件。

定義4 fi＝ 〈sizei，Ti，dci，linki〉表示科學(xué)工作流中編號為i的文件的數(shù)據(jù)集。其中，sizei表示文件的大小，Ti＝ ｛t1，t2，t3，…｝表示處理文件fi的任務(wù)的集合，dci表示文件被分配到的集群，linki＝｛in，out｝表示文件是輸入還是輸出。

定義5 trf為完成任務(wù)t所需要的文件集：trf＝ ｛f1，f2，…，fn｝。

定義6 tgf為執(zhí)行任務(wù)t所產(chǎn)生的中間文件或輸出文件集：tgf＝ ｛f1，f2，…，fn｝。

定義7 tim是執(zhí)行任務(wù)i所需移動的文件集：

為了更好地分析資源部署和任務(wù)調(diào)度，首先對一些基本概念進(jìn)行定義說明。

定義1 數(shù)據(jù)中心定義為一個集合C

2.2 問題分析與案例

科學(xué)工作流在云環(huán)境下運(yùn)行的步驟如下：

步驟1 云計算服務(wù)商建立數(shù)據(jù)中心，用戶可以按需申請使用。另一方面，數(shù)據(jù)中心也可以是科研院所建立的，免費(fèi)供合作伙伴或個人使用。

步驟2 使用者運(yùn)行科學(xué)工作流時，需要向云平臺申請資源，并對云平臺進(jìn)行定制。比如申請使用的存儲空間、計算能力、使用時間、使用方式等。

步驟3 在科學(xué)工作流運(yùn)行之前，需要分析具體科學(xué)工作流的數(shù)據(jù)特點(diǎn)和任務(wù)特點(diǎn)，進(jìn)行數(shù)據(jù)的邏輯部署。根據(jù)其結(jié)果，數(shù)據(jù)中心的任務(wù)分配器進(jìn)行數(shù)據(jù)的部署和任務(wù)的調(diào)度。

步驟4 在科學(xué)工作流執(zhí)行階段，會產(chǎn)生中間數(shù)據(jù)，這些數(shù)據(jù)會被后續(xù)任務(wù)使用，把數(shù)據(jù)分配到最合適的集群，以減少數(shù)據(jù)的傳輸，提高性能。

下面以圖1為例說明不同的數(shù)據(jù)部署和任務(wù)調(diào)度策略對數(shù)據(jù)移動次數(shù)和數(shù)據(jù)量的影響。

Figure 1 Instance of scientific workflows圖1 科學(xué)工作流實例

圖1 a是一個簡單科學(xué)工作流的例子，其中四個輸入文件f1、f2、f4、f5，兩個輸出文件f3、f6，四個任務(wù)t1，t2，t3，t4對應(yīng)的數(shù)據(jù)集FS ＝ ｛f1，f2，f3，f4，f5，f6｝，任 務(wù) 集 T ＝ ｛t1，t2，t3，t4｝。具體數(shù)據(jù)內(nèi)容為：f1＝ 〈200，t1〉，f2＝ 〈400，t1〉，f3＝〈100，｛t1，t2｝〉，f4＝ 〈500，｛t3，t2｝〉，f5＝ 〈300，｛t4｝〉，f6＝ 〈800，｛t4，t2｝〉。

科學(xué)工作流運(yùn)行中數(shù)據(jù)集和任務(wù)之間并不是一對多或者多對一的關(guān)系，而是多對多的關(guān)系。從圖1a中可以看出，f4同時被任務(wù)t2、t3使用，而任務(wù)t2同時使用f4、f3文件。由于在科學(xué)工作流中數(shù)據(jù)之間有相關(guān)性，所以將關(guān)系緊密的數(shù)據(jù)集盡量放置到同一個集群。在圖1a中，如果把工作流分配到三個集群，按圖1b中的數(shù)據(jù)部署和調(diào)度，由于t2∈C2需要使用f3，而f3?C2，f3∈C1是t1產(chǎn)生的，即f3＝ ｛200，t1，C1，link ＝out｝，所以要把f3傳輸?shù)紺2。同樣的原因，需要把f6傳輸?shù)紺3，f4傳輸?shù)紺2。因此，總共需要移動三次數(shù)據(jù)，移動的數(shù)據(jù)量為：100＋500＋800＝1400。如果按照圖1c的部署，t1、t2要處理f1、f2、f3、f4，而 ｛t1，t2｝∈C1，｛f1，f2，f3｝∈C1，所以不需要移動數(shù)據(jù)，但是f4∈C2，而t2也要處理f4，所以應(yīng)把f4傳輸?shù)紺1；同樣，t4要處理f5、f6，而t4∈C3，f5∈C3，但f6?C3，所以要把f6從C1傳輸?shù)紺3，t3要處理f4，但t3∈C2，f4∈C2，所以不需要移動數(shù)據(jù)，因此，只需移動兩次數(shù)據(jù)，移動的數(shù)據(jù)量為：500＋800＝1300。

3 數(shù)據(jù)依賴性的定義與BEA算法

在科學(xué)工作流中有大量的數(shù)據(jù)，在本文中，不考慮數(shù)據(jù)的格式，把所有數(shù)據(jù)當(dāng)作文件來處理。

3.1 數(shù)據(jù)關(guān)聯(lián)性的定義

通過2.2節(jié)的分析，可以清晰地看到不同的部署方法、任務(wù)調(diào)度策略，對科學(xué)工作流產(chǎn)生的數(shù)據(jù)移動次數(shù)和移動量是不同的。執(zhí)行每個任務(wù)，所需的數(shù)據(jù)必須位于同一個集群，否則就要把數(shù)據(jù)從其他的集群傳輸過來。如果一些數(shù)據(jù)集總是被相同的任務(wù)集使用，有理由相信，把這些數(shù)據(jù)集部署到同一個集群，再把相應(yīng)的任務(wù)調(diào)度到此集群，會減少數(shù)據(jù)的移動量和移動次數(shù)，稱這些數(shù)據(jù)集有依賴性。如果兩個數(shù)據(jù)集同時被同一個任務(wù)使用，則說明這兩個數(shù)據(jù)集有相關(guān)性；如果使用數(shù)據(jù)集的任務(wù)越多，數(shù)據(jù)越大，數(shù)據(jù)集間的關(guān)聯(lián)性也越大。因此，我們定義最大關(guān)聯(lián)量如下：該公式中各變量的含義見2.1節(jié)中的定義3和定義4。

3.2 基于BEA的聚類算法

鍵能算法 BEA（Bond Energy Algorithm）［16］被廣泛應(yīng)用于垂直分割分布式數(shù)據(jù)庫系統(tǒng)中的大表。這是一個排列類型的算法，通過行和列的排列、分割，使矩陣中類似的元素放置在一起。BEA算法把關(guān)聯(lián)矩陣AA（Affinity Matrix）作為輸入，

其中，n是矩陣的行或列數(shù)，aff（Ai，Aj）表示兩列或兩行相對于其他列或行的相近性。

約束條件為：

全局依賴量的約束條件說明，如果矩陣的一列元素被放置在CA最左列的左邊或最右列的右邊，則這兩列的相近度量值為0，因為在這種情況下CA左邊或右邊沒有鄰居，它們在CA中還不存在。行處理同此。

最大化的依賴量只考慮臨近的鄰居，因此導(dǎo)致了大的數(shù)據(jù)聚集在一起，小的數(shù)據(jù)聚集在一起。由于關(guān)聯(lián)矩陣是對稱的，因此，簡化后的關(guān)聯(lián)量定義如下：排列行和列形成一個聚類關(guān)聯(lián)矩陣CA（Clustered Affinity Matrix）。行和列依據(jù)全局依賴量最大化進(jìn)行。全局依賴量的定義如下：

BEA算法的基本思路如下：

初始化：任選一列

迭代

選擇下一列并放置于矩陣中，使得全局的依賴量最大

重復(fù)

行的處理和列相同

由于輸入的依賴矩陣是對稱矩陣，所以列的順序和行相同。

4 基于關(guān)聯(lián)量聚類的數(shù)據(jù)部署與任務(wù)調(diào)度

基于關(guān)聯(lián)量聚類的數(shù)據(jù)部署與任務(wù)調(diào)度分為以下幾個步驟：原始數(shù)據(jù)的分析與關(guān)聯(lián)矩陣的建立；BEA聚類、K分割的具體實現(xiàn)。

4.1 原始數(shù)據(jù)的分析與關(guān)聯(lián)矩陣的建立

由于標(biāo)準(zhǔn)的科學(xué)工作流為XML文件格式，對原始數(shù)據(jù)的分析主要是分析XML文件包含多少個任務(wù)（tasknumber），每個任務(wù)的運(yùn)行時間（runtime）是多少，每個任務(wù)需要處理的文件數(shù)（each＿task＿use＿file），文件名（filename）是什么，文件的大?。╢ilesize），文件的輸入輸出（filelink），每個文件被多少個任務(wù)（each＿file＿used＿task）使用。

原始數(shù)據(jù)提取的大致過程如下所示：

filestr＝fileread（xmlfile）；／／讀取XML文件

tasknumber＝get（filestr）；／／XML文件的任務(wù)數(shù)

for（each jobin filestr）

each＿job＿file＿number＝get（each＿job）；

runtime＝each＿job＿runtime；

filesize＝size；

filelink＝link；

filename＝file；

end

end

for（each file）

each＿file＿used＿task＝find（task use file）；

end

for（each task）

each＿task＿use＿file＝find（file in job）

end

下面詳細(xì)說明關(guān)聯(lián)矩陣的建立：關(guān)聯(lián)矩陣是根據(jù)數(shù)據(jù)間的最大關(guān)聯(lián)量建立的，最大關(guān)聯(lián)量的定量計算通過公式（1）來進(jìn)行。關(guān)聯(lián)矩陣的建立過程如下所示：

1.for（each＿file）

2. file＿use＿task＝0；

3. for（each＿file＿use＿task）

4. if（other＿file＿use＿the＿task）

5. file＿use＿task＋1；

6. end

7. AA＝file＿use＿task；

8.end

9.for（each＿element in AA）

10. if（size（AAi）＞（size（AAi＋1））

11. AAi＝AAi＊size（AAi＋1）；

12. else

13. AAi＝AAi＊size（AAi）；

14. end

15.end

1～8行計算出每個文件被多少任務(wù)使用，即Ti∩Tj，9～15行計算出相互關(guān)聯(lián)的兩個文件中文件數(shù)據(jù)大的那個乘以關(guān)聯(lián)的任務(wù)數(shù)并賦給關(guān)聯(lián)矩陣對應(yīng)的值。

4.2 BEA聚類與K分割的實現(xiàn)

BEA聚類算法首先通過聚類把關(guān)聯(lián)矩陣轉(zhuǎn)換為聚類矩陣，詳細(xì)的算法實現(xiàn)在3.2節(jié)已闡述過。而云計算中的科學(xué)工作流通常有多個集群，聚集后就要考慮如何把這些關(guān)聯(lián)數(shù)據(jù)分割成k個部分，部署到相應(yīng)的集群。把這些關(guān)聯(lián)數(shù)據(jù)部署到集群是個NP－h(huán)ard問題，運(yùn)用二元遞歸分割法來找到一個近似的最優(yōu)解，K分割算法如下所示：

1.／／input：k，分割k個部分

2. CA：聚類矩陣

3. newlocInex：聚類分割后的列索引

4. filesize：每個文件的大小

5. filelink：每個文件的類型，in或out

6.／／output：partSet，k個分割部分

7.［p，CPt，CPb］＝partition＿algorithm（CA）；／／首先把CA分割為兩個矩陣CMt，CMb，并求出分割點(diǎn)p

8.loop：CPt＝CAthe top part index／／分割的上部的列的索引

9.CPb＝CAthe downd part index／／分割的下部的列的索引

10.partSet（1）＝CPt；

11.partSet（2）＝CPb；

12.big＿index＝max（all has been partioned）／／最大部分的索引

13.［p，CMt，CMb］＝partition＿algorithm（partSet（big＿index））；對大的部分繼續(xù)分割

14.go to loop

首先把聚類矩陣CA分割為兩個部分，兩個部分為 ｛f1，f2，…，fk｝和 ｛fk＋1，fk＋1，…，fn｝，分割成兩個部分的標(biāo)準(zhǔn)是使如下的測量值最大化：

該測量值PM使得CA矩陣中關(guān)聯(lián)性高的數(shù)據(jù)被分割到一起，關(guān)聯(lián)性低的數(shù)據(jù)被分割到另一部分?；诖?，分別計算k＝1，2，…，n－1，n，并選擇使PM最大的k作為分割點(diǎn)把CA分割為兩個部 分，分 別 為 CPt＝ ｛f1，f2，…，fk｝和 CPb＝｛fk＋1，fk＋2，…，fn｝。經(jīng)過一次分割一個變?yōu)閮刹糠?，如果要把CA矩陣分割為k個部分，就要進(jìn)行k－1次分割；進(jìn)行k－1分割可以通過遞歸的方法完成，關(guān)鍵的問題是選擇哪一部分進(jìn)行繼續(xù)分割。選擇數(shù)據(jù)量最大的部分進(jìn)行分割，這是為了云計算中數(shù)據(jù)傳輸和移動的方便而考慮的；反之，如果部分?jǐn)?shù)據(jù)量巨大，傳輸和移動都比較耗時間，影響網(wǎng)絡(luò)和數(shù)據(jù)中心的性能。K分割算法大致如下：第7行通過分割算法把聚類矩陣CA分割為CPt和CPb兩個部分；第8行和第9行計算出AA經(jīng)過BEA算法聚類為CA的矩陣的各個文件在CA中的索引；第10行和第11行分別把兩個部分賦給part－Set；第12行計算已分割部分中數(shù)據(jù)量最大的下標(biāo)；第13行繼續(xù)分割直到分割為k個部分。

5 仿真環(huán)境的建立與仿真結(jié)果分析

5.1 仿真環(huán)境的建立

為了測試基于最大關(guān)聯(lián)量的數(shù)據(jù)部署策略的效果，建立了以下仿真環(huán)境。測試硬件為：AMD Phenom? Ⅱ X4B95 3.0GHz，2GB RAM，Microsoft Windows XP environment。仿真結(jié)果是基于MATLAB R2009b實現(xiàn)的。為了更準(zhǔn)確地測試算法的性能，運(yùn)用標(biāo)準(zhǔn)CyberSahke科學(xué)工作流作為測試對象。這些工作流可以從Pegasus web page https：／／confluence.pegasus.isi.edu／display／pegasus／WorkflowGenerator下載。仿真結(jié)果基于關(guān)聯(lián)量的策略簡稱KA，基于相關(guān)性的策略簡稱K，為了比較這兩種數(shù)據(jù)部署策略，還使用了一種隨機(jī)的數(shù)據(jù)部署策略Random。

Random部署：從XML文件提取出工作流的數(shù)據(jù)，通過BEA聚類算法形成聚類矩陣，再通過K分割算法分割為k個部分。

K部署：從XML文件提取出工作流的數(shù)據(jù)，基于相關(guān)性形成關(guān)聯(lián)矩陣，把關(guān)聯(lián)矩陣中的數(shù)據(jù)通過BEA聚類算法形成聚類矩陣，再通過K分割算法分割為k個部分。

KA部署：本項目提出的基于關(guān)聯(lián)量的部署方法。

5.2 仿真結(jié)果及分析

運(yùn)用以上的標(biāo)準(zhǔn)測試工作流，把四個測試工作流中的文件和任務(wù)分別部署和調(diào)度到3、6、9、12、15和18個集群，測試K、KA和Random策略的性能，其結(jié)果如圖2所示。

圖2給出的是當(dāng)數(shù)據(jù)中心集群數(shù)量改變時文件移動量的變化趨勢圖。隨著集群數(shù)量的增多，Random策略的文件移動量都在逐步上升；K策略在測試任務(wù)為30、50、100的情況下，文件首先會上升，當(dāng)集群為12或15時達(dá)到穩(wěn)定，當(dāng)任務(wù)集為1 000時，文件的移動量會逐步上升；KA策略在測試任務(wù)為30、50、100時，文件會先上升，但是比K策略會早一點(diǎn)達(dá)到穩(wěn)定；當(dāng)任務(wù)集為1 000時K策略和KA策略文件移動的量都會逐步上升?？梢悦黠@看出，Random策略最差，KA策略比K策略性能優(yōu)越。

原因分析：隨著集群數(shù)量的增多，平均每個集群分得的數(shù)據(jù)集將減少，任務(wù)執(zhí)行時調(diào)用其它集群數(shù)據(jù)集的可能性增加，導(dǎo)致數(shù)據(jù)傳輸量上升。但是，KA策略要優(yōu)于K策略。

Figure 2 Amount of file movement with different clusters圖2 集群數(shù)量對文件移動量的影響

圖3 給出的是當(dāng)集群數(shù)量改變時文件移動次數(shù)的變化趨勢圖：隨著集群數(shù)量的增多，文件的移動次數(shù)也相應(yīng)地增多，Random策略的文件移動次數(shù)幾乎和集群數(shù)呈線性增長；K策略在測試任務(wù)為30、50、100的情況下，文件首先會上升，當(dāng)數(shù)據(jù)中心為12或15時達(dá)到穩(wěn)定，當(dāng)任務(wù)集為1 000時，文件的移動量會逐步上升；KA策略在測試任務(wù)為30、50、100時，文件會先上升，但是比K策略會早一點(diǎn)達(dá)到穩(wěn)定；當(dāng)任務(wù)集為1 000時K策略和KA策略文件移動次數(shù)都會逐步上升，但KA策略要比K策略增長緩慢。

Figure 3 Times of file movement with different clusters圖3 集群數(shù)量對文件移動次數(shù)的影響

圖4 給出的是集群數(shù)量改變時任務(wù)性能的變化趨勢圖。設(shè)定集群為k時，集群的性能為1～k的一個隨機(jī)數(shù)。由于集群數(shù)不同產(chǎn)生的集群的性能也不一樣，所以在比較性能時從縱向比較，同一個任務(wù)同一個集群的三種不同的數(shù)據(jù)部署和調(diào)度策略進(jìn)行比較。仿真結(jié)果表明：隨著任務(wù)集的增加，任務(wù)的執(zhí)行性能在不同的集群逐步上升，K策略和KA策略明顯優(yōu)于Random策略，KA策略稍微優(yōu)于K策略。

Figure 4 Task performances with different clusters圖4 集群數(shù)量對任務(wù)執(zhí)行性能的影響

6 結(jié)束語

本文對云計算環(huán)境下數(shù)據(jù)密集型應(yīng)用科學(xué)工作流的基本概念進(jìn)行了說明，對數(shù)據(jù)部署和任務(wù)調(diào)度進(jìn)行了分析；通過以上分析提出了最大關(guān)聯(lián)量的數(shù)學(xué)模型，基于最大關(guān)聯(lián)量模型提取對科學(xué)工作流中的數(shù)據(jù)，形成關(guān)聯(lián)矩陣；運(yùn)用BEA算法對關(guān)聯(lián)矩陣進(jìn)行聚類形成聚類矩陣，然后通過K分割算法把聚類矩陣分割為k個部分；通過任務(wù)調(diào)度器把k個部分部署到相應(yīng)的集群，任務(wù)調(diào)度到集群，完成任務(wù)的部署和調(diào)度。仿真結(jié)果表明，KA策略能有效地減少數(shù)據(jù)的移動次數(shù)和移動量，提高任務(wù)的性能，降低程序的復(fù)雜性。目前，本文策略沒有考慮云計算的費(fèi)用和能耗的優(yōu)化問題。由于科學(xué)工作流中要處理的數(shù)據(jù)量非常大，云計算中根據(jù)傳輸數(shù)據(jù)的量來收取數(shù)據(jù)的傳輸費(fèi)；科學(xué)工作流處理的任務(wù)復(fù)雜，在多個不同的集群對任務(wù)進(jìn)行處理，造成能耗非常大，所以，下一步計劃對云計算科學(xué)工作流中的費(fèi)用、能耗問題進(jìn)行研究。

［1］ Southern california earthquake center［EB／OL］.［2012－05－20］.http：／／www.scec.org.

［2］ Livny J，Teonadi H，Livny M，et al.High－throughput，kingdom－wide prediction and annotation of bac－terial non－coding rnas［J］.PLoS ONE，2008，3（9）：e3197.

［3］ Tera－Grid［EB／OL］.［2012－05－20］.http：／／www.teragrid.org／.

［4］ Weiss A.Computing in the clouds［J］.netWorker，2007，11（4）：16－20.

［5］ Deelman E，Singh G，Livny M，et al.The cost of doing science on the cloud：Themontage example［C］∥Proc of 2008 ACM／IEEE Conference on Supercomputing，2008：1－12.

［6］ Mehta G，F(xiàn)reeman T，Deelman E，et al.On the use of cloud computing for scientific workflows［C］.∥Proc of the 4th IEEE International Conference on e－Science，2008：640－645.

［7］ Juve G，Deelman E，Vahi K，et al.Scientific workflow applications on amazon ec2［C］∥Proc of Workshop on Cloudbased Services and Applications in Conjunction with the 5th IEEE e－Science，2010：59－66.

［8］ Doraimani S，Iamnitch A.File grouping for scientific data manag－ement：Lessons from experimenting with real traces［C］∥Proc of the 17th International Symposium on High Performance Distributed Computing，2008：153－164.

［9］ Fedak G，He H，Cappello F.BitDew：A programmable environment for large－scale data management and distribution［C］∥Proc of 2008ACM／IEEE Conference on Supercomputing，2008：1－12.

［10］ Agarwal S，Dunagan J，Jain N，et al.Volley：Automated data placement for geo－distributed cloud services［C］∥Proc of the 7th USENIX Conference on Networked Systems Design and Implementation，2010：2.

［11］ Cope J M，Trebon N，Tufo H M，et al.Robust data placement in urgent computing environments［C］∥Proc of the 2009IEEE International Symposium on Parallel ＆ Distributed Processing，2009：1－13.

［12］ Pandey S，Buyya R.Scheduling data intensive workflow applications based on multi－source parallel data retrieval in distributed computing networks［EB／OL］.［2012－05－15］.http：／／www.cloudbus.org／reports／MultiDataSourceWorkflowCloud2010.pdf.last.

［13］ Ramakrishnan A，Singh G，Zhao H，et al.Scheduling dataintensive workflows onto storage－constrained distributed resources［C］∥Proc of the 7th IEEE International Symposium on Cluster Computing and the Grid，2007：401－409.

［14］ Zhang Chun－yan，Liu Qing－lin，Meng Ke.Task allocation based on ant colony optimization in cloud computing［J］.Journal of Computer Applications，2012，32（5）：1418－1420.（in Chinese）

［15］ Zeng Zhi，Liu Ren－yi，Zhang Feng，et al.A policy of task allocation base on distributed cluster computing towards cloud［J］.Telecommunications Science，2010（10）：30－34.（in Chinese）

［16］ McCormick W T，Sehweitzer P J，White T W.Problem decomposition and data reorganization by a clustering technique［J］.Operations Research，1972，20（5）：993－1009.

附中文參考文獻(xiàn)：

［14］ 張春艷，劉清林，孟珂.基于蟻群優(yōu)化算法的云計算任務(wù)分配［J］.計算機(jī)應(yīng)用，2012，32（5）：1418－1420.

［15］ 曾志，劉仁義，張豐，等.面向云的分布式集群四叉樹任務(wù)分配策略［J］.電信科學(xué)，2010（10）：30－34.