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

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

一種臨時(shí)私有云中邏輯拓?fù)涓兄淖鳂I(yè)調(diào)度算法

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

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

考慮到成本和靈活性等因素,利用公共云計(jì)算系統(tǒng)的資源構(gòu)建臨時(shí)私有云代替本地物理集群,已成為用戶在特定時(shí)間段內(nèi)處理大量并行作業(yè)的一種有效途徑。然而現(xiàn)有作業(yè)調(diào)度算法不能感知并利用臨時(shí)私有云的邏輯拓?fù)浣Y(jié)構(gòu),容易降低緊耦合并行應(yīng)用的性能。為解決該問(wèn)題,提出一種邏輯拓?fù)涓兄淖鳂I(yè)調(diào)度算法,根據(jù)私有云中虛擬機(jī)之間的帶寬和延遲等信息構(gòu)建邏輯拓?fù)潢P(guān)系,并綜合考慮用戶所提交作業(yè)的類型,進(jìn)而產(chǎn)生對(duì)應(yīng)的作業(yè)調(diào)度決策。實(shí)驗(yàn)結(jié)果表明,該算法在提高臨時(shí)私有云中緊耦合并行應(yīng)用性能方面優(yōu)于開(kāi)源云計(jì)算系統(tǒng)中常用的輪轉(zhuǎn)算法和隨機(jī)算法。

臨時(shí)私有云;并行應(yīng)用;虛擬機(jī);拓?fù)浣Y(jié)構(gòu);調(diào)度算法;網(wǎng)絡(luò)性能

1 概述

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

在一般情況下,運(yùn)行環(huán)境中的網(wǎng)絡(luò)拓?fù)鋵?duì)緊耦合并行應(yīng)用(也就是進(jìn)程之間需要頻繁通信和同步的并行應(yīng)用)的性能有著重要影響[2-3]。傳統(tǒng)的物理集群環(huán)境中,在網(wǎng)絡(luò)基礎(chǔ)設(shè)施建設(shè)完成后,計(jì)算節(jié)點(diǎn)之間的拓?fù)浣Y(jié)構(gòu)是固定的。然而,在臨時(shí)私有云環(huán)境中,虛擬機(jī)之間的網(wǎng)絡(luò)性能以及邏輯拓?fù)浣Y(jié)構(gòu)卻是多變且未知的[4],這主要?dú)w因于云計(jì)算基礎(chǔ)設(shè)施供應(yīng)商(例如Amazon EC2,阿里云等)在為用戶提供臨時(shí)私有云時(shí),根據(jù)供應(yīng)商自身的調(diào)度策略來(lái)放置和遷移虛擬機(jī),并且對(duì)用戶屏蔽了上述信息。在這種情況下,已有的作業(yè)調(diào)度算法因不能夠感知并利用臨時(shí)私有云的邏輯拓?fù)浣Y(jié)構(gòu),容易造成緊耦合并行應(yīng)用(也就是進(jìn)程之間需要頻繁的通信和同步的并行應(yīng)用)的性能降低。針對(duì)該問(wèn)題,本文提出一種邏輯拓?fù)涓兄淖鳂I(yè)調(diào)度算法以提高臨時(shí)私有云中緊耦合并行應(yīng)用的性能。

2 相關(guān)研究

在云計(jì)算環(huán)境中,當(dāng)并行應(yīng)用的進(jìn)程與虛擬機(jī)之間存在一對(duì)一的映射關(guān)系時(shí),并行應(yīng)用的調(diào)度問(wèn)題可以等價(jià)于虛擬機(jī)的調(diào)度問(wèn)題。具體地,云計(jì)算系統(tǒng)中的虛擬機(jī)調(diào)度工作大致分為3類:(1)初始的虛擬機(jī)放置,研究的是如何把用戶所請(qǐng)求的一個(gè)或多個(gè)虛擬機(jī)映射到可用的資源池中。(2)離線的虛擬機(jī)合并,研究的是如何把具有不同資源需求的虛擬機(jī)映射到物理資源中,它通過(guò)最小化活躍的物理服務(wù)器數(shù)量來(lái)節(jié)約能源。(3)在線遷移,研究的是如何制定在線虛擬機(jī)的重新映射決策。本文研究第(1)類問(wèn)題。

對(duì)于虛擬機(jī)的初始放置問(wèn)題,已有的云管理系統(tǒng)例如OpenStack[5]和OpenNebula[6]使用了輪轉(zhuǎn)算法、隨機(jī)算法、首次適應(yīng)算法和最佳適應(yīng)算法等策略。此外,研究者也提出了諸多解決方法。例如,文獻(xiàn)[7]提出使用遺傳算法來(lái)解決虛擬機(jī)的放置問(wèn)題。文獻(xiàn)[8]提出一種基于離散粒子群優(yōu)化的調(diào)度算法。文獻(xiàn)[9]提出一種融合遺傳算法與蟻群算法的混合調(diào)度算法。文獻(xiàn)[10]提出一種具備反饋機(jī)制的動(dòng)態(tài)調(diào)度算法。然而,上述方法都忽略了多個(gè)虛擬機(jī)因運(yùn)行同一個(gè)并行應(yīng)用而產(chǎn)生的緊耦合性,并且未考慮臨時(shí)私有云環(huán)境中虛擬機(jī)之間網(wǎng)絡(luò)性能的不穩(wěn)定性。

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

由以上分析可以看出,目前在臨時(shí)私有云中仍缺乏一種能夠感知并利用虛擬機(jī)之間邏輯拓?fù)浣Y(jié)構(gòu)的作業(yè)調(diào)度算法。為了解決這個(gè)問(wèn)題,本文提出了一種邏輯拓?fù)涓兄淖鳂I(yè)調(diào)度算法。

3 邏輯拓?fù)錁?gòu)建與調(diào)度算法

下文介紹了臨時(shí)私有云的邏輯拓?fù)錁?gòu)建算法,并以此為基礎(chǔ),給出了邏輯拓?fù)涓兄淖鳂I(yè)調(diào)度算法。

3.1 臨時(shí)私有云的邏輯拓?fù)?/p>

如前所述,受云計(jì)算基礎(chǔ)設(shè)施供應(yīng)商自身調(diào)度策略和資源供應(yīng)策略的影響,臨時(shí)私有云中虛擬機(jī)之間的網(wǎng)絡(luò)性能并不穩(wěn)定[4],為了能夠在調(diào)度并行應(yīng)用時(shí)充分利用虛擬機(jī)之間的網(wǎng)絡(luò)性能信息,需要獲取臨時(shí)私有云在當(dāng)前時(shí)間的一個(gè)邏輯拓?fù)浣Y(jié)構(gòu)。

在傳統(tǒng)物理集群的樹(shù)狀網(wǎng)絡(luò)拓?fù)渲?計(jì)算節(jié)點(diǎn)之間的路徑越長(zhǎng),它們之間的網(wǎng)絡(luò)性能一般會(huì)越差。以圖1中的物理集群為例,共有128個(gè)計(jì)算節(jié)點(diǎn)組成了一個(gè)樹(shù)狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。其中,編號(hào)為1～8的8個(gè)計(jì)算節(jié)點(diǎn)通過(guò)接入點(diǎn)A0互相通信,并通過(guò)A0與其余120個(gè)計(jì)算節(jié)點(diǎn)(編號(hào)為9～128)進(jìn)行通信。在這個(gè)場(chǎng)景中,計(jì)算節(jié)點(diǎn)1和節(jié)點(diǎn)8之間的網(wǎng)絡(luò)性能通常會(huì)優(yōu)于計(jì)算節(jié)點(diǎn)1和節(jié)點(diǎn)128之間的網(wǎng)絡(luò)性能。其主要原因分析如下:(1)計(jì)算節(jié)點(diǎn)1與節(jié)點(diǎn)8之間只需要通過(guò)A0進(jìn)行通信,而計(jì)算節(jié)點(diǎn)1和節(jié)點(diǎn)128之間則需要經(jīng)過(guò)A0-D0-C0-D3-A15等方可進(jìn)行通信,因此,從通信延遲的角度來(lái)看,前者要優(yōu)于后者;(2)隨著樹(shù)狀層次的增加,共享高層線路的計(jì)算節(jié)點(diǎn)數(shù)量也在增加,這必然降低了共享同一條線路的節(jié)點(diǎn)所實(shí)際分到的可用帶寬。因此,從可用帶寬的角度來(lái)看,前者要優(yōu)于后者。

圖1 集群樹(shù)狀網(wǎng)絡(luò)拓?fù)?/p>

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

對(duì)于一個(gè)由N臺(tái)虛擬機(jī)組成的臨時(shí)私有云,本文首先定義了3個(gè)矩陣來(lái)記錄虛擬機(jī)之間的網(wǎng)絡(luò)信息,分別是延遲矩陣、帶寬矩陣和網(wǎng)絡(luò)性能矩陣。其中,延遲矩陣和帶寬矩陣中的數(shù)據(jù)可以通過(guò)在每臺(tái)虛擬機(jī)中安裝測(cè)試代理的方式來(lái)獲取。在構(gòu)建臨時(shí)私有云邏輯拓?fù)渲?需要利用延遲矩陣和帶寬矩陣對(duì)虛擬機(jī)兩兩之間的網(wǎng)絡(luò)性能進(jìn)行建模,具體描述如下:

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

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

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

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

算法1邏輯拓?fù)錁?gòu)建算法

輸入網(wǎng)絡(luò)性能矩陣Performance[0,1,…,N-1] [0,1,…,N-1]

輸出臨時(shí)私有云的邏輯拓?fù)?/p>

在算法1中,根據(jù)設(shè)定的虛擬機(jī)之間的距離閾值(如partition()函數(shù)中的第5行所示)將所有虛擬機(jī)劃分為一些不重疊的分組(group),每個(gè)分組之間具有類似的網(wǎng)絡(luò)性能(即每個(gè)分組內(nèi)任一對(duì)虛擬機(jī)之間的距離不大于設(shè)定的閾值)。隨著逐漸放松距離閾值(如partition()函數(shù)中的第8行所示),小的分組(子分組)會(huì)隨之組成大的分組(父分組)。而分組之間的父子關(guān)系形成了一個(gè)樹(shù)形層次結(jié)構(gòu)(如算法1中的第6行所示)。

為了清楚地展示算法具體流程,此處以5個(gè)虛擬機(jī)(vm1～vm5)為例來(lái)進(jìn)行說(shuō)明,如圖2所示。

圖2 邏輯拓?fù)錁?gòu)建算法

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

在第1次調(diào)用partition()函數(shù)對(duì)集合set0進(jìn)行劃分時(shí),將set0中的5個(gè)分組重新劃分為2個(gè)分組,即{vm1,vm2,vm3}和{vm4,vm5},并保存在集合set1中。

在第2次調(diào)用partition()函數(shù)對(duì)集合set1進(jìn)行劃分時(shí),將set1中的2個(gè)分組劃分為一個(gè)分組,并保存在集合set2中。

經(jīng)過(guò)上述2次劃分后,得到樹(shù)形層次的邏輯拓?fù)浣Y(jié)構(gòu)logicHierarchy={set0,set1,set2}。

3.2 邏輯拓?fù)涓兄淖鳂I(yè)調(diào)度算法

在獲得了臨時(shí)私有云的邏輯拓?fù)浣Y(jié)構(gòu)信息后,本文設(shè)計(jì)一個(gè)基于邏輯拓?fù)涓兄淖鳂I(yè)調(diào)度算法(如算法2所示)。針對(duì)不同類型的并行應(yīng)用(緊耦合并行應(yīng)用和松耦合并行應(yīng)用)分別做出不同的調(diào)度決策。由構(gòu)建邏輯拓?fù)浣Y(jié)構(gòu)的算法1可知,在樹(shù)狀層次結(jié)構(gòu)里,同一層中各分組內(nèi)的虛擬機(jī)網(wǎng)絡(luò)性能相似。

算法2 邏輯拓?fù)涓兄淖鳂I(yè)調(diào)度算法

輸入作業(yè)的資源需求,臨時(shí)私有云邏輯拓?fù)浣Y(jié)構(gòu)logicTopology

輸出作業(yè)放置策略

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

當(dāng)用戶提交松耦合并行應(yīng)用時(shí),因松耦合并行應(yīng)用對(duì)虛擬機(jī)之間的網(wǎng)絡(luò)性能要求不高,所以算法只需在網(wǎng)絡(luò)性能最好的層次,從按升序排列的分組中依此收集每個(gè)分組中的空閑虛擬機(jī)(算法2中的第18行～第21行),直到收集的空閑虛擬機(jī)數(shù)量滿足松耦合并行應(yīng)用的需求為止(算法2中的第22行～第24行),或者因系統(tǒng)中沒(méi)有足夠數(shù)量的空閑虛擬機(jī)而返回空集(算法2中的第27行)。

4 實(shí)驗(yàn)結(jié)果與分析

為評(píng)估本文提出的邏輯拓?fù)涓兄惴?在不同數(shù)量的緊耦合并行應(yīng)用實(shí)驗(yàn)和不同的網(wǎng)絡(luò)性能標(biāo)準(zhǔn)差實(shí)驗(yàn)下,對(duì)其進(jìn)行性能測(cè)試,并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)設(shè)置具體如下:

(1)模擬環(huán)境

本文使用CloudSim[13]模擬了一個(gè)云計(jì)算環(huán)境。本文選擇CloudSim作為云模擬器主要考慮到以下2個(gè)原因:1)CloudSim能夠有效模擬云計(jì)算環(huán)境,并受到了國(guó)內(nèi)外研究者的廣泛認(rèn)可;2)文獻(xiàn)[14]通過(guò)擴(kuò)展CloudSim的功能已使其具備了對(duì)緊耦合并行應(yīng)用進(jìn)行模擬的能力。

(2)算法比較對(duì)象

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

由此可以看出,本文算法與上述幾種方法在關(guān)注點(diǎn)以及評(píng)價(jià)指標(biāo)方面有所不同,所以,不適合與它們進(jìn)行比較。基于以上考慮,本文選取了開(kāi)源云計(jì)算系統(tǒng)(OpenStack和OpenNebula)采用的2種通用方法(輪轉(zhuǎn)算法和隨機(jī)算法)作為對(duì)比對(duì)象。

(3)系統(tǒng)并行應(yīng)用

在實(shí)驗(yàn)中模擬了100個(gè)并行應(yīng)用,為了簡(jiǎn)單明了地對(duì)算法進(jìn)行評(píng)估,不失一般性,本文實(shí)驗(yàn)假設(shè)每個(gè)應(yīng)用包含4個(gè)并行進(jìn)程。其中,每個(gè)進(jìn)程運(yùn)行在一個(gè)單核虛擬機(jī)中。

4.2 緊耦合并行應(yīng)用實(shí)驗(yàn)

實(shí)驗(yàn)1不同數(shù)量的緊耦合并行應(yīng)用實(shí)驗(yàn)。模擬了400臺(tái)虛擬機(jī),并根據(jù)文獻(xiàn)[4]對(duì)Amazon EC2網(wǎng)絡(luò)性能的測(cè)試數(shù)據(jù)模擬生成了400臺(tái)虛擬機(jī)之間的網(wǎng)絡(luò)性能矩陣,取值范圍在400～650之間,相對(duì)標(biāo)準(zhǔn)差為13.7%。

本文實(shí)驗(yàn)中的100個(gè)并行應(yīng)用包括了X個(gè)緊耦合并行應(yīng)用(如NPB benchmark[15]中的BT,SP,IS, CG,LU和MG)以及Y個(gè)松耦合并行應(yīng)用(如NPB benchmark中的EP),其中,X+Y=100,X的初始值為10,并以10為單位遞增,最大值為90。例如在X=10,Y=90時(shí)進(jìn)行一輪實(shí)驗(yàn)(運(yùn)行5次求平均值),獲取10個(gè)緊耦合并行應(yīng)用在不同算法(邏輯拓?fù)涓兄惴?、輪轉(zhuǎn)算法、隨機(jī)算法)下的平均執(zhí)行時(shí)間,并根據(jù)理想狀態(tài)下10個(gè)緊耦合并行應(yīng)用的平均運(yùn)行時(shí)間進(jìn)行規(guī)格化處理。其中,理想狀態(tài)是指網(wǎng)絡(luò)性能矩陣中數(shù)據(jù)的標(biāo)準(zhǔn)偏差為0且能完全滿足緊耦合并行應(yīng)用對(duì)網(wǎng)絡(luò)性能的需求。

在X=20,30,…,90時(shí),分別進(jìn)行一輪上述實(shí)驗(yàn),規(guī)格化實(shí)驗(yàn)數(shù)據(jù)如圖3所示。

圖3 不同數(shù)量緊耦合并行應(yīng)用下的性能比較

具體分析如下:

(1)邏輯拓?fù)涓兄惴ǖ男阅苊黠@優(yōu)于輪轉(zhuǎn)算法和隨機(jī)算法。原因在于:相對(duì)于輪轉(zhuǎn)算法和隨機(jī)算法,邏輯拓?fù)涓兄惴軌蚶门R時(shí)私有云中虛擬機(jī)之間的網(wǎng)絡(luò)拓?fù)潢P(guān)系,選擇網(wǎng)絡(luò)性能好的多個(gè)虛擬機(jī)來(lái)運(yùn)行緊耦合并行應(yīng)用,從而達(dá)到提高緊耦合并行應(yīng)用性能的目的,而輪轉(zhuǎn)算法和隨機(jī)算法并不考慮虛擬機(jī)之間的邏輯拓?fù)潢P(guān)系。

(2)在臨時(shí)私有云環(huán)境中,輪轉(zhuǎn)算法與隨機(jī)算法的性能相近,并且比較穩(wěn)定。具體地,在上述2種算法下,緊耦合并行應(yīng)用的平均執(zhí)行時(shí)間在規(guī)格化后介于1.45～1.50之間。原因在于:臨時(shí)私有云中每個(gè)虛擬機(jī)的位置是受到云計(jì)算基礎(chǔ)設(shè)施供應(yīng)商調(diào)度算法和負(fù)載均衡算法的控制,并且這種控制對(duì)臨時(shí)私有云的所有者來(lái)說(shuō)是不透明的。因此,在臨時(shí)私有云中輪轉(zhuǎn)和隨機(jī)算法的性能是相當(dāng)?shù)?。在這種情況下,輪轉(zhuǎn)算法退化為隨機(jī)算法。

(3)隨著緊耦合并行應(yīng)用數(shù)量的增加,邏輯拓?fù)涓兄惴ǖ男阅苤饾u變差,但是仍優(yōu)于輪轉(zhuǎn)算法和隨機(jī)算法。原因在于:本文實(shí)驗(yàn)中網(wǎng)絡(luò)性能矩陣中的數(shù)值介于400～650之間,相對(duì)標(biāo)準(zhǔn)差為13.7%,也就是說(shuō),所有虛擬機(jī)之間的網(wǎng)絡(luò)性能數(shù)據(jù)并非全部相同(有的網(wǎng)絡(luò)性能好,有的網(wǎng)絡(luò)性能差)。因此,隨著緊耦合并行應(yīng)用數(shù)量的增加,網(wǎng)絡(luò)性能差的虛擬機(jī)會(huì)被用來(lái)執(zhí)行緊耦合并行應(yīng)用,從而導(dǎo)致緊耦合并行應(yīng)用的平均執(zhí)行時(shí)間也變長(zhǎng)。但是由于邏輯拓?fù)涓兄惴軌蛴行Ю锰摂M機(jī)之間的邏輯拓?fù)?其性能仍優(yōu)于輪轉(zhuǎn)和隨機(jī)算法。

4.3 網(wǎng)絡(luò)性能實(shí)驗(yàn)

實(shí)驗(yàn)2不同的網(wǎng)絡(luò)性能實(shí)驗(yàn)。虛擬機(jī)數(shù)量與實(shí)驗(yàn)1中的數(shù)量相同。因?yàn)閷?shí)驗(yàn)1中已經(jīng)比較了算法在系統(tǒng)中有不同數(shù)量緊耦合并行應(yīng)用時(shí)的性能,得出了相應(yīng)結(jié)論。因此,實(shí)驗(yàn)2固定了緊耦合并行應(yīng)用的數(shù)量(即X=10),通過(guò)改變虛擬機(jī)之間網(wǎng)絡(luò)性能矩陣的取值范圍來(lái)評(píng)估算法在不同相對(duì)標(biāo)準(zhǔn)差情況下的性能表現(xiàn)。虛擬機(jī)之間網(wǎng)絡(luò)性能矩陣的取值范圍以及相對(duì)標(biāo)準(zhǔn)差如表1所示。

表1 虛擬機(jī)間網(wǎng)絡(luò)性能矩陣的取值范圍及相對(duì)標(biāo)準(zhǔn)差

實(shí)驗(yàn)結(jié)果如圖4所示,具體分析如下:

(1)在系統(tǒng)中有10個(gè)緊耦合并行應(yīng)用的情況下(即X=10),邏輯拓?fù)涓兄惴ㄔ诓煌木W(wǎng)絡(luò)性能標(biāo)準(zhǔn)差下與理想狀態(tài)的性能相近。這說(shuō)明在不同的網(wǎng)絡(luò)性能相對(duì)標(biāo)準(zhǔn)差下,模擬系統(tǒng)中至少有40個(gè)虛擬機(jī)(10×4)的網(wǎng)絡(luò)性能與理想狀態(tài)下的網(wǎng)絡(luò)性能相當(dāng)。邏輯拓?fù)涓兄惴軌蛴行Ю眠@些網(wǎng)絡(luò)性最好的虛擬機(jī)來(lái)運(yùn)行上述10個(gè)緊耦合并行應(yīng)用。

(2)輪轉(zhuǎn)算法與隨機(jī)算法性能相近,并且性能隨著相對(duì)標(biāo)準(zhǔn)差的降低而變好,尤其是在相對(duì)標(biāo)準(zhǔn)差為2.4%時(shí),輪轉(zhuǎn)算法與隨機(jī)算法的性能接近于邏輯拓?fù)涓兄惴ㄒ约袄硐霠顟B(tài)下的性能。原因在于:隨著相對(duì)標(biāo)準(zhǔn)差的降低,虛擬機(jī)網(wǎng)絡(luò)性能越來(lái)越接近于理想狀態(tài)。此時(shí),不同算法對(duì)緊耦合并行應(yīng)用的性能影響不斷減弱。因此,邏輯拓?fù)涓兄惴?、輪轉(zhuǎn)算法和隨機(jī)算法的性能都開(kāi)始接近于理想狀態(tài)下的性能。

圖4 各虛擬機(jī)間網(wǎng)絡(luò)性能的相對(duì)標(biāo)準(zhǔn)差比較

在真實(shí)的云計(jì)算系統(tǒng)中虛擬機(jī)之間的網(wǎng)絡(luò)性能一般會(huì)隨著時(shí)間而呈現(xiàn)出波動(dòng)現(xiàn)象,因此,在算法應(yīng)用于實(shí)際臨時(shí)私有云時(shí),需要每隔一定的時(shí)間(需要根據(jù)不同的云計(jì)算系統(tǒng)設(shè)定不同值)重新構(gòu)建臨時(shí)私有云的邏輯拓?fù)浣Y(jié)構(gòu)。不失一般性,實(shí)驗(yàn)1和實(shí)驗(yàn)2評(píng)估了一次邏輯拓?fù)錁?gòu)建完成后的算法性能。從實(shí)驗(yàn)結(jié)果可以看出,邏輯拓?fù)涓兄{(diào)度算法更適合于臨時(shí)私有云環(huán)境。

5 結(jié)束語(yǔ)

本文研究在創(chuàng)建臨時(shí)私有云后,如何利用邏輯拓?fù)湫畔?lái)優(yōu)化緊耦合并行應(yīng)用性能的問(wèn)題。為獲取邏輯拓?fù)湫畔?提出一個(gè)邏輯拓?fù)錁?gòu)建算法,并基于此設(shè)計(jì)一種邏輯拓?fù)涓兄淖鳂I(yè)調(diào)度算法。實(shí)驗(yàn)結(jié)果表明,邏輯拓?fù)涓兄恼{(diào)度算法比輪轉(zhuǎn)算法和隨機(jī)算法性能更好。在真實(shí)環(huán)境中構(gòu)建原型系統(tǒng)以進(jìn)一步測(cè)試和優(yōu)化邏輯拓?fù)涓兄恼{(diào)度算法是后續(xù)研究的重點(diǎn)。

[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] 鄔開(kāi)俊,魯懷偉.云環(huán)境下基于DPSO的任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程,2014,40(1):59-62.

[9] 張 雨,李 芳,周 濤.云計(jì)算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用,2014, 50(6):51-55.

[10] 馬 莉,唐善成,王 靜,等.云計(jì)算環(huán)境下的動(dòng)態(tài)反饋?zhàn)鳂I(yè)調(diào)度算法[J].西安交通大學(xué)學(xué)報(bào),2014, 48(7):77-82.

[11] 亞馬遜公司.AWS產(chǎn)品與解決方案[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

趙玉艷,陳海寶,趙生慧.一種臨時(shí)私有云中邏輯拓?fù)涓兄淖鳂I(yè)調(diào)度算法[J].計(jì)算機(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

安徽省自然科學(xué)基金資助面上項(xiàng)目(1408085MF126);安徽省教育廳自然科學(xué)研究基金資助重大項(xiàng)目(KJ2011ZD06);滁州學(xué)院優(yōu)秀青年人才基金資助重點(diǎn)項(xiàng)目(2013RC006);滁州學(xué)院科研啟動(dòng)基金資助項(xiàng)目(2014qd016)。

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

2014-08-20

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