云計算環境中面向DAG任務的多目標調度算法研究

劉軍寧

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

在科學領域內進行實驗時通常將需要完成的任務定義成為工作流的形式，實驗任務以數據流以及計算相關性作為基礎，并形成鏈式狀態的結構。當在應用密集型的計算工作流和數據流的過程中需要對大量的數據和信息展開計算，因此必要保證計算環境性能的優越性，才能夠提高運行的效率。云計算環境的出現能夠確保工作流擁有一個穩定的執行環境，使得工作流能夠獲得強大的技術職稱。云在提供計算資源的過程中主要以虛擬機( virtual machines, VM)的形式，在工作流中實驗任務和云提供的計算資源之間所反應的關系就是工作流在調度過程中的關系和問題。云在進行工作流的調度工作中主要含有2 個層面，第一個層面所指的是實驗任務和虛擬機之間的映射，第二個層面是指在單獨一個虛擬機上的任務執行順序。本文選擇Amazon EC2 為云環境，并在此基礎之上提出了有效的策略來解決對多個目標工作流實施調度過程中存在的問題。

1 Amazon EC2云環境

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

2 模型描述

2.1 DAG任務以及任務模型

圖1：云計算環境的動態調度示意圖

圖2：DAG 圖

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

2.2 資源模型

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

2.3 對問題進行定義

本文所研究的問題簡單來講所指得是把原有的工作流任務通過有效的、科學的調度方式傳輸到Amazon EC2 云環境進行計算和運行，這樣可以在減少用戶支付費用的情況下能夠減少執行時所需要使用的時間。因此之后需要對執行時間makespan 以及經濟代價這兩個優化的具體目標進行定義。

3 展開多目標優化

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

4 設計多目標工作流調度算法

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

5 實驗配置

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

6 實驗結果評估

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

現實工作流包括WIEN2k 工作流以及POV-Ray 工作流，兩個最后的執行結果相差的程度較小，均表現了CMOHEFT 算法的優越性。WIEN2k 工作流中兩種算法之間的對比差距增加，這是由于現實工作流在進行求解的過程中復雜程度會有所增加。POSH 的應用性能仍然低于 CMOHEFT 算法。資源量的增加會導致前者的調度時間縮短，并且代價也會上調[2]。

7 結束語

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