一種臨時私有云中邏輯拓撲感知的作業(yè)調(diào)度算法

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

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

一種臨時私有云中邏輯拓撲感知的作業(yè)調(diào)度算法

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

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

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

臨時私有云;并行應(yīng)用;虛擬機;拓撲結(jié)構(gòu);調(diào)度算法;網(wǎng)絡(luò)性能

1 概述

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

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

2 相關(guān)研究

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

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

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

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

3 邏輯拓撲構(gòu)建與調(diào)度算法

下文介紹了臨時私有云的邏輯拓撲構(gòu)建算法,并以此為基礎(chǔ),給出了邏輯拓撲感知的作業(yè)調(diào)度算法。

3.1 臨時私有云的邏輯拓撲

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

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

圖1 集群樹狀網(wǎng)絡(luò)拓撲

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

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

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

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

算法1邏輯拓撲構(gòu)建算法

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

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

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

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

圖2 邏輯拓撲構(gòu)建算法

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

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

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

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

3.2 邏輯拓撲感知的作業(yè)調(diào)度算法

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

算法2 邏輯拓撲感知的作業(yè)調(diào)度算法

輸入作業(yè)的資源需求,臨時私有云邏輯拓撲結(jié)構(gòu)logicTopology

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

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

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

4 實驗結(jié)果與分析

為評估本文提出的邏輯拓撲感知算法,在不同數(shù)量的緊耦合并行應(yīng)用實驗和不同的網(wǎng)絡(luò)性能標準差實驗下,對其進行性能測試,并對實驗結(jié)果進行分析。

4.1 實驗設(shè)置

實驗設(shè)置具體如下:

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

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

(2)算法比較對象

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

由此可以看出,本文算法與上述幾種方法在關(guān)注點以及評價指標方面有所不同,所以,不適合與它們進行比較?；谝陨峡紤],本文選取了開源云計算系統(tǒng)(OpenStack和OpenNebula)采用的2種通用方法(輪轉(zhuǎn)算法和隨機算法)作為對比對象。

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

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

4.2 緊耦合并行應(yīng)用實驗

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

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

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

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

具體分析如下:

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

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

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

4.3 網(wǎng)絡(luò)性能實驗

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

表1 虛擬機間網(wǎng)絡(luò)性能矩陣的取值范圍及相對標準差

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

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

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

圖4 各虛擬機間網(wǎng)絡(luò)性能的相對標準差比較

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

5 結(jié)束語

本文研究在創(chuàng)建臨時私有云后,如何利用邏輯拓撲信息來優(yōu)化緊耦合并行應(yīng)用性能的問題。為獲取邏輯拓撲信息,提出一個邏輯拓撲構(gòu)建算法,并基于此設(shè)計一種邏輯拓撲感知的作業(yè)調(diào)度算法。實驗結(jié)果表明,邏輯拓撲感知的調(diào)度算法比輪轉(zhuǎn)算法和隨機算法性能更好。在真實環(huán)境中構(gòu)建原型系統(tǒng)以進一步測試和優(yōu)化邏輯拓撲感知的調(diào)度算法是后續(xù)研究的重點。

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

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

[10] 馬 莉,唐善成,王 靜,等.云計算環(huán)境下的動態(tài)反饋作業(yè)調(diào)度算法[J].西安交通大學(xué)學(xué)報,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

趙玉艷,陳海寶,趙生慧.一種臨時私有云中邏輯拓撲感知的作業(yè)調(diào)度算法[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é)基金資助面上項目(1408085MF126);安徽省教育廳自然科學(xué)研究基金資助重大項目(KJ2011ZD06);滁州學(xué)院優(yōu)秀青年人才基金資助重點項目(2013RC006);滁州學(xué)院科研啟動基金資助項目(2014qd016)。

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

2014-08-20

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