氣象集約化資源池計(jì)算資源容量估計(jì)方法研究

梁中軍，何文春，韓同欣，曾　樂

(國家氣象信息中心 系統(tǒng)工程室，北京　100081)

?

工程與應(yīng)用

氣象集約化資源池計(jì)算資源容量估計(jì)方法研究

梁中軍*，何文春，韓同欣，曾樂

(國家氣象信息中心 系統(tǒng)工程室，北京100081)

精確估計(jì)計(jì)算資源的規(guī)模是氣象集約化資源池合理設(shè)計(jì)的關(guān)鍵，但是由于應(yīng)用對計(jì)算資源需求可能突發(fā)增長，應(yīng)用部署方案種類繁多等因素的存在，致使計(jì)算資源規(guī)模估計(jì)困難。為解決該問題，本文對計(jì)算資源容量規(guī)劃問題進(jìn)行建模，并在分析問題求解難度的基礎(chǔ)上，根據(jù)問題的特點(diǎn)設(shè)計(jì)了一種基于離散差分進(jìn)化算法的計(jì)算容量估計(jì)方法。在問題建模上，本文采用資源預(yù)留策略來保證應(yīng)用能獲取足夠的計(jì)算資源。在方法設(shè)計(jì)上，方法首先建立了應(yīng)用的部署順序與計(jì)算資源容量規(guī)模的映射關(guān)系，并以所需參考服務(wù)器的規(guī)模和資源利用水平來綜合評估應(yīng)用部署順序的適應(yīng)度；然后，通過隨機(jī)方式生成初始方案,并以適應(yīng)度為評價(jià)標(biāo)準(zhǔn)，利用變異、交叉、局部搜索等操作改變應(yīng)用的部署順序；最后，通過迭代搜索估計(jì)計(jì)算資源所需的規(guī)模。實(shí)驗(yàn)結(jié)果表明該方法能有效估計(jì)計(jì)算資源容量的規(guī)模。

氣象集約化資源池；離散差分進(jìn)化算法；容量規(guī)劃；計(jì)算資源容量估計(jì)；NP完全問題

0　引　言

隨著信息技術(shù)的不斷發(fā)展，云計(jì)算技術(shù)[1]已成為各企事業(yè)單位提升部門信息化水平的重要技術(shù)。目前，氣象部門正在利用云計(jì)算技術(shù)來構(gòu)建氣象集約化資源池，以提高基礎(chǔ)設(shè)施資源的利用水平，實(shí)現(xiàn)資源的集約化管理。在集約化資源池的設(shè)計(jì)過程中，合理進(jìn)行容量規(guī)劃是有效利用基礎(chǔ)設(shè)施資源的關(guān)鍵。

在容量規(guī)劃時(shí)，氣象集約化資源池的計(jì)算資源容量規(guī)模不僅要滿足多個(gè)氣象業(yè)務(wù)系統(tǒng)的需求，還要盡量避免資源浪費(fèi)。然而，由于應(yīng)用對計(jì)算資源需求可能突發(fā)增長，應(yīng)用部署方案種類繁多等因素的存在，氣象集約化資源池計(jì)算容量估計(jì)面臨下列挑戰(zhàn)。

(1)氣象集約化資源池所需的計(jì)算容量應(yīng)該滿足氣象業(yè)務(wù)系統(tǒng)對計(jì)算資源的需求，以保證業(yè)務(wù)穩(wěn)定運(yùn)行。由于氣象應(yīng)用系統(tǒng)的運(yùn)行狀態(tài)具有一定不確定性(例如：系統(tǒng)處理的氣象數(shù)據(jù)規(guī)模量突發(fā)增加，并發(fā)訪問突然增大等情況)，所以應(yīng)用對計(jì)算資源的需求可能會發(fā)生突發(fā)增長的情況。這可能會導(dǎo)致計(jì)算資源使用率過高，從而影響業(yè)務(wù)的運(yùn)行。如何在不確定的條件下對計(jì)算容量進(jìn)行合理估計(jì)是一個(gè)挑戰(zhàn)。

(2)在氣象集約化資源池中，各個(gè)氣象業(yè)務(wù)系統(tǒng)主要由虛擬機(jī)來承載，承載應(yīng)用組件的虛擬機(jī)的部署方案(簡稱為應(yīng)用組件的部署方案)與參考服務(wù)器的配置共同決定了資源的利用水平，以及資源池的計(jì)算能力是否能滿足業(yè)務(wù)的需要。由于部署方案是根據(jù)虛擬機(jī)和物理服務(wù)器的組合來確定，所以其種類較多，計(jì)算資源容量估計(jì)困難。經(jīng)本文證明該問題是一個(gè)NP完全問題，計(jì)算容量規(guī)劃問題求解難度較大。

(3)雖然已有學(xué)者提出一些虛擬機(jī)部署算法[2-6]或調(diào)度算法[7-10]用于計(jì)算虛擬機(jī)的放置方案，但是這些算法沒有考慮應(yīng)用對資源需求突發(fā)增長的情況，難以被直接用于估算氣象集約化資源池中計(jì)算資源的容量。與虛擬機(jī)調(diào)度問題和虛擬機(jī)部署問題不同，虛擬機(jī)部署或調(diào)度問題的已知條件是物理服務(wù)器的信息是確定的，而求解本問題需要在多個(gè)參考物理服務(wù)器中選擇合適的型號，并估計(jì)所需物理服務(wù)器的數(shù)量。

為解決上述問題，本文對計(jì)算資源容量規(guī)劃問題進(jìn)行建模，并在分析問題求解難度的基礎(chǔ)上，根據(jù)問題的特點(diǎn)設(shè)計(jì)了一種基于離散差分進(jìn)化算法的計(jì)算容量估計(jì)方法。在問題建模上，本文采用資源預(yù)留策略來應(yīng)對系統(tǒng)對計(jì)算資源的需求可能會突發(fā)增長的情況，保證應(yīng)用能獲取足夠的計(jì)算資源。在方法設(shè)計(jì)上，方法首先建立了應(yīng)用部署順序與計(jì)算資源容量規(guī)模的映射關(guān)系，并根據(jù)所需參考服務(wù)器的規(guī)模和資源利用水平來綜合評估應(yīng)用部署順序的適應(yīng)度；然后，通過隨機(jī)方式生成初始方案,并以適應(yīng)度為評價(jià)標(biāo)準(zhǔn)，利用變異、交叉、局部搜索等操作改變應(yīng)用的部署順序；最后，通過迭代搜索估計(jì)計(jì)算資源所需的規(guī)模。實(shí)驗(yàn)結(jié)果表明本方法能有效估計(jì)計(jì)算資源的規(guī)模。

1　氣象集約化資源池設(shè)計(jì)

氣象集約化資源池的設(shè)計(jì)目的就是根據(jù)氣象信息化的發(fā)展要求，滿足業(yè)務(wù)系統(tǒng)發(fā)展、業(yè)務(wù)遷移整合對基礎(chǔ)設(shè)施資源的需要，實(shí)現(xiàn)基礎(chǔ)設(shè)施資源的集約化管理。氣象集約化資源池主要包含計(jì)算、存儲和網(wǎng)絡(luò)三類資源。 設(shè)計(jì)步驟主要包括：系統(tǒng)需求調(diào)研、資源池硬件軟件選型和容量規(guī)劃，具體描述如下。

(1)系統(tǒng)需求調(diào)研就是要對氣象集約化資源池承載的應(yīng)用系統(tǒng)的需求進(jìn)行調(diào)研，收集整理內(nèi)容包括業(yè)務(wù)系統(tǒng)的硬件資源現(xiàn)狀和其未來的新增需求，具體信息包括：CPU、內(nèi)存、存儲和網(wǎng)絡(luò)。

(2)資源池硬件軟件選型就是按照氣象集約化資源池對硬件和軟件的技術(shù)指標(biāo)，平衡價(jià)格、產(chǎn)品穩(wěn)定及易用性等因素初步選擇參考軟硬件的型號。其中，在服務(wù)器的初步選擇上優(yōu)先選擇整體容量大、可擴(kuò)展性強(qiáng)的物理服務(wù)器，存儲需要滿足業(yè)務(wù)系統(tǒng)的存儲容量需求及I/O帶寬的需求，網(wǎng)絡(luò)要滿足應(yīng)用及管理的性能要求，虛擬化軟件要滿足對硬件支持的技術(shù)指標(biāo)。通過上述選型步驟可獲得若干個(gè)參考服務(wù)器，它們將在容量規(guī)劃階段進(jìn)一步被選擇。

(3)容量規(guī)劃就是在調(diào)研選型的基礎(chǔ)上對硬件資源的規(guī)模進(jìn)行估計(jì)，規(guī)劃內(nèi)容主要是氣象集約化資源池的計(jì)算資源與存儲資源。其中，計(jì)算資源的容量是所有物理服務(wù)器的CPU和內(nèi)存的總和,存儲的總?cè)萘渴撬写鎯θ萘康目偤汀?/p>

2　計(jì)算資源容量規(guī)劃問題描述

本文重點(diǎn)關(guān)注設(shè)計(jì)過程中的容量規(guī)劃步驟，主要研究計(jì)算容量規(guī)劃問題。在估計(jì)計(jì)算資源的容量時(shí)，通常需要考慮以下因素。

①氣象集約化資源池主要承載各類氣象業(yè)務(wù)應(yīng)用，為此，容量規(guī)劃需要確保氣象業(yè)務(wù)系統(tǒng)擁有足夠的計(jì)算能力，以保證業(yè)務(wù)能夠穩(wěn)定運(yùn)行。

②氣象集約化資源池的建設(shè)目的就是要提高資源的利用水平，為此，容量規(guī)劃要考慮氣象業(yè)務(wù)應(yīng)用部署在資源池后的資源利用率達(dá)到一定水平。

③在氣象集約化資源池中，氣象業(yè)務(wù)系統(tǒng)主要由虛擬機(jī)來承載，承載應(yīng)用組件的虛擬機(jī)的部署方案(簡稱為應(yīng)用組件的部署方案)和參考服務(wù)器的配置共同決定了資源的利用水平和資源池的計(jì)算能力是否能滿足業(yè)務(wù)的需要。為此，容量規(guī)劃時(shí)需要綜合考慮承載氣象業(yè)務(wù)應(yīng)用虛擬機(jī)的部署與參考服務(wù)器的選擇。

④考慮到部分業(yè)務(wù)應(yīng)用的計(jì)算需求可能會突發(fā)增長，計(jì)算資源使用率過高將影響性能等因素的存在，容量規(guī)劃要考慮預(yù)留一定的計(jì)算能力來保證承載業(yè)務(wù)運(yùn)行穩(wěn)定性。

根據(jù)上述因素，氣象集約化資源池的計(jì)算資源容量規(guī)劃問題的描述如下。

計(jì)算資源容量規(guī)劃問題：已知?dú)庀髽I(yè)務(wù)應(yīng)用系統(tǒng)的計(jì)算能力需求(即：業(yè)務(wù)系統(tǒng)應(yīng)用組件對虛擬機(jī)的計(jì)算能力需求)和k種待選的參考服務(wù)器信息(包括服務(wù)器提供的計(jì)算能力信息)，假設(shè)每個(gè)應(yīng)用組件在集約化資源池只部署一次，計(jì)算資源容量規(guī)劃問題就是根據(jù)每個(gè)業(yè)務(wù)應(yīng)用對虛擬機(jī)配置需求，估算至少需要幾臺物理服務(wù)器才能滿足所有應(yīng)用的需求，同時(shí)保證每臺物理機(jī)預(yù)留足夠資源保證業(yè)務(wù)穩(wěn)定運(yùn)行，并使得資源利用率達(dá)到某一水平。

為求解上述問題，本文對計(jì)算資源容量規(guī)劃問題進(jìn)行建模，并利用下列數(shù)學(xué)符號來表示模型中的物理含義。

根據(jù)上述數(shù)學(xué)符號表達(dá)，計(jì)算資源容量規(guī)劃問題可被表示成如下模型：

計(jì)算資源容量規(guī)劃問題的目標(biāo)：

其中，M(Hk)是第k類參考服務(wù)器的最小規(guī)模，其取值由應(yīng)用部署所需物理服務(wù)器的個(gè)數(shù)決定，具體由公式(1)計(jì)算。

(1)

在公式(1)中，wh表示第k類參考服務(wù)器h是否有部署應(yīng)用，若部署則其值為1，否則為0，具體表

表1　問題建模的數(shù)學(xué)符號及物理意義

達(dá)如公式(2)所示。

(2)

資源能力約束：在應(yīng)用組件部署后，參考服務(wù)器仍具有一定的資源能力來保證應(yīng)用穩(wěn)定運(yùn)行。即：

(3)

(4)

其中，j∈[1,k]，dih是應(yīng)用組件與第j類參考服務(wù)器h的放置關(guān)系。

資源利用水平約束：氣象集約化資源池的資源利用率要達(dá)到一定水平。即：

(5)

(6)

部署約束條件：每個(gè)應(yīng)用組件只能部署在一臺服務(wù)器上，且只能部署一次。即：

(7)

通過以上描述可以看出，計(jì)算容量規(guī)劃問題等價(jià)于在不同參考服務(wù)器下尋找一種應(yīng)用放置策略，使得參考服務(wù)器的數(shù)目最小。

3　問題分析

為求解上述問題，本節(jié)對問題的求解難度進(jìn)行分析，通過理論證明該問題是NP完全問題，因此無法在多項(xiàng)式時(shí)間內(nèi)進(jìn)行求解，具體證明見定理1。

定理1：計(jì)算容量規(guī)劃問題是NP完全問題。

證明：假設(shè)計(jì)算容量規(guī)劃問題可以在多項(xiàng)式時(shí)間內(nèi)完成求解。根據(jù)文獻(xiàn)[11]可知裝箱問題是一個(gè)NP完全問題，該問題就是要尋求一種放置方式將n個(gè)物品放入若干個(gè)容量大小為C的箱子，使得箱子的占用數(shù)最少。

考慮本問題的特殊場景：有n個(gè)應(yīng)用組件需要部署，且當(dāng)前只有一種參考服務(wù)器，其計(jì)算能力為C；資源池的利用水平約束為零，估算至少需要幾臺物理服務(wù)器才能滿足需求。上述特殊情況的問題的求解等價(jià)于求解裝箱問題。

由于裝箱問題無法在多項(xiàng)式時(shí)間內(nèi)完成求解，所以本問題的特殊場景也無法在同樣的時(shí)間內(nèi)完成求解。因此，該結(jié)論與上述假設(shè)條件矛盾，假設(shè)條件不成立，即證明計(jì)算容量規(guī)劃問題無法在多項(xiàng)式時(shí)間內(nèi)完成求解，該問題是NP完全問題。

由于本問題屬于NP完全問題，所以難以設(shè)計(jì)精確的算法來對問題進(jìn)行求解。為此，結(jié)合問題的特點(diǎn)，本文設(shè)計(jì)下列近似算法來估計(jì)計(jì)算資源的容量。

4　基于離散差分進(jìn)化算法的計(jì)算容量估計(jì)方法

由于計(jì)算資源容量規(guī)劃問題無法在多項(xiàng)式時(shí)間內(nèi)精確求解，所以本文設(shè)計(jì)了一種基于離散差分進(jìn)化算法的計(jì)算容量估計(jì)方法(A Differential Evolution Algorithm For Estimating The Computing Resource Scale，簡稱為DEAECRS)。該方法的基本思想是根據(jù)應(yīng)用組件的部署方案來計(jì)算參考服務(wù)器的規(guī)模，通過離散差分進(jìn)化算法動態(tài)改變應(yīng)用組件的部署方案，從而迭代搜索參考服務(wù)器的最小規(guī)模。其中，應(yīng)用組件在參考服務(wù)器上的部署方案按照依次部署的方式生成，離散差分進(jìn)化算法利用變異、交叉和局部搜索等步驟來改變應(yīng)用組件的順序，從而生成不同的部署方案。

4.1部署方案的生成與容量規(guī)模計(jì)算

在氣象集約化資源池中，計(jì)算資源所需的規(guī)模是由應(yīng)用組件的部署方案和搭建資源池的服務(wù)器的配置所共同決定。為了評估其規(guī)模，本文首先生成應(yīng)用組件的部署方案，然后，根據(jù)方案估計(jì)其所需服務(wù)器的數(shù)量。為保證部署方案滿足資源能力約束條件，每類參考服務(wù)器上的部署方案將采用順序部署的方式生成。假設(shè)已知應(yīng)用組件的部署順序?yàn)镻，則其在第j類參考服務(wù)器的部署方案可通過下列步驟獲得：

步驟1：對于當(dāng)前待部署應(yīng)用組件i而言，首先需要判斷應(yīng)用組件i是否為第一個(gè)待部署的應(yīng)用，或者當(dāng)前已部署應(yīng)用組件的物理服務(wù)器中是否有服務(wù)器滿足公式(3)和公式(4)的要求，若其是第一個(gè)待部署的應(yīng)用或不滿足公式(3)和公式(4)的要求，則方案需要新增物理服務(wù)器來對應(yīng)用組件i進(jìn)行部署，否則執(zhí)行步驟2。

步驟2：采用貪婪策略從滿足資源能力約束的服務(wù)器中選擇綜合資源利用率最高的物理服務(wù)器進(jìn)行部署。即，首先根據(jù)公式(8)評估每一個(gè)備選物理服務(wù)器在部署應(yīng)用組件i后的資源綜合利用率U(Ai,Sj)，然后，選擇綜合利用率最高的物理服務(wù)器對應(yīng)用組件i進(jìn)行部署。

(8)

(9)

在公式(9)中，uc，um分別是資源池在建設(shè)時(shí)CPU和內(nèi)存預(yù)計(jì)達(dá)到的利用水平。

于是基于固定的部署順序，針對不同類參考服務(wù)器，采用上述步驟分別可獲得各類參考服務(wù)器所需的數(shù)量。

由于資源池建設(shè)需要滿足資源利用水平約束，所以并非所有的順序都能滿足問題的約束要求。為此，本文利用離散差分進(jìn)化算法通過改變應(yīng)用的部署順序來迭代估計(jì)計(jì)算資源的規(guī)模。

4.2問題映射

通過分析上述計(jì)算資源容量規(guī)模估計(jì)算法可以看出，輸入不同的部署順序?qū)@得不同部署方案，繼而獲得不同的計(jì)算資源規(guī)模。為此，本文通過改變應(yīng)用的部署順序來迭代搜索計(jì)算資源所需的最小規(guī)模。于是根據(jù)上述思想，本問題采用排列的方式來表示應(yīng)用組件的部署順序，于是計(jì)算資源規(guī)模估計(jì)問題將被映射成根據(jù)n個(gè)應(yīng)用組件的部署排列求解參考服務(wù)器的最小規(guī)模問題。其中，部署排列表示為P={p1,p2,...,pn}，{p1,p2,...,pn}是應(yīng)用1至n的一個(gè)排列。

4.3適應(yīng)度函數(shù)

為指導(dǎo)算法有效估計(jì)計(jì)算資源的規(guī)模，本文采用適應(yīng)度函數(shù)公式(10)來評估每一種部署順序的優(yōu)劣。部署順序獲得的適應(yīng)度取值是由每類參考服務(wù)器的數(shù)量以及方案滿足資源利用水平約束的情況所共同確定。

(10)

在公式(10)中，f(P,Sj)是部署順序P在第j類參考服務(wù)器上部署獲得的適應(yīng)度，其取值分兩種情況來計(jì)算，當(dāng)應(yīng)用按照部署順序P在第j類參考服務(wù)器上部署后滿足資源利用水平約束時(shí)，f(P,Sj)的取值為物理服務(wù)器數(shù)量的倒數(shù)，當(dāng)其不滿足資源利用水平約束時(shí)，f(P,Sj)的取值為懲罰函數(shù)PF(P,Sj)，具體描述如公式(11)所示。

(11)

在公式(11)中，W(P,Sj)是應(yīng)用按照部署順序P采用4.1節(jié)中的部署方法，在第j類參考服務(wù)器上部署所需物理服務(wù)器的數(shù)量，懲罰函數(shù)PF(P,Sj)的取值分三種情況(即，僅滿足內(nèi)存利用水平約束、僅滿足CPU利用水平約束和都不滿足)計(jì)算。

①當(dāng)部署方案僅滿足內(nèi)存利用水平時(shí)，懲罰函數(shù)PF(P,Sj)的取值可由公式(12)計(jì)算獲得。

(12)

② 當(dāng)部署方案僅滿足CPU利用水平時(shí)，懲罰函數(shù)PF(P,Sj)的取值由公式(13)計(jì)算獲得

(13)

③當(dāng)部署方案對資源利用水平約束都不滿足時(shí)，懲罰函數(shù)PF(P,Sj)的取值由公式(14)計(jì)算獲得。

(14)

在公式(12)-(14)中，θ是內(nèi)存利用率的重要程度，Um(P,Sj)和Uc(P,Sj)分別是應(yīng)用按照順序P在第j類參考服務(wù)器部署后的內(nèi)存利用水平以及CPU利用水平，其取值可由公式(15)和公式(16)計(jì)算。

(15)

(16)

4.4部署順序的變更

為有效求解計(jì)算容量規(guī)劃問題，本文借鑒文獻(xiàn)[12]中的操作步驟來改變應(yīng)用的部署順序，以此來迭代搜索參考服務(wù)器所需的最小規(guī)模。這些操作包括：變異操作、交叉操作和局部搜索，具體描述如下所示。

變異操作：根據(jù)其他兩種應(yīng)用部署順序的差異，改變當(dāng)前方案的部署順序。具體步驟就是首先計(jì)算其他兩種部署順序的差異(即，每個(gè)應(yīng)用在不同部署順序中的位置偏移)，然后根據(jù)差異改變當(dāng)前部署順序生成新的方案。假設(shè)當(dāng)前部署順序?yàn)镻1，其他兩種部署順序?yàn)镻2和P3，則當(dāng)前的部署順序P1可以通過P1⊕(P2?P3)而改變。其中，?操作可用于計(jì)算順序之間的差異，⊕操作可根據(jù)部署順序之間的差異信息將應(yīng)用的部署順序轉(zhuǎn)換成新的排列。例如：應(yīng)用的三個(gè)部署順序分別為P1=(4,3,2,1,5)，P2=(1,2,3,4,5)，P3=(2,1,4,3,5)，則對于應(yīng)用組件1而言，它在P2中是第1個(gè)部署，在P3中是第2個(gè)部署，部署順序的差異為1，于是在本例子中，部署順序P2與P3的差異為P2?P3={1，-1,1，-1,0},P1的新部署順序?yàn)?3,4,1,2,5)。

交叉操作：根據(jù)兩個(gè)應(yīng)用部署的順序的信息交叉生成四個(gè)新的部署順序。具體步驟就是首先選擇交叉操作的位置，然后，將一個(gè)方案的部署順序的片段復(fù)制到新方案中，并從另一方案中選擇不重復(fù)的應(yīng)用依次復(fù)制到新方案空缺的位置里。其中，交叉操作的位置采用隨機(jī)生成，它將方案劃分成2個(gè)部分，復(fù)制部分和填充部分。例如：應(yīng)用的部署順序?yàn)镻4=(1,2,3,4,5)和P5=(5,1,3,2,4)，交叉位置為第2個(gè)位置和第4個(gè)位置，則從P4中復(fù)制由P5中填充交叉生成的新部署順序?yàn)镻6=(5,2,3,4,1)和P7=(1,3,2,4,5)，從P5中復(fù)制由P4中填充交叉生成的新部署順序?yàn)镻8=(4,1,3,2,5)和P9=(5,1,2,3,4)。其中，在新生成的部署順序中，下劃線部分為復(fù)制部分，其他為填充部分。

局部搜索操作：局部搜索就是按照一定概率采用刪除再插入的方式對方案的部署順序進(jìn)行優(yōu)化。具體步驟是按照一定概率β從方案中依次刪除一個(gè)應(yīng)用，重新分配其部署的順序，并選擇適應(yīng)度值最高的部署順序作為下次迭代搜索的初始順序。

4.5算法描述

根據(jù)上述操作，基于離散差分進(jìn)化算法的計(jì)算容量估計(jì)方法可通過下列步驟獲得參考服務(wù)器的最小規(guī)模。

步驟1：初始信息設(shè)置。首先，設(shè)置離散差分進(jìn)化算法的種群規(guī)模、最大迭代次數(shù)、局部搜索執(zhí)行的概率，參考服務(wù)器的CPU與內(nèi)存信息，應(yīng)用對CPU和內(nèi)存的需求，資源利用率(即：CPU利用率，內(nèi)存的利用率)的期望水平，然后，按照種群規(guī)模隨機(jī)生成若干組部署順序，按照公式(10)來計(jì)算部署順序的適應(yīng)度，形成部署順序種群，并找出種群中的最優(yōu)部署順序。

步驟2：對種群中每種部署順序進(jìn)行變異操作生成新的部署順序。具體操作就是從種群中選擇其他兩種部署順序，根據(jù)其差異改變當(dāng)前方案的部署順序，并評估其適應(yīng)度。

步驟3：對種群中的每種部署順序及其變異個(gè)體進(jìn)行交叉操作生成四個(gè)新的部署順序，計(jì)算新順序的適應(yīng)度，從中選擇適應(yīng)度最高的新部署順序進(jìn)行下一步操作。

步驟4：按照局部搜索概率對交叉生成且適應(yīng)度最高的新部署順序進(jìn)行局部搜索。當(dāng)執(zhí)行局部搜索時(shí)，依次刪除該順序中一個(gè)應(yīng)用，并重新分配其部署的順序，計(jì)算其適應(yīng)度，選擇適應(yīng)度最高的順序作為該類部署順序的變更方案；否則將步驟3中適應(yīng)度最高的部署順序作為變更方案執(zhí)行步驟5。

步驟5：分析種群中每類部署順序的變更方案和原部署順序的適應(yīng)度大小，若變更方案的適應(yīng)度更高，則用變更順序替代原部署順序進(jìn)行下一次迭代。

步驟6：更新種群中的最優(yōu)個(gè)體，并判斷算法是否滿足終止條件，若滿足則輸出所需參考服務(wù)器的最小規(guī)模。否則，轉(zhuǎn)步驟2繼續(xù)執(zhí)行。

5　實(shí)驗(yàn)分析

為了分析本文所提方法的有效性，實(shí)驗(yàn)以資源池所選參考服務(wù)器的數(shù)量、資源池的計(jì)算資源利用水平為綜合評價(jià)指標(biāo)，對比下列算法來分析方法的估計(jì)效果。

基于最佳適應(yīng)算法的計(jì)算資源容量估計(jì)(ABestFitAlgorithmForEstimatingTheComputingResourceScale，簡稱為BFECRS):該方法針對每類參考服務(wù)器，首先，按順序依次部署各個(gè)應(yīng)用生成部署方案，然后，根據(jù)部署方案估計(jì)所需參考服務(wù)器的數(shù)量，并選擇數(shù)量最少的參考服務(wù)器數(shù)量作為本問題的解。在部署方案生成上，算法針對每類參考服務(wù)器來分別部署，優(yōu)先把應(yīng)用部署在已經(jīng)被使用的物理服務(wù)器上，只有當(dāng)已使用物理服務(wù)器無法滿足應(yīng)用需求時(shí)，才新增物理服務(wù)器。當(dāng)有多個(gè)物理服務(wù)器可以部署時(shí)，算法將首先評估每個(gè)候選物理服務(wù)器在部署應(yīng)用后的綜合資源利用率，然后，選擇其值最高的物理服務(wù)器進(jìn)行部署。

基于最壞適應(yīng)算法的計(jì)算資源容量估計(jì)(AWorstFitAlgorithmForEstimatingTheComputingResourceScale，簡稱為WFECRS)：該算法的評估步驟與BFECRS的步驟相同，唯一的區(qū)別在于當(dāng)有多個(gè)物理服務(wù)器可以部署時(shí)，算法將首先評估每個(gè)候選物理服務(wù)器在部署應(yīng)用后的綜合資源利用率，然后，選擇其值最低的物理服務(wù)器進(jìn)行部署。

在實(shí)驗(yàn)中，四組應(yīng)用集合對計(jì)算資源的需求采用隨機(jī)模擬生成，需求內(nèi)容包括CPU的核數(shù)與內(nèi)存的大小。承載四組應(yīng)用集合所需虛擬機(jī)的規(guī)模分別為30，50，70，90，參考服務(wù)器的型號為搭建資源池的四種主流配置，其CPU和內(nèi)存的能力情況如下表所示，每類參考服務(wù)器的CPU和內(nèi)存的資源預(yù)留比例均為5%，資源池建設(shè)預(yù)計(jì)達(dá)到的CPU利用水平和內(nèi)存利用水平均為50%。

表2　實(shí)驗(yàn)中參考服務(wù)器的配置

為滿足上述四組應(yīng)用集合對計(jì)算資源的需求，本文利用WFECRS算法、BFECRS算法和DEAECRS算法來分別估計(jì)資源池中計(jì)算資源的規(guī)模，具體結(jié)果如圖1所示。

圖1　三種算法估計(jì)計(jì)算資源的規(guī)模

從圖1中可以看出，DEAECRS算法估計(jì)的計(jì)算資源的規(guī)模在四組應(yīng)用中均為最小。WFECRS算法估計(jì)的計(jì)算資源規(guī)模略高于BFECRS算法所估計(jì)的規(guī)模。

為了全面分析算法的效果，本文根據(jù)WFECRS算法、BFECRS算法和DEAECRS算法所選擇的參考服務(wù)器類型和其規(guī)模來分別計(jì)算資源池中CPU的利用水平和內(nèi)存的利用水平。具體如圖2、圖3所示。

圖2　不同算法構(gòu)建資源池的CPU利用率

圖3　不同算法構(gòu)建資源池的內(nèi)存利用率

從圖2和圖3可以看出上述三種算法均可以達(dá)到資源池建設(shè)的資源利用水平要求。其中，利用DEAECRS算法構(gòu)建的資源池在CPU利用率和內(nèi)存利用率上均高于WFECRS算法和BFECRS算法的結(jié)果。

綜上所述，本文所提的DEAECRS算法能夠有效求解計(jì)算資源容量規(guī)劃問題。

6　結(jié)　語

本文主要解決氣象集約化資源池的計(jì)算資源容量規(guī)劃問題。在問題建模和理論分析的基礎(chǔ)上，提出了一種基于離散差分進(jìn)化算法的計(jì)算容量估計(jì)方法，并通過實(shí)驗(yàn)對比證明該方法能夠有效估計(jì)計(jì)算資源的規(guī)模。雖然，本文給出了計(jì)算資源容量的估計(jì)方法，但是在容量規(guī)劃時(shí)還要考慮存儲資源的規(guī)劃問題。為此，下一步的研究，將根據(jù)氣象應(yīng)用對存儲的I/O要求和應(yīng)用數(shù)據(jù)的規(guī)模，著重解決存儲的容量規(guī)劃問題。

[1]王棟, 芮平亮. 云霧環(huán)繞的數(shù)據(jù)中心全景剖析[J]. 中國電子科學(xué)研究院學(xué)報(bào), 2011, 06(3):324-327.

[2]LI, B, et al. EnaCloud: An Energy-Saving Application Live Placement Approach for Cloud Computing Environments[C]. //Proceedings of the 2009 IEEE International Conference on Cloud Computing IEEE Computer Society, 2009:17-24.

[3]劉志飄, 王尚廣, 孫其博,等. 一種能量感知的虛擬機(jī)放置智能優(yōu)化算法[J]. 華中科技大學(xué)學(xué)報(bào):自然科學(xué)版, 2012(S1):398-402.

[4]李強(qiáng), 郝沁汾, 肖利民,等. 云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào), 2011,34(12):2253-2264.

[5]楊靖, 張宏軍, 趙水寧,等. 基于粒子群優(yōu)化算法的虛擬機(jī)部署策略[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36(1):117-121.

[6]張笑燕, 王敏訥, 杜曉峰. 云計(jì)算虛擬機(jī)部署方案的研究[J]. 通信學(xué)報(bào), 2015(3):241-248.

[7]SUN, X, et al. Multi-dimensional Resource Integrated Scheduling in a Shared Data Center[C]. //Distributed Computing Systems Workshops (ICDCSW), 2011 31st International Conference on IEEE, 2011:7-13.

[8]MENG, X, et al. Efficient resource provisioning in compute clouds via VM multiplexing[C]. //Proceedings of the 7th International Conference on Autonomic Computing, 2010:11-20.

[9]肖鵬, 劉洞波, 屈喜龍. 云計(jì)算中基于能耗比例模型的虛擬機(jī)調(diào)度算法[J]. 電子學(xué)報(bào), 2015(2):305-311.[10]袁愛平, 萬燦軍. 云環(huán)境下基于改進(jìn)遺傳算法的虛擬機(jī)調(diào)度策略[J]. 計(jì)算機(jī)應(yīng)用, 2014, 34(2):357-359.

[11]GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. New York: W. H. Freeman and Company, 1979:221-226.

[12]董明剛. 基于差分進(jìn)化的優(yōu)化算法及應(yīng)用研究[D]. 浙江大學(xué), 2012:13-20.

梁中軍(1983—)，男，新疆人，博士，主要研究方向?yàn)樵朴?jì)算與大數(shù)據(jù)；E-mail：liangzj@cma.gov.cn

何文春(1982—)男，湖北人, 高級工程師，主要研究方向?yàn)樵朴?jì)算和氣象數(shù)據(jù)存儲；

韓同欣(1982—)，男，山東人，高級工程師，主要研究方向?yàn)樵朴?jì)算；

曾樂(1977—)，女，湖南人，高級工程師，博士，主要研究方向?yàn)樵朴?jì)算和分布式數(shù)據(jù)處理。

Research on Computing Resource Scale Estimating Method for Intensive Meteorological Resource Pool

LIANG Zhong-jun*, HE Wen-chun, HAN Tong-xing, ZENG Le

(Engineering system Division, National Meteorological Information Center, Beijing 100081, China)

Estimating the scale of computing resource accurately is crucial for designing the intensive meteorological resource pool. However，it is difficult to estimate the scale, due to the growth of emergency demand for computing resource and a large number of schemes for deploying the meteorological application in different servers. In this paper, a model was built to describe the problem of estimating the scale of computing resource, and a differential evolution algorithm for estimating the computing resource scale was proposed to solve it by analyzing the difficulty of problem solving. To ensure the application of sufficient resources, reserving computing resource strategy was used in this model. To solve the problem，this algorithm firstly built a mapping relationship between application deployment order and computing resource scale, and a fitness function was proposed to evaluate the application deployment order by taking account of the number of servers and the resource utilization. Then, the initial application deployment orders were generated randomly, and they changed by mutation operation, crossover operation and local search operation according to their fitness. At last, the scale of computing resource was estimated after the iterative search. The experiment result shows that this algorithm can estimate the computing resource scale effectively.

Intensive Meteorological Resource Pool; Differential Evolution; Capacity Planning; estimating the computing resource scale; NP-complete problem

10.3969/j.issn.1673-5692.2016.04.017

2016-06-26

2016-07-28

TP393

A

1673-5692(2016)04-429-08