云計(jì)算環(huán)境中面向DAG任務(wù)的多目標(biāo)調(diào)度算法研究

劉軍寧

（江蘇省委黨校圖書館 江蘇省南京市 210009）

在科學(xué)領(lǐng)域內(nèi)進(jìn)行實(shí)驗(yàn)時(shí)通常將需要完成的任務(wù)定義成為工作流的形式，實(shí)驗(yàn)任務(wù)以數(shù)據(jù)流以及計(jì)算相關(guān)性作為基礎(chǔ)，并形成鏈?zhǔn)綘顟B(tài)的結(jié)構(gòu)。當(dāng)在應(yīng)用密集型的計(jì)算工作流和數(shù)據(jù)流的過程中需要對大量的數(shù)據(jù)和信息展開計(jì)算，因此必要保證計(jì)算環(huán)境性能的優(yōu)越性，才能夠提高運(yùn)行的效率。云計(jì)算環(huán)境的出現(xiàn)能夠確保工作流擁有一個穩(wěn)定的執(zhí)行環(huán)境，使得工作流能夠獲得強(qiáng)大的技術(shù)職稱。云在提供計(jì)算資源的過程中主要以虛擬機(jī)( virtual machines, VM)的形式，在工作流中實(shí)驗(yàn)任務(wù)和云提供的計(jì)算資源之間所反應(yīng)的關(guān)系就是工作流在調(diào)度過程中的關(guān)系和問題。云在進(jìn)行工作流的調(diào)度工作中主要含有2 個層面，第一個層面所指的是實(shí)驗(yàn)任務(wù)和虛擬機(jī)之間的映射，第二個層面是指在單獨(dú)一個虛擬機(jī)上的任務(wù)執(zhí)行順序。本文選擇Amazon EC2 為云環(huán)境，并在此基礎(chǔ)之上提出了有效的策略來解決對多個目標(biāo)工作流實(shí)施調(diào)度過程中存在的問題。

1 Amazon EC2云環(huán)境

Amazon EC2 云環(huán)境的全稱為Amazon 彈性計(jì)算云EC2，實(shí)際上屬于IaaS ( infrastructure as a service，基礎(chǔ)設(shè)施即服務(wù))云服務(wù)，能夠針對用戶開放Amazon 的相關(guān)計(jì)算設(shè)施。為了能夠保證云計(jì)算對各種資源實(shí)現(xiàn)有效的利用，并且能夠在所給定的相關(guān)約束性條件之下仍然及時(shí)完成計(jì)算任務(wù)，就必須要對調(diào)度進(jìn)行優(yōu)化。調(diào)度會影響到云計(jì)算的實(shí)際運(yùn)行效率，也就是說調(diào)度的優(yōu)化效果決定了云計(jì)算的效率。調(diào)度的目標(biāo)在于最大限度的提高計(jì)算資源利用效率、減少在處理任務(wù)過程中所需要使用的時(shí)間，在保證計(jì)算質(zhì)量的基礎(chǔ)上也能夠具有較高的工作效率。如圖1 所示，即為云計(jì)算環(huán)境的動態(tài)調(diào)度示意圖。Amazon EC2 云環(huán)境可以一共展示3 種不同類型的實(shí)例，第一種實(shí)例屬于預(yù)留型，即可以允許一個用戶對多個不同主機(jī)中的資源進(jìn)行較長時(shí)間的預(yù)定；第二種實(shí)例屬于按需型，所指的是用戶可以按照自己請求的資源類型和時(shí)間按照每小時(shí)對資源付費(fèi)；第三種實(shí)例屬于Spot 實(shí)例，如果用戶擁有沒有使用的Amazon 的資源，可以對該資源展開投標(biāo)，并且用戶還能夠?qū)δ骋毁Y源進(jìn)行指定性的出價(jià)格。Spot 價(jià)格是根據(jù)資源的實(shí)際需求量進(jìn)行制定的，如果所出的價(jià)格要比這一價(jià)格高，那么用戶就能夠獲得實(shí)例，如果所處的價(jià)格小于這一價(jià)格，那么由Amazon EC2 云環(huán)境將Spot 實(shí)例，進(jìn)行回收。

2 模型描述

2.1 DAG任務(wù)以及任務(wù)模型

圖1：云計(jì)算環(huán)境的動態(tài)調(diào)度示意圖

圖2：DAG 圖

DAG（directed a cycling graph，有向無環(huán)圖）是一個沒有環(huán)、有方向的圖，可以對某一個工作流程的開展過程進(jìn)行仔細(xì)的描述，是應(yīng)用范圍較為廣泛的工具之一[1]。如圖2 所示，即為DAG 圖。DAG 模型能夠?qū)⒉⑿谐绦蜻M(jìn)行精準(zhǔn)的刻畫。雖然無法利用DAG 圖將某一個實(shí)際程序的循環(huán)最為直觀的表示出來，但是能夠把處于循環(huán)之中不同數(shù)據(jù)流的并行計(jì)算進(jìn)行分解，將其分解成為其他的任務(wù)，這種任務(wù)的容量會變得更小。之后會對小任務(wù)進(jìn)行模型刻畫，則能夠通過DAG 圖進(jìn)行展示。在一般情況下，通常會選擇DAG圖來描述需要進(jìn)行處理的各個任務(wù)，在描述完畢之后能夠更加直觀的觀察到不同任務(wù)之間存在的順序關(guān)系以及先后關(guān)系，同時(shí)還可以展現(xiàn)出在各個任務(wù)之間具體的、所傳遞的信息量。DAG 圖可以讓我們更加快速的尋找到一條最為關(guān)鍵的路徑或者多條具有關(guān)鍵性的路徑，在對這些關(guān)鍵性的路徑實(shí)施判斷和評估的時(shí)候能夠得到最快的運(yùn)行速度，即所需要的最短的運(yùn)行時(shí)間。本次研究過程中即使用DAG 圖對工作流進(jìn)行定義，被定義為W=（A，D），A 所代表的n 多個任務(wù)的總集，即任務(wù)集，D 所代表的是不同任務(wù)之間的控制流以及數(shù)據(jù)流之間存在的關(guān)系。

2.2 資源模型

此時(shí)對云平臺的構(gòu)成進(jìn)行假設(shè)，設(shè)定其是通過m 個為異構(gòu)類型的資源集共同組合而形成的，將其設(shè)定為R，之后Amazon EC2云環(huán)境進(jìn)行云資源的提供，例如包括m1．large、m1．xlarge、c1．medium 及c1．xlarge 等。對于給定的資源進(jìn)行分析和類型確定，在確定類型之后選擇CFLOP 對其展開測量，分析在每一秒內(nèi)可以執(zhí)行的浮點(diǎn)運(yùn)算情況。在本次研究過程中，設(shè)定工作流任務(wù)在Amazon EC2 云環(huán)境中能夠做到并行執(zhí)行，并按照這種形式持續(xù)運(yùn)行，每一個小時(shí)進(jìn)行進(jìn)行一次收費(fèi)。最后可以發(fā)現(xiàn)用戶所需要付出的費(fèi)用會受到多種因素的影響，不單單只是資源如何使用，例如數(shù)據(jù)存儲和虛擬機(jī)各個實(shí)例之間數(shù)據(jù)的傳輸情況也會影響到用戶最后所需要支付的費(fèi)用。DAG 圖如圖2 所示。

2.3 對問題進(jìn)行定義

本文所研究的問題簡單來講所指得是把原有的工作流任務(wù)通過有效的、科學(xué)的調(diào)度方式傳輸?shù)紸mazon EC2 云環(huán)境進(jìn)行計(jì)算和運(yùn)行，這樣可以在減少用戶支付費(fèi)用的情況下能夠減少執(zhí)行時(shí)所需要使用的時(shí)間。因此之后需要對執(zhí)行時(shí)間makespan 以及經(jīng)濟(jì)代價(jià)這兩個優(yōu)化的具體目標(biāo)進(jìn)行定義。

3 展開多目標(biāo)優(yōu)化

多目標(biāo)優(yōu)化其實(shí)上是在數(shù)學(xué)規(guī)劃過程中所存在的重要分支，對在一個以上的目標(biāo)函數(shù)進(jìn)行研究，并在函數(shù)的給定區(qū)域之上對其進(jìn)行最優(yōu)化。簡單來講，可以將多目標(biāo)優(yōu)化認(rèn)為是尋找到能夠讓矢量函數(shù)變成最小化形態(tài)的所有解，用函數(shù)可以表示為f(x) =[f1(x), f2(x) , …, fo(x)]，其中o 所代表的是具體的目標(biāo)函數(shù)數(shù)量。本次研究中的目標(biāo)函數(shù)數(shù)量為2，第一個目標(biāo)函數(shù)為執(zhí)行時(shí)間makespan，第二個目標(biāo)函數(shù)為經(jīng)濟(jì)代價(jià)。上文所提到的在解決工作流調(diào)度這一問題時(shí)所得出的最優(yōu)解中每一個都另外含有兩個不同的矢量。其一包括多個不確定數(shù)量的元素矢量，其數(shù)量確定需要取決于工作流的實(shí)際騰武數(shù)量。其二為大小程度為n 的排列情況，隨代表的是不同任務(wù)在執(zhí)行過程中所需要嚴(yán)格遵循的順序。其實(shí)，要求同時(shí)尋找到一個可以讓執(zhí)行時(shí)間makespan 最短，同時(shí)也讓所需要付出經(jīng)濟(jì)代價(jià)最少的解是很難的，或者說在工作流調(diào)度的問題中是無法完成的。為了能夠真正的解決這一問題，本次研究應(yīng)用了Pareto 最優(yōu)這一概念，來對兩個目標(biāo)函數(shù)的最優(yōu)解進(jìn)行評估和判斷。設(shè)定兩個解分別為y 和z，如果前者在兩項(xiàng)目標(biāo)函數(shù)上都要比后者小，那么可以將其稱之為解 y 占優(yōu)解z。如果前者的執(zhí)行時(shí)間makespan 最短，后者需要付出經(jīng)濟(jì)代價(jià)最少，兩個解分別占據(jù)一個優(yōu)勢，那么前者和后者均被稱之為非占優(yōu)解。

4 設(shè)計(jì)多目標(biāo)工作流調(diào)度算法

本次研究過程中選擇兩種算法進(jìn)行優(yōu)化，分別為HEFT 算法以及MOHEFT 算法，通過對兩種算法優(yōu)化之后可以在Amazon EC2 云環(huán)境中展開應(yīng)用，這種方式打破了以往傳統(tǒng)情況下的異構(gòu)計(jì)算環(huán)境特點(diǎn)。在之前的系統(tǒng)中可以明確的了解到資源的實(shí)際數(shù)量以及資源的類型分布情況，然而在Amazon EC2 云環(huán)境中卻只能擁有有限資源總量。但是Amazon EC2 云環(huán)境的優(yōu)勢在于可以按照用戶的需向用戶動態(tài)化的提供資源，云計(jì)算的計(jì)算能力以及云環(huán)境中的資源可用性都是處于動態(tài)的變化過程的。為了能夠保證本次研究中優(yōu)化后的算法可以在Amazon EC2 云環(huán)境中進(jìn)行合理的使用，選擇將資源的實(shí)際輸入量設(shè)定為m=N×I。其中I 所代表的是云資源提供角色所供給的實(shí)例數(shù)量以及實(shí)例的各種類型，經(jīng)過這種設(shè)定之后，能夠保證當(dāng)資源處于總量最大的時(shí)候，任何組合都具有一定的可能性。共選擇兩種算法，第一種屬于CHEFT 算法，第二種屬于CMOHEFT 算法。

5 實(shí)驗(yàn)配置

本次研究所選擇的仿真平臺為WorkFlowSim。首先，先給定出能夠?qū)λ惴ǖ膶?shí)際性能進(jìn)行評估的重要指標(biāo)，之后分析了工作流的實(shí)際類型以及云環(huán)境中的具體配置。另外，除了上述提到的兩種算法，同時(shí)還利用了應(yīng)用極其廣泛的POSH 算法，將該種算法作為性能對比的對照組。POSH 算法也屬于常用的一種針對多個目標(biāo)函數(shù)求出最優(yōu)解的算法，并且在進(jìn)行算法運(yùn)行的過程中也考慮到了如何求除均衡解的這一個問題。

6 實(shí)驗(yàn)結(jié)果評估

合成三種工作流的類型分別為Type-1 工作流、Type-2 工作流以及Type-3 工作流。Type-1 工作流是對比CMOHEFT 算法與 POSH 算法，其中前者解的質(zhì)量性能要明顯優(yōu)于POSH 算法，、Type-2 工作流中得出的結(jié)果Type-1 工作流相同，且最優(yōu)性要明顯于第一組。Type-3 工作流是對上兩個工作流結(jié)果的印證，也更加明確了CMOHEFT 算法的最優(yōu)解，能夠在于Amazon EC2 云環(huán)境中針對多個目標(biāo)函數(shù)完成最優(yōu)的調(diào)度。

現(xiàn)實(shí)工作流包括WIEN2k 工作流以及POV-Ray 工作流，兩個最后的執(zhí)行結(jié)果相差的程度較小，均表現(xiàn)了CMOHEFT 算法的優(yōu)越性。WIEN2k 工作流中兩種算法之間的對比差距增加，這是由于現(xiàn)實(shí)工作流在進(jìn)行求解的過程中復(fù)雜程度會有所增加。POSH 的應(yīng)用性能仍然低于 CMOHEFT 算法。資源量的增加會導(dǎo)致前者的調(diào)度時(shí)間縮短，并且代價(jià)也會上調(diào)[2]。

7 結(jié)束語

綜上所述，本文基于Amazon EC2 云環(huán)境中提出了面向DAG任務(wù)的多目標(biāo)調(diào)動算法，該種算法的名稱為CMOHEFT 算法。此次算法設(shè)計(jì)的目標(biāo)在于可以保障工作流任務(wù)的執(zhí)行跨度能夠和工作流任務(wù)的執(zhí)行所產(chǎn)生的經(jīng)濟(jì)代價(jià)處于同步的狀態(tài)，并利用了啟發(fā)式的手段使得多個目標(biāo)之間形成了均衡的狀態(tài)，成為了最優(yōu)解的結(jié)合。同時(shí)利用了Pareto 邊界的手段以及hypervo- lume 值的手段共同對均衡解展開了分析，判斷是否均衡解具有一定的有效性。利用人工的方式一共合成了三種工作流，以及兩種現(xiàn)實(shí)工作流的相關(guān)測試。最后對整體過程和最終結(jié)果進(jìn)行分析，可以明顯發(fā)現(xiàn)為CMOHEFT算法的應(yīng)用效果最好，優(yōu)于CHEFT 算法和POSH 算法，在多數(shù)的工作流任務(wù)中都可以減少執(zhí)行跨度以及執(zhí)行所產(chǎn)生的經(jīng)濟(jì)代價(jià)，可以進(jìn)行應(yīng)用。