基于多層圖劃分的云環境軟件部署管理算法

戴偉，劉華

（1. 華中科技大學 管理學院，湖北 武漢，430074；2. 湖北理工學院 經濟與管理學院，湖北 黃石，435003）

基于多層圖劃分的云環境軟件部署管理算法

戴偉1，2，劉華1

（1. 華中科技大學 管理學院，湖北 武漢，430074；2. 湖北理工學院 經濟與管理學院，湖北 黃石，435003）

針對在云服務器上軟件構件分配時需要最大限度地減少所需帶寬的問題，提出一種基于多層圖劃分算法的混合算法，來解決云計算環境中的軟件部署問題。該算法對重邊匹配（HEM）算法進行改進，同時添加1個新的約束條件來進行粗化，且使用類似KL的算法進行細分，最后結合退火算法從而實現對圖劃分算法的重新設計和評估。與傳統的圖劃分相比，本文提出的算法考慮到基礎設施的異構性，因此不局限于平衡劃分。實驗仿真結果表明：相比傳統的KL圖劃分算法，提出的混合算法在執行時間和求解質量之間取得很好的平衡，綜合性能優于傳統算法。

云計算；圖劃分算法；退火算法；軟件部署

當今，云計算的出現促進了效用計算［1］新模式的產生，即根據需求提供計算能力。用戶能夠通過互聯網來使用應用程序并進行存儲及處理。與維護自己的私人電腦系統相比，新的終端模式的優勢是成本更低、擴展性更高及性能更高，因此，其適用于計算負載較高的情況。使用云計算對基于Web的應用程序是有利的，而且也可以用于其他由很多服務組件組成的應用程序，這些服務組件遵循服務型的編程范式。對于中央處理器（CPU）功率或內存消耗而言，一些服務組件的需求量很大，因此，應該在云中的專用服務器上運行這些服務組件，而不是在普通臺式電腦或移動終端運行，例如目標識別中的識別組件或語音文字轉換應用程序。云計算的廣泛應用就會帶來軟件部署這一問題。在云計算環境里可以將軟件構件從移動設備上傳到云服務器，即將軟件應用程序部署到云基礎設施上，但是這種應用會顯著增加網絡流量。在均勻適度規模的數據中心內，就可用的硬件節點而言，有很多選項需要進行考慮。為了降低成本，云客戶和云供應商都十分需要通過部署優化把所有組件都要部署在具有強大工作性能的服務器上，同時最小化不同機器間的通訊開銷，但是這一過程會導致額外的延時和網絡負載。針對這一問題可以構建1個圖劃分模型，把軟件組件的加權圖劃分成若干份，用這些分區表示可用的機器［2］。此外，優化部署會隨著時間改變，因此，迫切需要找到一種快速算法來實現優化部署。本文作者提出一種能夠有效降低組件之間的通信成本，并同時實現劃分軟件應用程序的算法。這種軟件應用由若干組件組成，位于云中若干相互連接、具有不同容量的機器上。對算法的性能和執行時間，與不同的算法進行評估和比較，并討論不同參數的影響。本研究把重點放在本次評估中含有100～1 000個組件的圖上。

1 原理介紹

1.1 圖劃分原理

在計算機科學的很多領域，圖劃分是一個基本的問題，例如超大規模集成電路（VISI）設計、并行處理與負載平衡［3］。圖劃分問題能夠解決在 k等集中的圖分割問題，同時最小化等集間的邊權。當k=2時，稱作是最小分割對分問題。

第1種算法就是所謂的移動型算法，這種算法嘗試通過在劃分區之間移動頂點或交換頂點迭代改進劃分［4］。通過加入頂點移動選擇降低圖切割的成本，這種算法會收斂到局部最優。FIDUCCIA等［5］為KL算法引進了若干個最優解并產生了圖劃分的線性時間算法。移動型算法能夠與隨機算法結合，如模擬退火算法，粒子群優化算法或為脫離局部最優解的蟻群優化算法。迭代改進方法的最大劣勢是其性能會隨著圖的變大而惡化。

人們已經廣泛使用多層次劃分方法來劃分大圖。主導思想是：根據匹配通過合并頂點迭代的方法使原始圖粗化，直到最后留下一個具有相似結構的小圖。然后可以用擬譜方法或貪婪型圖增長方法對這個小圖標進行劃分。接下來對粗化的圖再次迭代細化。在每個層次中都使用了局部改進啟發法如 KL算法［6］。圖劃分的近期工作是以擴散或最大流量為作為研究重點。已知技術間的組合也能夠產生新的啟發法。CHARDAIRE等［7］結合貪婪算法、遺傳算法和KL優化算法，并使用了基于群數加強優化（PROBE）的啟發法。ZAMPROGNO等［8］提出了貪婪圖增長啟發法，這種啟發式結合了局部優化算法。MARTIN［9］使用了由擬譜方法和KL優化算法改進的遺傳法。

這些方法都可以把圖劃分成預先設定好的塊數且每塊大小相同。但是在云計算背景下，并非所有的機器都有同等的能力，使用的機器數量也不是預先設定好的，因此，這些算法也不能隨時使用。本文提出的算法把若干可用的具有不同能力的機器作為輸入的唯一約束條件，任何機器都不能超過這種約束條件的最大能力并且每臺機器上恰好部署1個組件。同時，仍舊可以使用原始圖劃分問題的思想，對1個優化部署進行計算。

1.2 網格上的任務分配

在網格計算背景下，可以使用圖劃分問題對異構基礎設施上的并行任務進行劃分。很多已提出的算法如MiniMax，VHEM，QM，PaGrid和MinEX結合優化算法使用多層次劃分算法，而其他的算法如PART［10］使用了模擬退火法。

所有的算法都是把重點放在以網絡模型為基礎的并行應用程序上，如流體動力學，把1個大任務分解成較小的平行小任務，網格中的每個處理器執行1個小任務，目的是為了以后盡可能快地執行這些任務，因此，要將速度最慢的節點的執行時間最小化。在本文提出的問題中，執行時間的指標沒有什么意義，因為把重點放在了云應用程序上，只要終端用戶開始使用程序，這些程序的組件就會產生負荷。網格中任務圖的結構也是以輸入網為基礎的，而就本文提出的方法而言，云應用程序的圖是以軟件組件和它們之間的相互作用為基礎的。

設定G=（V，E）為無向圖，V=｛v1， v2， …， vN｝為N個頂點的集合，E為與頂點連接的所有邊的集合。頂點代表在分布式軟件系統中部署的組件，邊代表這些組件之間的通信費用。每個頂點 vi設定 1個成本值 wj代表此頂點組件所需的資源量（如 CPU處理能力）。C=cij為G的鄰接矩陣，例如，如果vi和vj之間存在邊，那么cij等于這條邊的權值，否則cij=0。邊權值代表不同軟件組件之間的通信費用（例如帶寬）成本。

設定S=（K， L）為基礎設施的無向圖，K為可用的機器集合，L為不同機器間的鏈接。每個機器都有最大的能力Xm，每個鏈接都設定1個成本值便于使用此鏈接。從這個圖中可以推導出矩陣B=（bmn），bmn代表機器m和機器n之間交換數據的成本。

此時的目的是把每個頂點 vi分配給其中 1臺機器，這樣機器間的交換的總數據加權通過B將最小化。更正式的方法是，決策變量 Tim代表圖切割。如果組件i部署在機器m上，那么Tim等于1，否則Tim為0。為讓部署在不同機器間的節點之間的邊權值總和最小化，需要引進變量hij，當組件i和j部署在不同的機器上，hij等于1，否則為0。這樣目標函數最小化就變成了圖切割（GC）的權值：

函數P（j）返回到頂點j所部屬的機器上，變量hij可以用Tim表示為

還需要2個約束條件，對本文提出的問題進行描述。

式（3）表示的是在1臺機器上節點所使用的資源總量，但資源總量不能超過這臺機器的最大能力。式（4）確保了在每臺機器上部署1個節點。

2 提出的混合算法

由于模擬退火法（SA）的隨機因素，因此它通常探索的解空間比以KL為基礎的優化算法要大得多，這樣就會以耗費更多的計算時間才能得到最優解。因此，本文結合了這2種方法，混合算法與多層次算法非常相似：僅在最粗化階段，第1次把劃分和SA的一些操作優化。在最粗化階段，使用SA可以找到最優解，而額外的計算代價仍然相對較低。在進一步細化迭代中，再次使用KL優化算法，這樣細化過程比較快。此外，由于粗化和細化的特征，預計在鄰近最粗化圖時會出現全局最優解，因此，KL算法最終得到的局部最優解更可能也是全局最優解，而且在最粗化階段，多次使用SA優化是為了得到更好解。

2.1 多層圖形劃分算法(MLKL)

前面所述問題可看作是整數線性規劃（ILP）問題，因此，可以用ILP求解器（IBM ILOGCPLEX）找到這個問題的最優解。解決此問題所需要的時間和資源的數量會隨著圖的大小呈幾何方式增長，因此，需要用啟發法更快地尋求一個好的解決方法。本文仍可以使用針對較小圖設計的ILP解決方法來對本文提出的算法進行基準測試，但這可能需要承擔最優性的費用。

本文使用了由HENDRICKSON等［11］提出的多層次優化方法。即合并相連的頂點對圖進行粗化，最后得到1個小圖。然后再次劃分并細化小圖，同時在每個細化階段都要進行最優化劃分。劃分包括3個階段。

1） 粗化階段：粗化圖G生成一系列較小的圖G1，G2，…，Gm，得到的頂點|V1|＞|V2|＞…＞|Vm|。

2） 初始劃分階段：在最粗化的圖基礎上計算劃分P。

3） 細化階段：通過所有中間一系列圖，把圖 G中的劃分P映射回原圖。為得到更好地劃分，每一個細化階段都要使用優化算法。

2.1.1 粗化階段

在粗化階段，從圖Gi開始，通過折疊邊及合并與其他邊連接的頂點得到圖Gi+1，此時圖Gi+1的頂點較少。當折疊1條邊的時候，與這條邊相連接的兩個頂點會變成1個頂點，此時這個頂點的權值是折疊前2頂點的權值之和。當2個頂點之間有1條連接到第3個節點的邊，這2條邊會折疊成1條邊且此時這條邊的權值是這兩條邊的邊權值之和。每次粗化迭代時，匹配都會產生無公共頂點邊的集合，然后合并匹配的頂點，為了得到最小切割邊，需要折疊很多帶權值的邊，因為這些切割邊可能不是最好的切割邊。

粗化算法使用了重邊匹配（HEM）算法。該算法是由KARYPIS等［12］提出并得到廣泛使用的粗化方法。即采用隨機順序訪問圖的頂點，每個頂點u會與1個未被匹配的鄰接點v相匹配，最后得到的這條邊（u，v）就具有最大權值，這一權值超過其他與頂點u相關連的邊權值［13-15］。當頂點權值和小于最小分區的尺寸，為了能夠映射出不同機器上的最大圖的頂點，又添加了1個新的約束條件與這2個頂點相匹配。

2.1.2 初始劃分階段

經過粗化，現在的問題是對基礎設施上的軟件組件進行可行性的部署選擇。假設已有足夠的機器和資源滿足條件。此時，問題即可簡化為1個簡單的裝箱問題并且可以用首次適應算法來解決。

通過降序排列頂點權值對頂點進行排序，降序排列機器的最大能力對機器進行排序。對于每個頂點來說，機器列表都是迭代過的，然后把頂點分配到第 1臺剩有足夠能力的機器上，此后這臺機器的能力就會隨著這個頂點的權值減弱。

算法1計算初始化分的偽代碼如下：

2.1.3 細化階段

在最后階段，再次逐漸將圖細化，并使用KL優化算法改進在先前階段中得到的初始劃分。該算法是建立在HENDRICKSON等［11］提出的優化算法基礎之上的。即移動1個頂點到1個不同的組件相關聯的增益概念。這種增益可以反射出切割尺寸的凈變化，這種變化是由于把頂點從一臺機器移動到另一臺機器造成的。也就是說，增益是在頂點vi從機器m移動到機器n的過程中加入的。相關增益kmn表達如下：

當函數p（j）再次返回到當前頂點j的位置，使用改進的KL基礎優化算法進行處理，這種算法由2遍循環組成。每遍外循環都會試圖移動周圍的頂點以此找到更好的切割方式。在一遍到目前為止對最好劃分沒有任何改進的循環之后，新一遍循環也會結束，這暗示著此算法達到了局部最優。為避免此算法陷入無限循環，在單次外部循環過程中1個頂點只能移動1次。內循環會迭代選擇1個頂點讓其移動，例如具有最大增益卻受某些條件管制的頂點，但注意這也可能是 1個負增益的移動。在一定程度上負增益的移動會讓此算法有脫離陷入局部最優的可能性。當1個頂點移動的時候，這個頂點的所有鄰接點的增益也會更新。當找不到更合適的移動時，此過程就會結束。

算法2 KL優化算法偽代碼如下：

選擇不在移動列表中的且具有最高增益kmn的頂點，并讓其移動；

If （θ（p）＜0 && θ（n）-wi＞θ（m））

正確→找到更合適的移動

If （?p： θ（p）＜0） /* θ（p）表示P劃分區自由空間的數量 */

else

正確→找到更合適的移動

｝

If （找到更合適的移動）

進行移動并把此移動添加到移動列表中；

更新已移動的頂點的鄰接點的增益；

If （當前劃分＜最好劃分）

當前劃分→最好劃分；

If （如果沒有合理的正增益移動）

break；｝｝

Return 最佳劃分

當找到1個最好的劃分方式，內循環只接受正增益的移動，然后進行下一遍循環。基本原理是：將這種算法找到1個最好的劃分方式，以此得到局部優化，然后開始新的迭代，在先前迭代移動列表中出現的頂點移動可以再次被選擇作為新迭代的頂點移動。

圖1所示為符合選擇條件的局部優化。需確保沒有機器超負荷，而不是建立平衡劃分。在這方面，1個不正確的做法是阻止頂點移動，這樣會違反目標的能力條件。然而，這個規則會導致移動對局部優化造成無法避免的影響（見圖1）。

因此，允許頂點移動到1個超過最大分區權值的分區，條件是再也沒有其他的權值過大的分區。如果分區s具有很多權值，那么選擇具有最高增益的頂點，然后把它從機器m中移走并降低負荷量。符合選擇條件的局部優化如圖1所示，此方法也會收斂到1個最優解（m0=｛n0， n2｝，m1=｛n1， n3， n4｝）。

圖1 符合選擇條件的局部優化Fig.1 Suitable selection conditions of local optimization

當兩個合理的移動具有相等的增益時，選擇沒有超過目標分區邊界的移動。若不能區分出合理的移動，則選擇對分區來說非空白的移動。若仍舊不能區分出這2個移動，則局面隨機就會被打破。

不再繼續進行移動，直到對所有的頂點進行移動，便可以盡快終止這種算法以節約時間。通過截止閾值的合理選擇能夠降低執行時間，同時也不會耗費太多求解質量。如果選擇截止閾值 0，這種算法就不會接受任何帶有負增益的移動，而且會表現得像最陡下降算法一樣，在最接近的局部最小值處終止。

2.2 模擬退火法(SA)

用于解決K劃分問題的第2種方法是建立在模擬退化法（SA）基礎之上的，組合優化技術由KIRKPATRICK等［16-17］提出。為了在K劃分問題的背景下使用SA技術，受JOHNSON等［18］的啟發，本文把SA技術作為拼裝后的優化技術。JOHNSON等［18］驗證了SA對于圖對分問題的有效性。

SA算法通過把頂點從一個分區移動到另一個分區的方式把自己從一個解決方法移動到鄰近的解決方法。帶有概率經驗值（g/T）的移動會被接受，在（g/T）中，如在其中的描述，g為移動增益，T為溫度，它會隨著時間漸漸降低。為了找到上節描述條件下的最優解，需要把帶有正增益的頂點 i移動到具有概率經驗值exp（θ（p）-wi/T）但沒有足夠能力的分區上，θ（p）為在分區p上的自由空間的數量。這一移動也需要依賴溫度。這就確保了在算法快要結束時，無需過度占用分區就可以收斂到1個有效解。

SA的性能主要依賴不同退火參數的設置，退火參數包括初始溫度T1、冷卻進度表、時長長度L和終止條件。PARK等［19］提出了一個更好的退火參數集，在其基礎之上本文作者進行如下改進。

2.2.1 初始溫度T1

2.2.2 溫度冷卻

冷卻功能會漸漸把溫度降低，直到這種算法達到其終止條件。本文采用一個簡單的幾何冷卻功能，在幾何冷卻功能中，由Tk=α×Tk-1給出在k時期的溫度，α（0＜α＜1）為冷卻比。JOHNSON等［18］驗證了其他不會影響性能的冷卻函數，如線性函數或對數函數。

時長長度L指的是嘗試在每個溫度層次上移動的次數。本文把每個頂點移動到其他的機器上，因此，時長長度L=s×N×（M-1） （其中，N為頂點的個數，M為使用的機器的數量）。試驗證明：對于s來說，選取50較合適。

算法3模擬退火法偽代碼如下：

While （滿足終止條件）

｛

While （計時器≥L（時長））

｛

計數器++；

計算把頂點i移動到分區p的增益g；

If （g≥0）

｛

If （θ（p）≥wi）

執行移動；

else

｝

else

If （θ（p）≥wi）

進行移動；

If （當前劃分＜最好劃分）

當前劃分→最好劃分；｝｝

Return 最佳劃分

2.2.3 終止算法

終止條件決定算法何時達到凍結狀態以及何時終止進一步研究解決方法。當時間計數達到了預先設定的最大值或當溫度下降到預選的最終溫度以下時，一些終止條件會終止這種算法。本文作者使用了JOHNSON的終止規則［18］，即在時長結束時增加1個計數器。當計數器達到預定的終止極限I時，模擬退火法就會終止，計數器會重置為0。

表1顯示的是使用的SA細化算法中采用的模擬退火法參數，這些參數參照文獻［18-19］中的實驗設置。其中，p1為衰減參數，s為分區數量，α為冷卻比，I為計數器預定的極限值。

表1 SA細化算法參數值設置Table 1 Parameters settings of SA refinement algorithm

3 算法結果評估

用產生的含有不同大小節點的測試圖對本文提出的算法進行評估。圖由EPPSTEIN等［20］提出的冪率生成器生成，并且根據參數λ分別是0.1和0.005的指數分布指定節點和邊的權值。雖然實際應用程序的圖結構依賴于軟件設計，但是依照大多數的設計原則選取這些圖配置，目的是為了減少不同軟件組件之間的依賴性，因此，產生具有節點少、鄰接點多的圖。產生的節點權值的限制范圍為1到100，這可以直觀地代表該組件在單處理器內核上的CPU時間。

實驗環境為1臺CPU為英特爾芯片Xeon L5520（2.2 GHz）四核的惠普機架式服務器，內存8 GB，使用JAVA軟件語言進行最佳部署，隨機生成100，200，…，800個節點部署在機器上。針對每個尺寸的圖，生成了100個圖和機器權值，根據得到的圖切割尺寸和處理時間進行評估。

首先，為了顯示本文提出的方法的有效性，將本算法與理論上作為小尺寸圖的ILP最優解進行比較。對于較大尺寸的圖，就求解質量和執行時間對3種算法進行比較，研究了截止閾值對KL優化算法的影響以及SA的執行次數。

圖2（a）和（b）顯示的是由MLKL，SA和混合算法得到的與ILP最優解相關的圖切割尺寸的平均值和執行時間。

為了評估軟件組件部署效率，假設在數據中心不同服務器間的通信鏈路區中權值相同，因此，?m，n：bmn=1。由于圖代表的是交互的軟件組件，還假設重要尺寸的圖有幾百個節點。對于小圖，可以將該解與最優ILP解進行對比（圖2）。

SA和混合算法使用了模擬退火法的4項并行執行的最好解決方法。混合算法所得結果比MLKL結果好。然而，混合算法和SA的執行時間分別比MLKL多3～8倍。

對于較大的圖，ILP處理器需要很長的時間才能找到1個解，因此，對與MLKL相關的算法進行比較，也對不同參數的影響進行了討論，這些參數包括 KL優化算法的截止閾值和SA優化算法的并行執行次數。

圖2 不同算法的圖切割尺寸和執行時間Fig.2 Graph partitioning size and execution time of different algorithms

圖3（a）所示為MLKL算法的截止閾值為0，200和500時的求解結果。當前劃分的圖切割偏差超過當時找到的最佳解的某一截止閾值，KL優化算法就會終止。0截止閾值意味著不允許有負增益的移動，從而這種優化就表現為最陡下降算法。閾值越高，就越接近無閾值的初始解。隨著圖尺寸的變大，允許帶有負增益的移動得到的提升就越少。圖3（b）所示為不同截止閾值算法的執行時間，以求解質量為代價，利用截止閾值可以減少執行時間。

圖4（a）和圖4（b）所示為 SA算法的求解質量與MLKL算法的對比以及SA算法不同數量的執行運行的執行時間。相對較小的圖而言，與MLKL找到的解相比，SA找到的解較好；但隨著圖尺寸的變大，MLKL找到的解比SA的好。由于搜索空間的增加，SA將不太可能找到可以得到最優解的隨機移動。SA執行時間要高于MLKL的執行時間。

隨著圖尺寸的增大，允許負增益移動的求解質量的提高會越少。圖5（a）顯示的是相對于MLKL算法的混合算法的求解質量，圖5（b）顯示的是執行時間。與MLKL相比，混合算法得到了稍好的分區，但是隨著圖變大，這種改進開始減少。就執行時間而言，混合算法比SA的少但仍比MLKL的執行時間長。

圖3 不同閾值下MLKL算法的圖切割尺寸和執行時間Fig.3 Graph partitioning size and execution time of MLKL under different thresholds

圖4 不同閾值下SA算法的圖切割尺寸和執行時間Fig.4 Graph partitioning size and execution time of SA under different thresholds

圖5 不同閾值下混合算法的圖切割尺寸和執行時間Fig.5 Graph partitioning size and execution time of hybrid algorithm under different thresholds

假定所有的應用程序組件都部署在云上，所有的服務器通過相同的鏈接互聯，因此，?m，n：bm，n=1。然而，在移動云計算背景下，用云可以把應用程序上的組件從移動設備上卸載到云上，其中用來將設備連接到互聯網的無線鏈路是一個重要的限制因素。依賴于技術和介于移動設備和云之間可使用的帶寬信號強度，最佳部署會改變。為計算這種情況下的最佳部署，可以通過無線鏈路嘗試限制交換數據的數量。

為計算在卸載場景中的最佳部署，在隨機生成的機器表中額外添加了1臺容量為25 G的機器D并鎖定這臺機器上的1個節點。機器之間的連接權重設置為1，對于每個服務器與D之間的連接要設置成α≥1。當α增加時，算法會計算出1個新的部署并嘗試降低無線鏈路的帶寬。

4 結論

1） 提出一種劃分軟件圖的混合算法，以實現在云中的部署。考慮到基礎設施的異質性，對最優劃分進行了計算。與計算網格部署最優化相反，未對一組網格結構任務的執行時間最小化，而是將軟件組件之間的帶寬最小化。

2） 提出多層次以KL為基礎的算法，這是一種快速分割器，可以實現實時部署計算。

3） 下一步可將這些方法融入到一個實際的軟件部署框架中，這樣可以對云基礎設施上的軟件組件進行自動分配。

［1］ 靳志成. 云計算環境下的軟件動態部署［D］. 上海： 上海交通大學電子信息與電氣工程學院， 2011： 1-8. JIN Zhicheng. Research on dynamic software deployment in cloud environment［D］. Shanghai： Shanghai Jiao Tong University. School of Electronics and Electric Engineering， 2011： 1-8.

［2］ 錢育蓉， 于炯， 王衛源， 等. 云計算環境下軟硬件節能和負載均衡策略［J］. 計算機應用， 2013， 33（12）： 3326-3330. QIAN Yurong， YU Jiong， WANG Weiyuan， et al. Energy saving and load balance strategy in cloud computing［J］. Journal of Computer Applications， 2013， 33（12）： 3326-3330.

［3］ MEYERHENKE H， MONIEN B， SCHAMBERGER S. Graph partitioning and disturbed diffusion［J］. Parallel Computing， 2009，35（10）： 544-569.

［4］ 黃樹成， 李甜， 沙愛暉. 一種基于圖劃分的混合屬性數據聚類算法［J］. 計算機應用與軟件， 2013， 30（7）： 11-13. HUANG Shucheng， LI Tian， SHA Aihui. A graph partition-based clustering algorithm for mixed attribute data［J］. Computer Applications and Software， 2013， 30（7）： 11-13.

［5］ FIDUCCIA C M， MATTHEYSES R M. A linear-time heuristic for improving network partitions［C］// Proceedings of the 19th Design Automation Conference. IEEE Press， 1982： 175-181.

［6］ VAHID F， LE T D. Extending the Kernighan/Lin heuristic for hardware and software functional partitioning［J］. Design Automation for Embedded Systems， 1997， 2（2）： 237-261.

［7］ CHARDAIRE P， BARAKE M， MCKEOWN G P. A probe-based heuristic for graph partitioning［J］. IEEE Transactions on Computers， 2007， 56（12）： 1707-1720.

［8］ ZAMPROGNO R， AMARAL A R S. An efficient approach for large scale graph partitioning［J］. Journal of Combinatorial Optimization， 2007， 13（4）： 289-320.

［9］ MARTIN J G. Spectral techniques for graph bisection in genetic algorithms［C］// Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. Washington， USA：ACM， 2006： 1249-1256.

［10］ CHEN J， TAYLOR V E. Mesh partitioning for efficient use of distributed systems［J］. IEEE Transactions on Parallel and Distributed Systems， 2002， 13（1）： 67-79.

［11］ HENDRICKSON B， LELAND R. A multilevel algorithm for partitioning graphs［C］// Proceedings of the 1995 ACM/IEEE conference on Supercomputing. California， USA： ACM， 1995：28-41.

［12］ KARYPIS G， KUMAR V. A parallel algorithm for multilevel graph partitioning and sparse matrix ordering［J］. Journal of Parallel and Distributed Computing， 1998， 48（1）： 71-95.

［13］ MIMAROGLU S， ERDIL E. Combining multiple clusterings using similarity graph［J］. Pattern Recognition， 2011， 44（3）：694-703.

［14］ 李冰鵬， 婁國哲. 一種軟件部署沖突檢測及其自動調整算法［J］. 計算機應用與軟件， 2011， 28（4）： 63-66. LI Bingpeng， LOU Guozhe. A software deployment algorithm of conflict detection and automatic adjustment［J］. Computer Applications and Software， 2011， 28（4）： 63-66.

［15］ 陳偉， 魏峻， 黃濤. W4H：一個面向軟件部署的技術分析框架［J］. 軟件學報， 2012， 23（7）： 1669-1687. CHEN Wei， WEI Jun， HUANG Tao. W4H： An analytical framework for software deployment technologies［J］. Journal of Software， 2012， 23（7）： 1669-1687.

［16］ KIRKPATRICK S， VECCHI M P. Optimization by simmulated annealing［J］. Science， 1983， 220（4598）： 671-680.

［17］ CERNY V. Thermodynamical approach to the traveling salesman problem： an efficient simulation algorithm［J］. Journal of Optimization Theory and Applications， 1985， 45（1）： 41-51.

［18］ JOHNSON D S， ARAGON C R， MCGEOCH L A， et al. Optimization by simulated annealing： an experimental evaluation；part I， graph partitioning［J］. Operations Research， 1989， 37（6）：865-892.

［19］ PARK M W， KIM Y D. A systematic procedure for setting parameters in simulated annealing algorithms［J］. Computers & Operations Research， 1998， 25（3）： 207-217.

［20］ EPPSTEIN D， WANG J. A steady state model for graph power laws［C］// Proceedings of the 2nd International Workshop on Web Dynamics. Hawaii， USA： ACM， 2002： 1-8.

（編輯 陳愛華）

Hybrid software deployment management algorithm based on multilevel graph partitioning in cloud environment

DAI Wei1，2， LIU Hua1

（1. School of Management， Huazhong University of Science and Technology， Wuhan 430074， China；2. School of Economics and Management， Hubei Polytechnic University， Huangshi 435003， China）

To allocate the software components to the appropriate cloud servers at the same time of minimizing the required bandwidth， a hybrid algorithm based on multi-layer graph partitioning algorithm was proposed for solving the software deployment issues in cloud computing environment. This algorithm improves the heavy-edge matching （HEM）algorithm， adds a new constraint for coarsening， conducts segmentation using the algorithm similar to KL， and finally achieves the re-design and assessment for graph partitioning algorithm in combination with annealing algorithm. Compared with traditional graph partitioning， the proposed algorithm takes into account the heterogeneity of the infrastructure， and so it is not limited to the balance partitioning. The simulation results of test show that compared with the traditional KL graph partitioning algorithm， the proposed hybrid algorithm can achieve a good balance between execution time and solution quality， and so its overall performance is better than that of the traditional algorithms.

cloud computing； graph partitioning algorithm； SA algorithm； software deployment

TP393.02

A

1672-7207（2016）05-1565-08

10.11817/j.issn.1672-7207.2016.05.016

2015-07-15；

2015-09-227

教育部人文社會科學研究青年基金資助項目（13YJCZH028） （Project（13YJCZH028） supported by Humanities and Social Sciences Youth Fund Project of Ministry of China）

戴偉，博士，副教授，從事云計算、數據挖掘和企業管理研究；電話：13971762521；E-mail： dweisky@163.com