云環(huán)境下優(yōu)化科學(xué)工作流執(zhí)行性能的兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略課件

云環(huán)境下優(yōu)化科學(xué)工作流執(zhí)行性能的

兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略姓名：張燦云環(huán)境下優(yōu)化科學(xué)工作流執(zhí)行性能的

兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策1摘要云環(huán)境中跨數(shù)據(jù)中心科學(xué)工作流的高效執(zhí)行通常面臨數(shù)據(jù)交互量大的問(wèn)題。本文給出基于相關(guān)度的兩階段高效數(shù)據(jù)放置策略和任務(wù)調(diào)度策略。最終通過(guò)實(shí)驗(yàn)表明，該策略能有效減少跨數(shù)據(jù)中心科學(xué)工作流執(zhí)行時(shí)的數(shù)據(jù)傳輸量，從而能有效提升科學(xué)工作流的執(zhí)行效率，并能減少資源的租賃費(fèi)用。摘要云環(huán)境中跨數(shù)據(jù)中心科學(xué)工作流的高效執(zhí)行通常面臨數(shù)據(jù)交互量2主要內(nèi)容一、引言二、相關(guān)工作三、科學(xué)工作流形式化描述和問(wèn)題分析四、基于相關(guān)度的兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略五、實(shí)驗(yàn)分析六、結(jié)論與展望主要內(nèi)容一、引言3一、引言在眾多科學(xué)研究領(lǐng)域中，科學(xué)計(jì)算過(guò)程往往由成千上萬(wàn)個(gè)步驟構(gòu)成，這往往需要對(duì)TB甚至PB量級(jí)的數(shù)據(jù)進(jìn)行分析和處理。在過(guò)去，科學(xué)家通常使用簡(jiǎn)單的方法編排任務(wù)以及管理數(shù)據(jù)，但是這種方式不僅耗時(shí)而且容易出錯(cuò)?？茖W(xué)工作流系統(tǒng)開(kāi)始受到關(guān)注并被用來(lái)進(jìn)行自動(dòng)化科學(xué)任務(wù)的編排、執(zhí)行、監(jiān)控以及追蹤。隨著問(wèn)題求解規(guī)模的增大，當(dāng)今大型科學(xué)工作流通常需要在復(fù)雜的分布式計(jì)算機(jī)系統(tǒng)上執(zhí)行。構(gòu)造這樣的系統(tǒng)往往需要付出異常昂貴的代價(jià)，申請(qǐng)?jiān)L問(wèn)這些系統(tǒng)也需要復(fù)雜耗時(shí)的過(guò)程。云計(jì)算技術(shù)提供共享基礎(chǔ)架構(gòu)的方法，通過(guò)這種方式，云計(jì)算中心可以提供高性能的計(jì)算資源和海量的存儲(chǔ)資源，而且成本低廉，使用簡(jiǎn)單。一、引言在眾多科學(xué)研究領(lǐng)域中，科學(xué)計(jì)算過(guò)程往往由成千上萬(wàn)個(gè)步4科學(xué)工作流任務(wù)間存在較強(qiáng)的數(shù)據(jù)依賴關(guān)系，其執(zhí)行往往需要頻繁對(duì)跨數(shù)據(jù)中心的數(shù)據(jù)集進(jìn)行傳輸和訪問(wèn)，不合理的數(shù)據(jù)放置和任務(wù)調(diào)度策略容易導(dǎo)致數(shù)據(jù)中心間數(shù)據(jù)傳輸量和訪問(wèn)量過(guò)大：增加用戶使用云資源的費(fèi)用，嚴(yán)重影響了科學(xué)工作流的執(zhí)行效率。研究基于云環(huán)境的高效數(shù)據(jù)放置策略和任務(wù)調(diào)度策略對(duì)減少跨數(shù)據(jù)中心數(shù)據(jù)傳輸量、提升科學(xué)工作流執(zhí)行性能、減少用戶費(fèi)用等方面具有重要意義?？茖W(xué)工作流任務(wù)間存在較強(qiáng)的數(shù)據(jù)依賴關(guān)系，其執(zhí)行往往需要頻繁對(duì)5本文通過(guò)分析科學(xué)工作流數(shù)據(jù)集之間的依賴關(guān)系、數(shù)據(jù)集和數(shù)據(jù)中心之間的相關(guān)度以及任務(wù)和數(shù)據(jù)中心之間的相關(guān)度，提出了一種云平臺(tái)下基于相關(guān)度的兩階段高效數(shù)據(jù)放置策略。根據(jù)數(shù)據(jù)依賴關(guān)系圖在工作流建立階段將關(guān)系緊密的數(shù)據(jù)集放置到同一個(gè)數(shù)據(jù)中心，將關(guān)系松散的數(shù)據(jù)集放置在不同數(shù)據(jù)中心。任務(wù)調(diào)度策略在運(yùn)行階段將任務(wù)調(diào)度到數(shù)據(jù)依賴最大的數(shù)據(jù)中心執(zhí)行，并將新產(chǎn)生數(shù)據(jù)集放置到相關(guān)度最高的數(shù)據(jù)中心。實(shí)驗(yàn)表明：本文提出的策略不但極大地減少了數(shù)據(jù)中心間的數(shù)據(jù)移動(dòng)量，提高了工作流任務(wù)的并行執(zhí)行效率，同時(shí)也節(jié)省了用戶的云資源使用費(fèi)用。本文通過(guò)分析科學(xué)工作流數(shù)據(jù)集之間的依賴關(guān)系、數(shù)據(jù)集和數(shù)據(jù)中心6本文的貢獻(xiàn)主要表現(xiàn)在以下幾個(gè)方面：在科學(xué)工作流建立階段，提出了基于數(shù)據(jù)依賴的初始化數(shù)據(jù)布局方法，充分挖掘數(shù)據(jù)相關(guān)性，使得數(shù)據(jù)布局盡可能的符合使用規(guī)則，同一個(gè)任務(wù)所需數(shù)據(jù)集最大規(guī)模地聚集在一個(gè)數(shù)據(jù)中心。在科學(xué)工作流運(yùn)行階段，提出一種相應(yīng)的任務(wù)調(diào)度策略，將任務(wù)調(diào)度到所需數(shù)據(jù)集規(guī)模最大的數(shù)據(jù)中心上，減少數(shù)據(jù)中心之間的數(shù)據(jù)傳輸量，加快科學(xué)工作流執(zhí)行速度。針對(duì)任務(wù)執(zhí)行過(guò)程中產(chǎn)生的中間數(shù)據(jù)集，本文利用數(shù)據(jù)集之間的關(guān)系，通過(guò)量化計(jì)算將它們放置到合適的數(shù)據(jù)中心，使得后續(xù)的任務(wù)調(diào)度與執(zhí)行能夠快速展開(kāi)。本文的貢獻(xiàn)主要表現(xiàn)在以下幾個(gè)方面：7二、相關(guān)工作Pegasus工作流數(shù)據(jù)放置策略：它首先預(yù)先分配數(shù)據(jù)到執(zhí)行任務(wù)的計(jì)算單元，這樣可以加快任務(wù)的執(zhí)行速度，降低任務(wù)等待時(shí)間；然后動(dòng)態(tài)地刪除那些不會(huì)被后續(xù)任務(wù)使用的數(shù)據(jù)，以減少存儲(chǔ)開(kāi)銷。這種策略只是保證了數(shù)據(jù)傳輸?shù)目煽啃院陀行?，并沒(méi)有考慮到云計(jì)算環(huán)境下因?yàn)閿?shù)據(jù)交互引起的跨數(shù)據(jù)中心之間的傳輸開(kāi)銷。副本機(jī)制它使用改進(jìn)后的貪婪算法和經(jīng)過(guò)優(yōu)化的遺傳算法計(jì)算副本的最佳放置策略，并利用基于Web服務(wù)的數(shù)據(jù)網(wǎng)絡(luò)系統(tǒng)ADPPS產(chǎn)生工作流來(lái)進(jìn)行實(shí)驗(yàn)驗(yàn)證。為了減少數(shù)據(jù)傳輸開(kāi)銷，但數(shù)據(jù)集副本機(jī)制增加了存儲(chǔ)開(kāi)銷。該策略主要針對(duì)網(wǎng)絡(luò)環(huán)境下多節(jié)點(diǎn)之間的數(shù)據(jù)傳輸而非針對(duì)云計(jì)算平臺(tái)上多數(shù)據(jù)中心之間的數(shù)據(jù)傳輸，并沒(méi)有考慮到數(shù)據(jù)之間存在相關(guān)性和依賴關(guān)系。二、相關(guān)工作Pegasus工作流副本機(jī)制8BitDew由用戶定義數(shù)據(jù)間的依賴關(guān)系，但并沒(méi)有利用數(shù)據(jù)間的依賴關(guān)系減少傳輸開(kāi)銷。Sector/Sphere是由Gu等人設(shè)計(jì)和實(shí)現(xiàn)一種分布式文件系統(tǒng)該系統(tǒng)中數(shù)據(jù)集是規(guī)模龐大的若干未分塊（non-block）的文件集合。Sphere通過(guò)設(shè)置目錄和文件樹將文件按照數(shù)據(jù)局部性原則聚合起來(lái)，同時(shí)使用高速傳輸協(xié)議UDT和文件副本減少傳輸延遲。實(shí)驗(yàn)結(jié)果表明，該系統(tǒng)比Hadoop處理數(shù)據(jù)要快２～４倍，但Sphere只是根據(jù)任務(wù)來(lái)聚集數(shù)據(jù)，并沒(méi)有對(duì)數(shù)據(jù)之間的關(guān)系進(jìn)行仔細(xì)分析利用。Nephele項(xiàng)目是現(xiàn)有的第一個(gè)數(shù)據(jù)處理框架，注重發(fā)掘在任務(wù)的調(diào)度、執(zhí)行過(guò)程中IaaS云環(huán)境下資源的動(dòng)態(tài)分配，有效地減少了資源使用開(kāi)銷，卻沒(méi)有減少數(shù)據(jù)傳輸開(kāi)銷。BitDew由用戶定義數(shù)據(jù)間的依賴關(guān)系，但并沒(méi)有利用數(shù)據(jù)間的9聚類矩陣的數(shù)據(jù)放置策略：用于多數(shù)據(jù)中心之間數(shù)據(jù)集的放置。該方法的數(shù)據(jù)放置策略分為兩步，在科學(xué)工作流建立階段:構(gòu)建一個(gè)相關(guān)度矩陣。通過(guò)BEA算法得到聚類矩陣。通過(guò)該矩陣將所有數(shù)據(jù)集劃分為K個(gè)集合?？茖W(xué)工作流執(zhí)行階段，在考慮存儲(chǔ)條件滿足的情況下，新產(chǎn)生的數(shù)據(jù)集被放置在與它相關(guān)度最大的數(shù)據(jù)中心上。實(shí)驗(yàn)表明，該方法可以有效減少跨據(jù)中心之間的數(shù)據(jù)移動(dòng)次數(shù)。但這種方法并未考慮移動(dòng)的數(shù)據(jù)大小，如果移動(dòng)次數(shù)較少，但所移動(dòng)的數(shù)據(jù)太大，傳輸開(kāi)銷不一定降低，導(dǎo)致科學(xué)工作流的執(zhí)行效率反而下降。聚類矩陣的數(shù)據(jù)放置策略：用于多數(shù)據(jù)中心之間數(shù)據(jù)集的放置。10三、科學(xué)工作流形式化描述和問(wèn)題分析

3.1相關(guān)模型和符號(hào)定義定義1數(shù)據(jù)中心設(shè)為DC＝dci＝〈capi,csi,λini〉表示編號(hào)為i數(shù)據(jù)中心，capi表示dci的計(jì)算能力，并用執(zhí)行同一任務(wù)所需的時(shí)間的倒數(shù)來(lái)量化表示，并假設(shè)該值保持不變；csi表示dci的存儲(chǔ)空間大小；λini表示在科學(xué)工作流建立階段，數(shù)據(jù)中心可以使用的存儲(chǔ)空間的比例。因?yàn)榭茖W(xué)工作流執(zhí)行過(guò)程中產(chǎn)生的中間數(shù)據(jù)有可能規(guī)模龐大，因此在原始數(shù)據(jù)分配階段要留有一定的空間來(lái)存儲(chǔ)中間數(shù)據(jù)，所以0＜λini＜1。λini是一個(gè)經(jīng)驗(yàn)值，它的大小取決于科學(xué)工作流的性質(zhì)。三、科學(xué)工作流形式化描述和問(wèn)題分析3.1相關(guān)模型和符號(hào)定11定義2原始數(shù)據(jù)集設(shè)為DSini＝｛d1，d2，d3…｝DSini表示在科學(xué)工作流建立時(shí)所存在的數(shù)據(jù)集，即所有原始輸入。中間數(shù)據(jù)集設(shè)為DSgen＝｛d1，d2，d3…｝DSgen表示在科學(xué)工作流執(zhí)行過(guò)程中所產(chǎn)生的數(shù)據(jù)集。固定數(shù)據(jù)集和非固定數(shù)據(jù)集分別設(shè)為FD和NFD．FD表示必須放置在固定數(shù)據(jù)中心的數(shù)據(jù)集，這是因?yàn)槟承?shù)據(jù)需要特定數(shù)據(jù)中心的特定設(shè)備才能處理，或者某些數(shù)據(jù)具有私有性和產(chǎn)權(quán)性．NFD表示沒(méi)有固定數(shù)據(jù)中心的數(shù)據(jù)集，這是相對(duì)FD而言。定義3T＝｛t1，t2，t3…｝表示在科學(xué)工作流上運(yùn)行的任務(wù)集，每一個(gè)任務(wù)執(zhí)行都需要若干數(shù)據(jù)集作為輸入。定義4di＝〈Ti，si，dci，fix＿flag，deplink〉di表示科學(xué)工作流中編號(hào)為i的數(shù)據(jù)集。Ti＝｛t1，t2，t3…｝表示使用di的任務(wù)集合；si表示數(shù)據(jù)集的大?。籨ci表示di所對(duì)應(yīng)的數(shù)據(jù)中心；fix＿flag為true表示di是固定數(shù)據(jù)，反之則為非固定數(shù)據(jù)；deplink是一個(gè)鏈表。定義2原始數(shù)據(jù)集設(shè)為DSini＝｛d1，d2，d3…｝123.2實(shí)例分析與問(wèn)題說(shuō)明圖１（a）給出了一個(gè)科學(xué)工作流的例子，該科學(xué)工作流包含5個(gè)子任務(wù)｛t1，t2，t3，t4，t5｝，5個(gè)輸入數(shù)據(jù)集｛d1，d2，d3，d4_f，d5｝和一個(gè)中間數(shù)據(jù)集｛d6｝，其中｛d4_f｝是dc2上的固定數(shù)據(jù)集，不能移動(dòng)。3.2實(shí)例分析與問(wèn)題說(shuō)明圖１（a）給出了一個(gè)科學(xué)工作流的例13以圖１為例，科學(xué)工作流的數(shù)據(jù)放置策略需要考慮以下幾點(diǎn)：（1）數(shù)據(jù)相關(guān)對(duì)科學(xué)工作流的影響?？茖W(xué)工作流運(yùn)行中數(shù)據(jù)集和任務(wù)之間并不是一對(duì)多或者多對(duì)一的關(guān)系，而是多對(duì)多的關(guān)系，即一個(gè)數(shù)據(jù)集可能會(huì)被多個(gè)任務(wù)同時(shí)使用，一個(gè)任務(wù)也可能調(diào)用多個(gè)數(shù)據(jù)集。（2）數(shù)據(jù)集大小對(duì)科學(xué)工作流的影響。（3）固定數(shù)據(jù)集對(duì)科學(xué)工作流的影響。固定數(shù)據(jù)集對(duì)科學(xué)工作流的影響。因?yàn)楣潭〝?shù)據(jù)集只能放置在特定的數(shù)據(jù)中心，無(wú)法向外傳輸，一旦任務(wù)使用到固定數(shù)據(jù)集，該任務(wù)一定會(huì)被調(diào)度到這個(gè)數(shù)據(jù)中心上執(zhí)行。（4）數(shù)據(jù)中心的計(jì)算能力、存儲(chǔ)能力對(duì)科學(xué)工作流的影響．由于各個(gè)數(shù)據(jù)中心隸屬于不同的組織機(jī)構(gòu)，其計(jì)算能力、存儲(chǔ)能力可能差異較大。合理的數(shù)據(jù)放置策略也要也要將這兩個(gè)因素考慮到，即在存儲(chǔ)空間足夠的前提下，向計(jì)算能力強(qiáng)的數(shù)據(jù)中心放置盡量多的數(shù)據(jù)集，以加快科學(xué)工作流的執(zhí)行速度。由于數(shù)據(jù)移動(dòng)開(kāi)銷對(duì)科學(xué)工作流性能影響較大，因此合理的數(shù)據(jù)放置策略應(yīng)該努力減少數(shù)據(jù)移動(dòng)量，本文針對(duì)這種情況提出了一種基于相關(guān)度的數(shù)據(jù)放置策略，該策略綜合考慮了數(shù)據(jù)相關(guān)度（即數(shù)據(jù)之間被相同任務(wù)使用的多少）、數(shù)據(jù)大小、固定數(shù)據(jù)集、數(shù)據(jù)中心的計(jì)算能力和存儲(chǔ)能力，有效提升了科學(xué)工作流的執(zhí)行效率。以圖１為例，科學(xué)工作流的數(shù)據(jù)放置策略需要考慮以下幾點(diǎn)：14四、基于相關(guān)度的兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略4.1建立階段數(shù)據(jù)放置策略在科學(xué)工作流建立階段，該策略對(duì)所有的原始輸入數(shù)據(jù)集在邏輯上進(jìn)行預(yù)分配，這樣做可以優(yōu)化數(shù)據(jù)分配方案，防止前期出現(xiàn)不合理分配的情況。預(yù)分配主要從局部性考慮，使得子任務(wù)在調(diào)度后，所需使用的數(shù)據(jù)集都盡量在本地?cái)?shù)據(jù)中心上存儲(chǔ)。定義5數(shù)據(jù)集相關(guān)度設(shè)為count（Ti∩Tj）×min｛si，sj｝，di，dj∈NFDdepij＝count（Ti∩Tj）×si，di∈NFD，dj∈FDcount（Ti∩Tj）×si，di∈FD,dj∈NFD0，di，dj∈FD四、基于相關(guān)度的兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略4.1建立階段15depij表示數(shù)據(jù)di和數(shù)據(jù)dj的相關(guān)度大小。count（Ti∩Tj）表示共同使用di和dj的任務(wù)數(shù)量。depij與數(shù)據(jù)集大小有關(guān)。由定義４知，數(shù)據(jù)集di有一個(gè)屬性deplink，此處定義為deplink（i）=｛<di,depij>|j≠i｝，根據(jù)depij大小形成一個(gè)降序鏈表。定義6預(yù)分配數(shù)據(jù)中心設(shè)為DCk，k＝1，2，…，m，假定DCk的存儲(chǔ)空間值為相應(yīng)的dck存儲(chǔ)空間大小。在科學(xué)工作流建立階段，需要先將原始數(shù)據(jù)集邏輯上分配到DCk，k＝1，2，…，m，然后按照DCk→dck的映射原則，將邏輯上的分配方案在物理的數(shù)據(jù)中心上實(shí)現(xiàn)。定義7待分配數(shù)據(jù)集集合設(shè)為DCwait。在科學(xué)工作流建立階段，該集合中存放的是與其它任何數(shù)據(jù)集相關(guān)度均為0的數(shù)據(jù)集；在科學(xué)工作流運(yùn)行階段，該集合中存放在后續(xù)過(guò)程中需要分配的數(shù)據(jù)集。depij表示數(shù)據(jù)di和數(shù)據(jù)dj的相關(guān)度大小。16如圖２所示，在科學(xué)工作流建立階段需要對(duì)所有的原始數(shù)據(jù)進(jìn)行預(yù)分配，其流程大致如下:第1步（語(yǔ)句1～5）算法首先將所有的原始數(shù)據(jù)分為兩類，固定數(shù)據(jù)集FD和非固定數(shù)據(jù)集NFD。第2步（語(yǔ)句6～22）判斷di的deplink中相關(guān)度最大的數(shù)據(jù)集di是固定數(shù)據(jù)集還是非固定數(shù)據(jù)集。第3步（語(yǔ)句23～27）對(duì)DCwait中的數(shù)據(jù)集進(jìn)行預(yù)分配。如圖２所示，在科學(xué)工作流建立階段需要對(duì)所有的原始數(shù)據(jù)進(jìn)行預(yù)分174.2運(yùn)行階段數(shù)據(jù)放置與任務(wù)調(diào)度策略在科學(xué)工作流執(zhí)行階段，基于相關(guān)度的數(shù)據(jù)放置策略將中間數(shù)據(jù)集放置到與它相關(guān)度最大的數(shù)據(jù)中心上，如果該中心存儲(chǔ)空間不足，則按照該策略中的Adjustment算法對(duì)全局?jǐn)?shù)據(jù)集進(jìn)行調(diào)整。定義8數(shù)據(jù)集dk和數(shù)據(jù)中心dcm的相關(guān)度dc_depmk＝Ti表示數(shù)據(jù)中心dcm上數(shù)據(jù)集di所需使用的任務(wù)集，N表示dcm上數(shù)據(jù)集的個(gè)數(shù)，Tk指使用數(shù)據(jù)集dk的任務(wù)集集合，sk表示數(shù)據(jù)集dk大小。4.2運(yùn)行階段數(shù)據(jù)放置與任務(wù)調(diào)度策略18定義9調(diào)度任務(wù)tk在數(shù)據(jù)中心dcm上執(zhí)行引起的傳輸開(kāi)銷設(shè)為transCostmk＝［size(DSk)－size(DSk∩DSm)＋size(DS’gen-DS’m)］size(DS)表示集合DS中所有數(shù)據(jù)集大小之和，DSk是任務(wù)tk所需使用的數(shù)據(jù)集，DSm包含數(shù)據(jù)中心dcm上的所有數(shù)據(jù)集，DS’gen表示任務(wù)tk執(zhí)行完畢后產(chǎn)生的數(shù)據(jù)集，DS’m表示DS’gen中應(yīng)該放在dcm上的數(shù)據(jù)集。［size(DSk)－size(DSk∩DSm)］表示tk在dcm上執(zhí)行需要從其它數(shù)據(jù)中心調(diào)入的數(shù)據(jù)集大小，size(DS’gen-DS’m))表示tk在dcm上執(zhí)行完畢后產(chǎn)生的中間數(shù)據(jù)集向其它數(shù)據(jù)中心發(fā)送的數(shù)據(jù)集大小。如果transCosthk＝，將tk調(diào)度到dch上執(zhí)行所引起的傳輸開(kāi)銷是最低的。定義9調(diào)度任務(wù)tk在數(shù)據(jù)中心dcm上執(zhí)行引起的傳輸開(kāi)銷設(shè)為19科學(xué)工作流運(yùn)行的時(shí)候，從任務(wù)集合中選取任務(wù)ti，根據(jù)定義９將ti調(diào)度到合適的數(shù)據(jù)中心執(zhí)行，執(zhí)行完畢后若產(chǎn)生新的任務(wù)和新的數(shù)據(jù)集，則首先更新任務(wù)集合，然后給新產(chǎn)生的數(shù)據(jù)集選擇合適的數(shù)據(jù)中心放置。對(duì)新產(chǎn)生的中間數(shù)據(jù)dk，根據(jù)定義８計(jì)算其與所有數(shù)據(jù)中心的相關(guān)度dc_depmk，選擇相關(guān)度最大的數(shù)據(jù)中心分配，如果該數(shù)據(jù)中心存儲(chǔ)空間不足，表明科學(xué)工作流已經(jīng)運(yùn)行了一段時(shí)間，出現(xiàn)了負(fù)載不均衡，因此需要對(duì)所有數(shù)據(jù)集進(jìn)行重新調(diào)整?？茖W(xué)工作流運(yùn)行的時(shí)候，從任務(wù)集合中選取任務(wù)ti，根據(jù)定義９20調(diào)整算法如圖4所示，詳細(xì)過(guò)程如下：第1步（語(yǔ)句1～31）對(duì)所有數(shù)據(jù)中心上的數(shù)據(jù)集進(jìn)行預(yù)分配。第2步（語(yǔ)句32～38）預(yù)分配完成以后，對(duì)所有邏輯數(shù)據(jù)中心DCi和物理數(shù)據(jù)中心dci上的每個(gè)數(shù)據(jù)集dk進(jìn)行對(duì)比。調(diào)整算法如圖4所示，詳細(xì)過(guò)程如下：21五、實(shí)驗(yàn)分析5.1實(shí)驗(yàn)環(huán)境和設(shè)置為了驗(yàn)證基于相關(guān)度的數(shù)據(jù)放置策略效果，在“天河”集群上建立了一個(gè)包含80個(gè)節(jié)點(diǎn)的測(cè)試平臺(tái)，每一個(gè)節(jié)點(diǎn)包含一個(gè)IntelXeonE55402.53GHz的四核cpu。為了模擬云計(jì)算平臺(tái)，在每個(gè)節(jié)點(diǎn)上安裝Ｘｅｎ并在上面創(chuàng)建了虛擬集群以模擬數(shù)據(jù)中心；為每一個(gè)cpu核創(chuàng)建一個(gè)帶有存儲(chǔ)空間的計(jì)算實(shí)體，每個(gè)數(shù)據(jù)中心包含１６個(gè)計(jì)算實(shí)體，于是共有２０個(gè)數(shù)據(jù)中心；為了對(duì)數(shù)據(jù)進(jìn)行管理，在每個(gè)數(shù)據(jù)中心上安裝了ApacheHDFS，并運(yùn)行swinDew-C（SwinburneDecentralisedWorkflowforCloud)用來(lái)解釋和執(zhí)行工作流。本文將采用模擬的、可定制的科學(xué)工作流來(lái)測(cè)試基于相關(guān)度的數(shù)據(jù)放置策略。通過(guò)分別改變科學(xué)工作流的數(shù)據(jù)集和任務(wù)的數(shù)量來(lái)控制科學(xué)工作流的復(fù)雜度；通過(guò)改變上界與下界來(lái)控制數(shù)據(jù)集大小的取值范圍；同樣，固定數(shù)據(jù)集的比例和數(shù)據(jù)中心的數(shù)量也可以進(jìn)行調(diào)整。實(shí)驗(yàn)過(guò)程中，為了保證結(jié)果的可靠性，每一個(gè)科學(xué)工作流在保持配置和云平臺(tái)環(huán)境不變的情況下，運(yùn)行300次后取平均值作為測(cè)試結(jié)果。五、實(shí)驗(yàn)分析5.1實(shí)驗(yàn)環(huán)境和設(shè)置22為了說(shuō)明本文所提數(shù)據(jù)放置策略的效果，實(shí)驗(yàn)對(duì)比了３種數(shù)據(jù)放置策略，分別是Random、Cluster和本文所提出的基于相關(guān)度的數(shù)據(jù)放置策略。Random策略：輸入數(shù)據(jù)集在建立階段隨機(jī)的放到其中一個(gè)數(shù)據(jù)中心，如果是固定數(shù)據(jù)集則放置到指定的數(shù)據(jù)中心；運(yùn)行階段，如果空間足夠，產(chǎn)生的中間數(shù)據(jù)集則存放在本地?cái)?shù)據(jù)中心，否則隨機(jī)放置到其中一個(gè)數(shù)據(jù)中心。在網(wǎng)格、集群系統(tǒng)中，產(chǎn)生的中間數(shù)據(jù)集就是存放在本地或者隨機(jī)放在存儲(chǔ)空間富余的結(jié)點(diǎn)上。Cluster策略：在文獻(xiàn)［11］中提到的數(shù)據(jù)放置策略。在建立階段，把所有的輸入數(shù)據(jù)分為犓個(gè)數(shù)據(jù)集合，把這犓個(gè)數(shù)據(jù)集合放置到合適的數(shù)據(jù)中心；在運(yùn)行階段，把新產(chǎn)生的數(shù)據(jù)集放置到合適的數(shù)據(jù)中心?；谙嚓P(guān)度的數(shù)據(jù)放置策略：本文所提的數(shù)據(jù)放置策略，在文章后續(xù)部分所有圖示中用Data-dependence表示該策略。為了說(shuō)明本文所提數(shù)據(jù)放置策略的效果，實(shí)驗(yàn)對(duì)比了３種數(shù)據(jù)放置策235.2測(cè)試結(jié)果及分析5.2.1數(shù)據(jù)集數(shù)量變化對(duì)結(jié)果的影響

圖5顯示的是當(dāng)數(shù)據(jù)集數(shù)量增加時(shí)，數(shù)據(jù)移動(dòng)次數(shù)和數(shù)據(jù)移動(dòng)量的變化趨勢(shì)。實(shí)驗(yàn)設(shè)定如下：科學(xué)工作流任務(wù)量犖和數(shù)據(jù)集數(shù)量犖取相同的值，數(shù)據(jù)集的變化范圍設(shè)為1～500MB，固定數(shù)據(jù)集比例為20％，數(shù)據(jù)中心為15個(gè)。5.2測(cè)試結(jié)果及分析圖5顯示的是當(dāng)數(shù)據(jù)集數(shù)量增加時(shí)，數(shù)據(jù)24原因分析：Cluster策略按照最大數(shù)量的原則將數(shù)據(jù)集聚集在同一個(gè)數(shù)據(jù)中心，而基于相關(guān)度的數(shù)據(jù)放置策略按照最大流量的原則將數(shù)據(jù)集聚集在同一個(gè)數(shù)據(jù)中心；同時(shí)，在運(yùn)行階段Cluster策略將任務(wù)調(diào)度到包含數(shù)據(jù)個(gè)數(shù)最多的數(shù)據(jù)中心，基于相關(guān)度的數(shù)據(jù)放置策略則將任務(wù)調(diào)度到數(shù)據(jù)量最多的數(shù)據(jù)中心，所以任務(wù)執(zhí)行時(shí)，基于相關(guān)度的數(shù)據(jù)放置策略引起的數(shù)據(jù)傳輸量就會(huì)明顯減少。原因分析：Cluster策略按照最大數(shù)量的原則將數(shù)據(jù)集聚集255.2.2數(shù)據(jù)集大小取值范圍變化對(duì)數(shù)據(jù)移動(dòng)量的影響圖6表示數(shù)據(jù)集大小幅度改變時(shí)數(shù)據(jù)移動(dòng)量的變化趨勢(shì)。實(shí)驗(yàn)設(shè)定如下：科學(xué)工作流任務(wù)量為80，數(shù)據(jù)集數(shù)量為80，固定數(shù)據(jù)集比例為20％，數(shù)據(jù)中心為15個(gè)，數(shù)據(jù)集大小的平均值是250MB。原因分析：若數(shù)據(jù)大小變化幅度很大，則Data-dependence策略在大多數(shù)情況下會(huì)選擇移動(dòng)規(guī)模小的數(shù)據(jù)集，這樣就降低了數(shù)據(jù)移動(dòng)量。5.2.2數(shù)據(jù)集大小取值范圍變化對(duì)數(shù)據(jù)移動(dòng)量的影響圖6表示265.2.3固定數(shù)據(jù)集比例的改變對(duì)數(shù)據(jù)移動(dòng)量的影響圖7表出的是固定數(shù)據(jù)集比例改變時(shí)數(shù)據(jù)的移動(dòng)量的變化趨勢(shì)。實(shí)驗(yàn)設(shè)定如下：科學(xué)工作流任務(wù)量為80，數(shù)據(jù)集個(gè)數(shù)為80，數(shù)據(jù)中心為