一種臨時私有云中邏輯拓撲感知的作業調度算法

趙玉艷,陳海寶,2,趙生慧

(1.滁州學院計算機與信息工程學院,安徽滁州239000;2.華中科技大學計算機科學與技術學院,武漢430074)

一種臨時私有云中邏輯拓撲感知的作業調度算法

趙玉艷1,陳海寶1,2,趙生慧1

(1.滁州學院計算機與信息工程學院,安徽滁州239000;2.華中科技大學計算機科學與技術學院,武漢430074)

考慮到成本和靈活性等因素,利用公共云計算系統的資源構建臨時私有云代替本地物理集群,已成為用戶在特定時間段內處理大量并行作業的一種有效途徑。然而現有作業調度算法不能感知并利用臨時私有云的邏輯拓撲結構,容易降低緊耦合并行應用的性能。為解決該問題,提出一種邏輯拓撲感知的作業調度算法,根據私有云中虛擬機之間的帶寬和延遲等信息構建邏輯拓撲關系,并綜合考慮用戶所提交作業的類型,進而產生對應的作業調度決策。實驗結果表明,該算法在提高臨時私有云中緊耦合并行應用性能方面優于開源云計算系統中常用的輪轉算法和隨機算法。

臨時私有云;并行應用;虛擬機;拓撲結構;調度算法;網絡性能

1 概述

隨著虛擬化和云計算的快速普及和發展,在公共云計算系統中構建臨時私有云(也稱為虛擬集群)來替代本地物理集群,已成為用戶在特定時間段內處理大量并行作業(如基于消息傳遞接口(Message Passing Interface,MPI[1])的并行應用程序)的有效途徑。在創建臨時私有云后,用戶如同操作本地物理集群一般操作臨時私有云,使用作業調度系統管理作業調度。臨時私有云給用戶帶來的好處具體有:(1)不需要用戶對基礎設施進行前期投資和運維;(2)提供可定制的應用運行環境;(3)按使用付費。

在一般情況下,運行環境中的網絡拓撲對緊耦合并行應用(也就是進程之間需要頻繁通信和同步的并行應用)的性能有著重要影響[2-3]。傳統的物理集群環境中,在網絡基礎設施建設完成后,計算節點之間的拓撲結構是固定的。然而,在臨時私有云環境中,虛擬機之間的網絡性能以及邏輯拓撲結構卻是多變且未知的[4],這主要歸因于云計算基礎設施供應商(例如Amazon EC2,阿里云等)在為用戶提供臨時私有云時,根據供應商自身的調度策略來放置和遷移虛擬機,并且對用戶屏蔽了上述信息。在這種情況下,已有的作業調度算法因不能夠感知并利用臨時私有云的邏輯拓撲結構,容易造成緊耦合并行應用(也就是進程之間需要頻繁的通信和同步的并行應用)的性能降低。針對該問題,本文提出一種邏輯拓撲感知的作業調度算法以提高臨時私有云中緊耦合并行應用的性能。

2 相關研究

在云計算環境中,當并行應用的進程與虛擬機之間存在一對一的映射關系時,并行應用的調度問題可以等價于虛擬機的調度問題。具體地,云計算系統中的虛擬機調度工作大致分為3類:(1)初始的虛擬機放置,研究的是如何把用戶所請求的一個或多個虛擬機映射到可用的資源池中。(2)離線的虛擬機合并,研究的是如何把具有不同資源需求的虛擬機映射到物理資源中,它通過最小化活躍的物理服務器數量來節約能源。(3)在線遷移,研究的是如何制定在線虛擬機的重新映射決策。本文研究第(1)類問題。

對于虛擬機的初始放置問題,已有的云管理系統例如OpenStack[5]和OpenNebula[6]使用了輪轉算法、隨機算法、首次適應算法和最佳適應算法等策略。此外,研究者也提出了諸多解決方法。例如,文獻[7]提出使用遺傳算法來解決虛擬機的放置問題。文獻[8]提出一種基于離散粒子群優化的調度算法。文獻[9]提出一種融合遺傳算法與蟻群算法的混合調度算法。文獻[10]提出一種具備反饋機制的動態調度算法。然而,上述方法都忽略了多個虛擬機因運行同一個并行應用而產生的緊耦合性,并且未考慮臨時私有云環境中虛擬機之間網絡性能的不穩定性。

Amazon EC2推出了集群計算實例[11],并利用放置組策略來讓同一個組內的所有實例(虛擬機)具有低延遲和高帶寬。然而,由于Amazon EC2的非開源特性,研究者并不清楚Amazon EC2的放置組策略到底有多嚴格以及使用何種技術來提供上述保證。

由以上分析可以看出,目前在臨時私有云中仍缺乏一種能夠感知并利用虛擬機之間邏輯拓撲結構的作業調度算法。為了解決這個問題,本文提出了一種邏輯拓撲感知的作業調度算法。

3 邏輯拓撲構建與調度算法

下文介紹了臨時私有云的邏輯拓撲構建算法,并以此為基礎,給出了邏輯拓撲感知的作業調度算法。

3.1 臨時私有云的邏輯拓撲

如前所述,受云計算基礎設施供應商自身調度策略和資源供應策略的影響,臨時私有云中虛擬機之間的網絡性能并不穩定[4],為了能夠在調度并行應用時充分利用虛擬機之間的網絡性能信息,需要獲取臨時私有云在當前時間的一個邏輯拓撲結構。

在傳統物理集群的樹狀網絡拓撲中,計算節點之間的路徑越長,它們之間的網絡性能一般會越差。以圖1中的物理集群為例,共有128個計算節點組成了一個樹狀網絡拓撲結構。其中,編號為1～8的8個計算節點通過接入點A0互相通信,并通過A0與其余120個計算節點(編號為9～128)進行通信。在這個場景中,計算節點1和節點8之間的網絡性能通常會優于計算節點1和節點128之間的網絡性能。其主要原因分析如下:(1)計算節點1與節點8之間只需要通過A0進行通信,而計算節點1和節點128之間則需要經過A0-D0-C0-D3-A15等方可進行通信,因此,從通信延遲的角度來看,前者要優于后者;(2)隨著樹狀層次的增加,共享高層線路的計算節點數量也在增加,這必然降低了共享同一條線路的節點所實際分到的可用帶寬。因此,從可用帶寬的角度來看,前者要優于后者。

圖1 集群樹狀網絡拓撲

受到傳統物理集群樹狀結構中節點之間網絡性能的差異性所啟發,本文利用虛擬機之間的網絡性能,將臨時私有云的拓撲構建為樹狀層次結構。實際上,構建樹狀層次結構就是對所有虛擬機進行劃分的過程。然而,計算一個最優的分層結構是一個NP-hard問題(類似于裝箱問題)[12]。由于指數級的復雜性,通常計算最優解決方法是不可行的,尤其是在虛擬機的數量很龐大時,因此本文采用貪心方法來構建層次結構。其基本思想是:設定一個網絡性能閾值,然后根據虛擬機之間的網絡性能,將所有虛擬機劃分到彼此無交集的分組中。在同一個網絡性能閾值下劃分出的所有分組構成樹狀層次結構中的一個層次。增大網絡性能閾值,重復之前的操作,從而形成一個新的層次。以此類推,直到滿足樹狀結構的層數限制。

對于一個由N臺虛擬機組成的臨時私有云,本文首先定義了3個矩陣來記錄虛擬機之間的網絡信息,分別是延遲矩陣、帶寬矩陣和網絡性能矩陣。其中,延遲矩陣和帶寬矩陣中的數據可以通過在每臺虛擬機中安裝測試代理的方式來獲取。在構建臨時私有云邏輯拓撲之前,需要利用延遲矩陣和帶寬矩陣對虛擬機兩兩之間的網絡性能進行建模,具體描述如下:

(1)延遲矩陣:Latency[0,1,…,N-1][0, 1,…,N-1],其中,Latency[i][j]表示虛擬機i到虛擬機j的平均延遲,其初始值為0。

(2)帶寬矩陣:Bandwidth[0,1,…,N-1][0, 1,…,N-1],其中,Bandwidth[i][j]表示虛擬機i到虛擬機j的平均帶寬,其初始值為∞。

(3)網絡性能矩陣:Performance[0,1,…,N-1] [0,1,…,N-1],其中,Performance[i][j]=Latency[i][j]+1/Bandwidth[i][j]。在計算出網絡性能矩陣后,需要對其進行離散化處理。

貪心算法用到的符號和函數具體如下:group表示分組,由網絡性能滿足條件的虛擬機組成,如group={vm1,vm2,vm3};setcounter表示在第counter次迭代中產生的全部分組所組成的集合;|setcounter|表示集合中的分組數量;set0表示集合set的初始值,每個分組只包含一個虛擬機,即set0={{vm1},{vm2},…, {vmn}};partition(set)表示劃分函數,對集合set的分組進行劃分,返回值為新的一個集合set’,集合中分組數量小于集合set中的分組數量;distance(v,group)表示距離函數,返回虛擬機v與分組group之間的網絡性能值;logicHierarchy表示臨時私有云的邏輯層次。邏輯拓撲構建算法的具體步驟如下:

算法1邏輯拓撲構建算法

輸入網絡性能矩陣Performance[0,1,…,N-1] [0,1,…,N-1]

輸出臨時私有云的邏輯拓撲

在算法1中,根據設定的虛擬機之間的距離閾值(如partition()函數中的第5行所示)將所有虛擬機劃分為一些不重疊的分組(group),每個分組之間具有類似的網絡性能(即每個分組內任一對虛擬機之間的距離不大于設定的閾值)。隨著逐漸放松距離閾值(如partition()函數中的第8行所示),小的分組(子分組)會隨之組成大的分組(父分組)。而分組之間的父子關系形成了一個樹形層次結構(如算法1中的第6行所示)。

為了清楚地展示算法具體流程,此處以5個虛擬機(vm1～vm5)為例來進行說明,如圖2所示。

圖2 邏輯拓撲構建算法

在初始化階段,集合set0中共有5個分組,其中,每個分組中包含1個虛擬機,即{vm1},{vm2}, {vm3},{vm4}和{vm5}。

在第1次調用partition()函數對集合set0進行劃分時,將set0中的5個分組重新劃分為2個分組,即{vm1,vm2,vm3}和{vm4,vm5},并保存在集合set1中。

在第2次調用partition()函數對集合set1進行劃分時,將set1中的2個分組劃分為一個分組,并保存在集合set2中。

經過上述2次劃分后,得到樹形層次的邏輯拓撲結構logicHierarchy={set0,set1,set2}。

3.2 邏輯拓撲感知的作業調度算法

在獲得了臨時私有云的邏輯拓撲結構信息后,本文設計一個基于邏輯拓撲感知的作業調度算法(如算法2所示)。針對不同類型的并行應用(緊耦合并行應用和松耦合并行應用)分別做出不同的調度決策。由構建邏輯拓撲結構的算法1可知,在樹狀層次結構里,同一層中各分組內的虛擬機網絡性能相似。

算法2 邏輯拓撲感知的作業調度算法

輸入作業的資源需求,臨時私有云邏輯拓撲結構logicTopology

輸出作業放置策略

算法2的基本思想是:當用戶提交緊耦合并行應用時,算法首先在每層中把分組按照所含空閑虛擬機的數量進行升序排列(算法2中的第1行),然后從網絡性能最好的層次(算法2中的第4行～第7行)開始,從排列好的分組中選擇大小合適的分組(即分組中空閑虛擬機的數量略大于或等于緊耦合并行應用所需要的虛擬機數量),找到這樣的分組后,將所需數量的虛擬機分配給上述緊耦合并行應用(算法2中的第8行～第10行)。若在性能最好的層次中沒有找到可以放置緊耦合并行應用的分組,則在性能次好的層次中尋找。依此類推,直到找到合適的分組為止,或者因系統中沒有足夠數量的空閑虛擬機而返回空集(算法2中的第15行)。

當用戶提交松耦合并行應用時,因松耦合并行應用對虛擬機之間的網絡性能要求不高,所以算法只需在網絡性能最好的層次,從按升序排列的分組中依此收集每個分組中的空閑虛擬機(算法2中的第18行～第21行),直到收集的空閑虛擬機數量滿足松耦合并行應用的需求為止(算法2中的第22行～第24行),或者因系統中沒有足夠數量的空閑虛擬機而返回空集(算法2中的第27行)。

4 實驗結果與分析

為評估本文提出的邏輯拓撲感知算法,在不同數量的緊耦合并行應用實驗和不同的網絡性能標準差實驗下,對其進行性能測試,并對實驗結果進行分析。

4.1 實驗設置

實驗設置具體如下:

(1)模擬環境

本文使用CloudSim[13]模擬了一個云計算環境。本文選擇CloudSim作為云模擬器主要考慮到以下2個原因:1)CloudSim能夠有效模擬云計算環境,并受到了國內外研究者的廣泛認可;2)文獻[14]通過擴展CloudSim的功能已使其具備了對緊耦合并行應用進行模擬的能力。

(2)算法比較對象

如在第1節的相關研究中所述,為了解決虛擬機的初始放置問題,研究者們已提出了諸多方法(如基于粒子群的方法、基于遺傳算法的方法等)。然而,它們主要關注的是如何解決裝箱問題(即如何在一臺物理機中裝入更多的虛擬機)來提高云計算系統的資源利用率。上述方法在制定放置決策時,都忽略了多個虛擬機因運行同一個并行應用而產生的緊耦合關系,并且未考慮和利用在臨時私有云環境中虛擬機之間的邏輯拓撲關系。而本文算法關注于通過合理放置虛擬機來提升虛擬機中并行應用的性能,并且充分考慮和利用臨時私有云中虛擬機之間的邏輯拓撲關系。

由此可以看出,本文算法與上述幾種方法在關注點以及評價指標方面有所不同,所以,不適合與它們進行比較。基于以上考慮,本文選取了開源云計算系統(OpenStack和OpenNebula)采用的2種通用方法(輪轉算法和隨機算法)作為對比對象。

(3)系統并行應用

在實驗中模擬了100個并行應用,為了簡單明了地對算法進行評估,不失一般性,本文實驗假設每個應用包含4個并行進程。其中,每個進程運行在一個單核虛擬機中。

4.2 緊耦合并行應用實驗

實驗1不同數量的緊耦合并行應用實驗。模擬了400臺虛擬機,并根據文獻[4]對Amazon EC2網絡性能的測試數據模擬生成了400臺虛擬機之間的網絡性能矩陣,取值范圍在400～650之間,相對標準差為13.7%。

本文實驗中的100個并行應用包括了X個緊耦合并行應用(如NPB benchmark[15]中的BT,SP,IS, CG,LU和MG)以及Y個松耦合并行應用(如NPB benchmark中的EP),其中,X+Y=100,X的初始值為10,并以10為單位遞增,最大值為90。例如在X=10,Y=90時進行一輪實驗(運行5次求平均值),獲取10個緊耦合并行應用在不同算法(邏輯拓撲感知算法、輪轉算法、隨機算法)下的平均執行時間,并根據理想狀態下10個緊耦合并行應用的平均運行時間進行規格化處理。其中,理想狀態是指網絡性能矩陣中數據的標準偏差為0且能完全滿足緊耦合并行應用對網絡性能的需求。

在X=20,30,…,90時,分別進行一輪上述實驗,規格化實驗數據如圖3所示。

圖3 不同數量緊耦合并行應用下的性能比較

具體分析如下:

(1)邏輯拓撲感知算法的性能明顯優于輪轉算法和隨機算法。原因在于:相對于輪轉算法和隨機算法,邏輯拓撲感知算法能夠利用臨時私有云中虛擬機之間的網絡拓撲關系,選擇網絡性能好的多個虛擬機來運行緊耦合并行應用,從而達到提高緊耦合并行應用性能的目的,而輪轉算法和隨機算法并不考慮虛擬機之間的邏輯拓撲關系。

(2)在臨時私有云環境中,輪轉算法與隨機算法的性能相近,并且比較穩定。具體地,在上述2種算法下,緊耦合并行應用的平均執行時間在規格化后介于1.45～1.50之間。原因在于:臨時私有云中每個虛擬機的位置是受到云計算基礎設施供應商調度算法和負載均衡算法的控制,并且這種控制對臨時私有云的所有者來說是不透明的。因此,在臨時私有云中輪轉和隨機算法的性能是相當地。在這種情況下,輪轉算法退化為隨機算法。

(3)隨著緊耦合并行應用數量的增加,邏輯拓撲感知算法的性能逐漸變差,但是仍優于輪轉算法和隨機算法。原因在于:本文實驗中網絡性能矩陣中的數值介于400～650之間,相對標準差為13.7%,也就是說,所有虛擬機之間的網絡性能數據并非全部相同(有的網絡性能好,有的網絡性能差)。因此,隨著緊耦合并行應用數量的增加,網絡性能差的虛擬機會被用來執行緊耦合并行應用,從而導致緊耦合并行應用的平均執行時間也變長。但是由于邏輯拓撲感知算法能夠有效利用虛擬機之間的邏輯拓撲,其性能仍優于輪轉和隨機算法。

4.3 網絡性能實驗

實驗2不同的網絡性能實驗。虛擬機數量與實驗1中的數量相同。因為實驗1中已經比較了算法在系統中有不同數量緊耦合并行應用時的性能,得出了相應結論。因此,實驗2固定了緊耦合并行應用的數量(即X=10),通過改變虛擬機之間網絡性能矩陣的取值范圍來評估算法在不同相對標準差情況下的性能表現。虛擬機之間網絡性能矩陣的取值范圍以及相對標準差如表1所示。

表1 虛擬機間網絡性能矩陣的取值范圍及相對標準差

實驗結果如圖4所示,具體分析如下:

(1)在系統中有10個緊耦合并行應用的情況下(即X=10),邏輯拓撲感知算法在不同的網絡性能標準差下與理想狀態的性能相近。這說明在不同的網絡性能相對標準差下,模擬系統中至少有40個虛擬機(10×4)的網絡性能與理想狀態下的網絡性能相當。邏輯拓撲感知算法能夠有效利用這些網絡性最好的虛擬機來運行上述10個緊耦合并行應用。

(2)輪轉算法與隨機算法性能相近,并且性能隨著相對標準差的降低而變好,尤其是在相對標準差為2.4%時,輪轉算法與隨機算法的性能接近于邏輯拓撲感知算法以及理想狀態下的性能。原因在于:隨著相對標準差的降低,虛擬機網絡性能越來越接近于理想狀態。此時,不同算法對緊耦合并行應用的性能影響不斷減弱。因此,邏輯拓撲感知算法、輪轉算法和隨機算法的性能都開始接近于理想狀態下的性能。

圖4 各虛擬機間網絡性能的相對標準差比較

在真實的云計算系統中虛擬機之間的網絡性能一般會隨著時間而呈現出波動現象,因此,在算法應用于實際臨時私有云時,需要每隔一定的時間(需要根據不同的云計算系統設定不同值)重新構建臨時私有云的邏輯拓撲結構。不失一般性,實驗1和實驗2評估了一次邏輯拓撲構建完成后的算法性能。從實驗結果可以看出,邏輯拓撲感知調度算法更適合于臨時私有云環境。

5 結束語

本文研究在創建臨時私有云后,如何利用邏輯拓撲信息來優化緊耦合并行應用性能的問題。為獲取邏輯拓撲信息,提出一個邏輯拓撲構建算法,并基于此設計一種邏輯拓撲感知的作業調度算法。實驗結果表明,邏輯拓撲感知的調度算法比輪轉算法和隨機算法性能更好。在真實環境中構建原型系統以進一步測試和優化邏輯拓撲感知的調度算法是后續研究的重點。

[1] ANL Mathematics and Computer Science Division.The MessagePassingInterfaceStandard[EB/OL]. [2014-07-19].http://www.mcs.anl.gov/research/ projects/mpi/.

[2] Expósito R R,TaboadaGL,RamosS,etal. Performance AnalysisofHPCApplicationsinthe Cloud[J].Future Generation Computer Systems,2013, 29(1):218-229.

[3] Gupta A,Kalé L V,Milojicic D,et al.HPC-aware VM Placement in Infrastructure Clouds[C]//Proceedings of 2013 International Conference on Cloud Engineering. [S.l.]:IEEE Press,2013:11-20.

[4] Wang Guohui,Ng T S E.The Impact of Virtualization onNetworkPerformanceofAmazonEC2Data Center[C]//Proceedings of INFOCOM’10.[S.l.]: IEEE Press,2010:1-9.

[5] OpenStack.Open Source Software for Building Private and Public Clouds[EB/OL].[2014-07-19].https:// www.openstack.org/.

[6] OpenNebula.Cloud and Data Center Virtual Infrastructure Management[EB/OL].[2014-07-19].https://www. opennebula.org/.

[7] Xu J,Fortes J.A Multi-objective Approach to Virtual Machine Management in Datacenters[C]//Proceedings of the 8th ACM International Conference on Autonomic Computing.[S.l.]:ACM Press,2011:225-234.

[8] 鄔開俊,魯懷偉.云環境下基于DPSO的任務調度算法[J].計算機工程,2014,40(1):59-62.

[9] 張 雨,李 芳,周 濤.云計算環境下基于遺傳蟻群算法的任務調度研究[J].計算機工程與應用,2014, 50(6):51-55.

[10] 馬 莉,唐善成,王 靜,等.云計算環境下的動態反饋作業調度算法[J].西安交通大學學報,2014, 48(7):77-82.

[11] 亞馬遜公司.AWS產品與解決方案[EB/OL].(2014-03-01).http://aws.amazon.com/cn/ec2/.

[12] Gong Yifan,He Bingsheng,Zhong Jianlang.Network PerformanceAwareMPICollectiveCommunication Operations in the Cloud[J].IEEE Transactions on Parallel Distributed Systems,2013,96(1):1-9.

[13] Calheiros R N,RanjanR,BeloglazovA,etal. CloudSim:A Toolkit for Modeling and Simulation of CloudComputingEnvironmentsandEvaluationof Resource Provisioning Algorithms[J].Software:Practice and Experience,2011,41(1):23-50.

[14] Garg S K,Buyya R.An Environment for Modeling and Simulation of Message——Passing Parallel Applications for CloudComputing[J].Software:Practiceand Experience,2013,43(11):1359-1375.

[15] NASA.NPB Benchmark[EB/OL].[2014-07-19]. http://www.nas.nasa.gov/publications/npb.html/.

編輯 陸燕菲

A Logic-topology-aware Job Scheduling Algorithm in Temporary Private Cloud

ZHAO Yuyan1,CHEN Haibao1,2,ZHAO Shenghui1
(1.School of Computer and Information Engineering,Chuzhou University,Chuzhou 239000,China;
2.School of Computer Science&Technology,Huazhong University of Science and Technology,Wuhan 430074,China)

Considering the cost and flexibility,building a temporary private cloud in public cloud to replace the local physical cluster is an effective way for users to run a large number of parallel jobs during a particular period.However,the existing scheduling algorithms are not suitable for temporary private cloud hosting tightly coupled parallel applications, because they can not use the logic topology information of temporary private cloud,which probably results in the performance degradation of such type of applications.To mitigate such impact,a logic-topology-aware scheduling algorithm is presented.It builds the logic topology of virtual machines according to bandwidth and latency among them, makes scheduling decisions based on the logic topology and the information of applications.Experimental results show that compared with Round Robin and Random algorithms of open-source cloud software,logic-topology-aware scheduling algorithm improves the performance of tightly coupled parallel applications.

temporary private cloud;parallel application;virtual machine;topology structure;scheduling algorithm; network performance

趙玉艷,陳海寶,趙生慧.一種臨時私有云中邏輯拓撲感知的作業調度算法[J].計算機工程, 2015,41(2):1-6.

英文引用格式:Zhao Yuyan,Chen Haibao,Zhao Shenghui.A Logic-topology-aware Job Scheduling Algorithm in Temporary Private Cloud[J].Computer Engineering,2015,41(2):1-6.

1000-3428(2015)02-0001-06

:A

:TP393.09

10.3969/j.issn.1000-3428.2015.02.001

安徽省自然科學基金資助面上項目(1408085MF126);安徽省教育廳自然科學研究基金資助重大項目(KJ2011ZD06);滁州學院優秀青年人才基金資助重點項目(2013RC006);滁州學院科研啟動基金資助項目(2014qd016)。

趙玉艷(1982-),女,講師、碩士,主研方向:數據挖掘,云計算;陳海寶,講師、博士研究生;趙生慧,教授、博士。

2014-08-20

:2014-10-03E-mail:zhyy@chzu.edu.cn