蔣卓材 藍(lán)永勝 顏亮
(桂林航天工業(yè)學(xué)院 網(wǎng)絡(luò)與信息化管理中心,廣西 桂林 541004)
隨著計(jì)算機(jī)軟硬件和網(wǎng)絡(luò)技術(shù)的快速發(fā)展,計(jì)算模式由分散式的計(jì)算模式,發(fā)展到利用網(wǎng)絡(luò)技術(shù)將獨(dú)立的計(jì)算資源相互連接,協(xié)同完成指定任務(wù)的網(wǎng)絡(luò)計(jì)算模式,很多計(jì)算模式相繼被提出,包括網(wǎng)格計(jì)算、自主計(jì)算、透明計(jì)算和云計(jì)算等[1]。由于互聯(lián)網(wǎng)和5G技術(shù)的快速發(fā)展和部署,云計(jì)算服務(wù)吸引了人們的廣泛關(guān)注并在不同場合中大范圍應(yīng)用。云計(jì)算采用虛擬化技術(shù)對(duì)網(wǎng)格計(jì)算、并行計(jì)算和分布式系統(tǒng)進(jìn)行了改進(jìn)和提升[2],云計(jì)算將數(shù)據(jù)和計(jì)算遷移到異構(gòu)的計(jì)算資源中,并通過虛擬化的技術(shù)將虛擬服務(wù)器對(duì)外統(tǒng)一為一個(gè)計(jì)算資源池,用戶通過較低的成本購買計(jì)算服務(wù),降低了用戶的物理資源的投入和維護(hù),提高了資源的可用性和靈活性,同時(shí)降低了用戶成本。
任務(wù)調(diào)度是云計(jì)算中的一個(gè)關(guān)鍵環(huán)節(jié),通過云計(jì)算調(diào)度平臺(tái)將計(jì)算任務(wù)分解成若干個(gè)彼此相互聯(lián)系的子任務(wù)。資源調(diào)度平臺(tái)按照一定的調(diào)度策略,比如遺傳算法、模擬退火算法等調(diào)度策略把各個(gè)子任務(wù)分配到云計(jì)算虛擬節(jié)點(diǎn)上計(jì)算,如何選擇和設(shè)計(jì)一種高效調(diào)度策略達(dá)到完成時(shí)間最短,成本最小,系統(tǒng)利用率提升等目的成為云計(jì)算研究的重點(diǎn)之一。
云計(jì)算的任務(wù)調(diào)度問題實(shí)質(zhì)是一類NP問題,但云計(jì)算各個(gè)子任務(wù)之間有很強(qiáng)的相關(guān)性和并行性,近年來一些啟發(fā)式算法和智能算法,如遺傳、蟻群等算法運(yùn)用到云計(jì)算領(lǐng)域,設(shè)計(jì)云計(jì)算調(diào)度系統(tǒng)要充分考慮云計(jì)算資源的環(huán)境限制,云計(jì)算環(huán)境比傳統(tǒng)分布式計(jì)算環(huán)境復(fù)雜得多, 針對(duì)云計(jì)算任務(wù)調(diào)度特點(diǎn)合理設(shè)計(jì)任務(wù)調(diào)度策略和調(diào)度算法,合理分配和遷移到相應(yīng)資源上執(zhí)行,對(duì)提高云計(jì)算平臺(tái)的計(jì)算有效性和實(shí)用性都具有十分重要的意義。
資源的虛擬化、分布式和動(dòng)態(tài)擴(kuò)展是云計(jì)算的幾個(gè)主要特點(diǎn)。云計(jì)算平臺(tái)的主要結(jié)構(gòu)如圖1所示。用戶通過特定的入口訪問云計(jì)算平臺(tái),云計(jì)算平臺(tái)前端模塊分解用戶任務(wù),生成子任務(wù),并根據(jù)相關(guān)參數(shù),按照一定的調(diào)度策略把相關(guān)子任務(wù)分解到各個(gè)計(jì)算子節(jié)點(diǎn)進(jìn)行運(yùn)行,最終在子任務(wù)完成后匯總結(jié)果,并將結(jié)果返回給用戶。云計(jì)算平臺(tái)在系統(tǒng)運(yùn)行過程中通過任務(wù)調(diào)度、資源優(yōu)化分配、軟硬件監(jiān)控和故障維護(hù)等方式保證任務(wù)和平臺(tái)的穩(wěn)定運(yùn)行。
圖1 云計(jì)算主要架構(gòu)
云計(jì)算任務(wù)調(diào)度即為工作流調(diào)度問題,與傳統(tǒng)的獨(dú)立任務(wù)的并行執(zhí)行不同,云計(jì)算各個(gè)子任務(wù)之間具有約束與依賴性,其調(diào)度本質(zhì)就是把并行程序的一組相關(guān)任務(wù)按照一定調(diào)度策略分配到云資源計(jì)算節(jié)點(diǎn)上進(jìn)行處理,并安排好每個(gè)計(jì)算節(jié)點(diǎn)上的執(zhí)行順序,滿足用戶對(duì)任務(wù)執(zhí)行時(shí)間上的相關(guān)QoS約束,并獲得較好的計(jì)算性能。在云計(jì)算環(huán)境中的任務(wù)調(diào)度是一類相互之間存在通信和并且相互關(guān)聯(lián)的任務(wù)調(diào)度,對(duì)此類問題,本文采用有向無環(huán)圖(DAG圖)進(jìn)行數(shù)學(xué)建模,圖2中所示的9個(gè)任務(wù)的DAG圖,每個(gè)子任務(wù)用一個(gè)圓圈表示,箭頭表示子任務(wù)之間的通信、先后順序、網(wǎng)絡(luò)通信開銷和約束關(guān)系,只有前驅(qū)節(jié)點(diǎn)完成后,后繼節(jié)點(diǎn)才能執(zhí)行。通過高效的調(diào)度策略合理調(diào)度到每個(gè)計(jì)算節(jié)點(diǎn)上,實(shí)現(xiàn)總執(zhí)行時(shí)間最少。
圖2 9個(gè)子任務(wù)的DAG圖
云計(jì)算平臺(tái)的任務(wù)分解模塊會(huì)按策略將大型任務(wù)分解為若干子任務(wù),子任務(wù)之間符合任務(wù)運(yùn)行邏輯,子任務(wù)通過DAG進(jìn)行數(shù)學(xué)建模,有效的表達(dá)子任務(wù)之間的先后關(guān)系和數(shù)據(jù)依賴關(guān)系。分析DAG圖的任務(wù)之間的通信量、優(yōu)先關(guān)系和云計(jì)算環(huán)境下各個(gè)節(jié)點(diǎn)的計(jì)算能力和相互之間的通信成本,將云計(jì)算任務(wù)調(diào)度問題的數(shù)學(xué)模型(Cloud Computing Task Scheduling Model)定義為CTSM=(M,LC,L,Q,E,C)其中M表示云計(jì)算資源節(jié)點(diǎn)集合,L表示調(diào)度子任務(wù)集合,LC表示子任務(wù)計(jì)算成本集合,Q[n,n]表示約束關(guān)系矩陣,Qij表示任務(wù)Li和任務(wù)Lj相互之間約束關(guān)系,任務(wù)Li是任務(wù)Lj的前驅(qū),只有任務(wù)Li完成任務(wù)Lj才能執(zhí)行。E是個(gè)云計(jì)算節(jié)點(diǎn)的處理能力集合。C(Li,Lj)為通信成本矩陣,表示任務(wù)Li到任務(wù)Lj的通信成本?;谠朴?jì)算的DAG圖任務(wù)調(diào)度數(shù)學(xué)模型采用DAG圖的深度遍歷策略算法,計(jì)算每個(gè)子任務(wù)在計(jì)算序列中的深度值,從而獲取DAG圖子任務(wù)之間的約束和先后關(guān)系,滿足子任務(wù)之具有的相關(guān)制約和先后執(zhí)行順序。
云計(jì)算數(shù)學(xué)建模對(duì)DAG圖采用深度遍歷策略其深度值為
(1)
通過深度值計(jì)算,獲取子任務(wù)約束和先后關(guān)系,構(gòu)建計(jì)算節(jié)點(diǎn)和資源關(guān)系矩陣“MLm×n”,m為計(jì)算資源數(shù)量,其中n為深度值。
通過高效合理的調(diào)度策略,在滿足計(jì)算節(jié)點(diǎn)和資源關(guān)系矩陣MLm×n,考慮節(jié)點(diǎn)計(jì)算能力和網(wǎng)絡(luò)開銷等綜合因素的前提下,使得完成任務(wù)時(shí)間最少。
基于云計(jì)算機(jī)DAG圖T(S)計(jì)算模型如
(2)
(3)
因此基于DAG圖的云計(jì)算任務(wù)調(diào)度數(shù)學(xué)模型可以構(gòu)建為min{T(S)},其中
T(S)=max{FT(l,m)|l∈L,m∈M}。
(4)
遺傳算法(Genetic Algorithm)是模擬達(dá)爾文生物進(jìn)化的自然選擇和遺傳的特點(diǎn),通過數(shù)學(xué)建模的方法自然搜索尋找最優(yōu)解的算法[3]。算法從最初一個(gè)種群開始,通過度量函數(shù),對(duì)個(gè)體進(jìn)行編碼(編碼后的個(gè)體變量又稱為染色體)和適應(yīng)度評(píng)價(jià)計(jì)算,不同的個(gè)體構(gòu)成一個(gè)種群,通過遺傳算法進(jìn)行運(yùn)算,對(duì)染色體進(jìn)行重組、變異,產(chǎn)生新的染色體,通過不斷的選擇、交叉和變異等迭代運(yùn)算,在種群中找到相對(duì)最優(yōu)解。GA算法具有較強(qiáng)的全局搜索性能,可以整個(gè)群體空間進(jìn)行搜索。并且算法具有并行性的特點(diǎn),適合用在云環(huán)境下DAG數(shù)學(xué)模型環(huán)境下的任務(wù)調(diào)度,所以把GA算法引入云計(jì)算任務(wù)調(diào)度,作為任務(wù)調(diào)度的基礎(chǔ)性算法。
遺傳算法從問題解的解集開始搜索,區(qū)別于傳統(tǒng)算法從單個(gè)初始值開始迭代求解,因此具有很強(qiáng)的全局搜索能力,但同時(shí)容易出現(xiàn)早收斂,而達(dá)不到全局最優(yōu)。
粒子群(PSO)算法模擬動(dòng)物覓食行為特征的群體智能全局隨機(jī)搜索算法,在算法中單個(gè)動(dòng)物視為一個(gè)粒子,每一個(gè)粒子由速度決定他的方向和位置,并同最優(yōu)粒子進(jìn)行對(duì)比,通過不斷迭代計(jì)算,而在種群中找到最優(yōu)解[4]。GA算法具有很好的全局和局部搜索能力,但易產(chǎn)生早熟收斂情況,且搜索效率低、收斂慢[5],粒子群算法搜索效率高,但算法不穩(wěn)定容易陷入局部最優(yōu),結(jié)合二者優(yōu)點(diǎn),將粒子群算法和思想引入遺傳算法中,如圖3所示,將粒子群搜索作為遺傳算法的變異算子[6]。
把粒子群算法作用于變異的過程,其實(shí)是有條件的打破遺傳算法的局部最優(yōu)解的過程。對(duì)選擇的個(gè)體進(jìn)行變異,完成一次全局的尋優(yōu),重新生成新的染色體個(gè)體,更新種群的基因信息,有條件的接受新個(gè)體解,從而是種群引入新個(gè)體的過程。算法保持了群體的多樣性,計(jì)算過程中爬山能力增強(qiáng)有效地避免了早熟現(xiàn)象。
圖3 基于遺傳粒子群算法的混合策略圖
算法根據(jù)云計(jì)算數(shù)學(xué)模型,先通過等深度DAG算法分解成資源與任務(wù)關(guān)系矩陣,采用二維二進(jìn)制染色體編碼機(jī)制對(duì)染色體進(jìn)行編碼,編碼體現(xiàn)了云計(jì)算任務(wù)調(diào)度的邏輯合法性,然后通過遺傳粒子群算法對(duì)種群進(jìn)行全局尋優(yōu)生成新種群,并通過不斷迭代運(yùn)算,輸出最優(yōu)調(diào)度解。
3.2.1 染色體編碼設(shè)計(jì)
染色體的編碼方式有很多種,本文根據(jù)云計(jì)算DAG任務(wù)調(diào)度的特點(diǎn)采用二進(jìn)制矩陣直接編碼的方式定義二維矩陣“資源-任務(wù)”矩陣MLm×n來描述染色體編碼結(jié)構(gòu)。矩陣中的每一基因列表示被調(diào)度任務(wù)和資源節(jié)點(diǎn)之間的映射關(guān)系,通過二維二進(jìn)制矩陣表示一個(gè)合法的云計(jì)算DAG任務(wù)調(diào)度序列,也是任務(wù)調(diào)度的一個(gè)合法解。
以圖2中的DAG圖為例,假設(shè)計(jì)算資源節(jié)點(diǎn)數(shù)為4,可以產(chǎn)生多個(gè)二維染色體矩陣,例如圖4為一個(gè)染色體編碼矩陣結(jié)構(gòu):
圖4 資源和任務(wù)調(diào)度染色體編碼矩陣
3.2.2 遺傳算法的選擇算子和交叉算子設(shè)計(jì)
本文通過輪盤選擇算子,既按一定比例保留適應(yīng)度函數(shù)結(jié)果中最優(yōu)解,從而保存下一代群體的優(yōu)良個(gè)體解不丟失,染色體s被選中的概率為
(5)
通過上面選擇算子可以看出,適應(yīng)度值越高,在種群中被選擇的概率越高,從而在進(jìn)化過程中,使得優(yōu)秀的遺傳基因得以保留,又可以容納部分劣解,從而保持遺傳的多樣性和隨機(jī)性。
根據(jù)云計(jì)算DAG任務(wù)調(diào)度的特點(diǎn)設(shè)計(jì)交叉算子,云計(jì)算子任務(wù)之間有較強(qiáng)的相互依賴關(guān)系,設(shè)計(jì)交叉算子不能破壞二維矩陣“資源-任務(wù)”矩陣MLm×n之間的約束關(guān)系,本文采用不同個(gè)體染色體二維矩陣列等深度交換運(yùn)算的策略進(jìn)行交叉運(yùn)行,交換不同染色體的等深度基因從而形成新的染色體個(gè)體,保留MLm×n的約束關(guān)系,新生成的染色體矩陣為一個(gè)合法的DAG任務(wù)調(diào)度解。
3.2.3 遺傳算法變異算子的優(yōu)化策略
(6)
式中:由于云計(jì)算DAG任務(wù)調(diào)度具有相互約束性,變異過程遷移不同列等深度的基因,保證變異后的染色體個(gè)體為合法調(diào)度序列,w是慣性因子;c1、c2為加速系數(shù),合理設(shè)計(jì)取值范圍可以加快收斂但又不陷入局部最優(yōu)[7]。rand為介于[0,1]之間的隨機(jī)數(shù)。為了解決粒子群在種群空間的搜索力度,每個(gè)粒子的速度被限制在±Vmax范圍內(nèi)。
3.2.4 云計(jì)算環(huán)境下基于遺傳粒子群算法的DAG任務(wù)調(diào)度算法設(shè)計(jì)
下面給出混合遺傳和粒子群優(yōu)化算法的設(shè)計(jì)過程。
步驟1:初始化算法的基本參數(shù),包括GA算法的種群數(shù)量N、選擇算子、交叉算子等,并初始化PSO算法的粒子群變異概率、權(quán)重w、c1和c2因子等參數(shù)。
步驟2:染色體的編碼形式采用二維矩陣RLm×n編碼方式, 每個(gè)染色體就是一個(gè)合法的DAG任務(wù)調(diào)度解。令t=0,k=0。
步驟3:根據(jù)DAG圖采用深度遍歷策略初始化種群, 其中有N個(gè)個(gè)體:s1t,s2t,...,sNt。
步驟4:計(jì)算染色體群體中每個(gè)個(gè)體的適應(yīng)值f(s1t),f(s2t)...f(sNt)。
步驟5:選擇算子通過概率PRi公式:
通過公式可以看出,在整個(gè)種群中個(gè)體的適應(yīng)度值的占比越大,越可能被選擇參與迭代尋優(yōu)。
步驟6:對(duì)被選擇的個(gè)體根據(jù)交叉概率,進(jìn)行二維二進(jìn)制矩陣交叉運(yùn)算。
步驟7:粒子群的變異計(jì)算 。
步驟7.1:生成0~1之間的隨機(jī)數(shù)randi,i=1,2...,N, 如果有randi
步驟7.3:將變異后的染色體個(gè)體納入種群中。
步驟8:如果t
步驟9:染色體解碼,輸出最優(yōu)解,終止算法。
根據(jù)云計(jì)算任務(wù)調(diào)度的特點(diǎn),選擇CloudStack工具進(jìn)行試驗(yàn)平臺(tái)搭建,CloudStack是具有開源、高可用性和擴(kuò)展性的一個(gè)開源云計(jì)算解決方案[8]。為了驗(yàn)證算法有效性,對(duì)比遺傳算法和本算法進(jìn)行仿真結(jié)果比較,本文采用40、80、160個(gè)不同輕重負(fù)載子任務(wù)根據(jù)DAG圖進(jìn)行任務(wù)調(diào)度。最大的迭代進(jìn)化代數(shù)設(shè)計(jì)為400次。模擬實(shí)驗(yàn)輸出對(duì)比結(jié)果如表1。
表1 仿真實(shí)驗(yàn)數(shù)據(jù)結(jié)果
表1為不同負(fù)載和計(jì)算資源節(jié)點(diǎn)下完成時(shí)間和找到最優(yōu)解的迭代次數(shù),從試驗(yàn)數(shù)據(jù)可以看出:
①當(dāng)任務(wù)個(gè)數(shù)固定時(shí),隨著計(jì)算資源個(gè)數(shù)的增加,云計(jì)算完成計(jì)算任務(wù)的時(shí)間和收斂時(shí)的進(jìn)化代數(shù)成下降趨勢,而得到最優(yōu)解的最大進(jìn)化代數(shù)也提前。
②當(dāng)計(jì)算資源個(gè)數(shù)固定,隨著任務(wù)個(gè)數(shù)的增加,云計(jì)算完成計(jì)算任務(wù)的時(shí)間呈上升趨勢,當(dāng)子任務(wù)個(gè)數(shù)成倍增加,完成時(shí)間和收斂進(jìn)化代數(shù)并不成倍增加,體現(xiàn)了算法的優(yōu)化過程。
③通過模擬仿真結(jié)果可以看出,優(yōu)化后的算法在完成時(shí)間和收斂時(shí)的進(jìn)化代數(shù)上都有明顯的提升和優(yōu)化。
④從算法性能對(duì)比可以看出,優(yōu)化后的算法對(duì)比原遺傳算法能在較短的進(jìn)化代數(shù)上接近最優(yōu)解,并且在較少的計(jì)算時(shí)間上接近最優(yōu)解。
分析優(yōu)化后的算法在性能上有明顯提升的原因,在于GA算法具有的高效全局和局部搜索能力,但同時(shí)GA算法在搜索計(jì)算過程中,容易出現(xiàn)染色體種群中某個(gè)個(gè)體適應(yīng)值過大,造成個(gè)體適應(yīng)值大大超過了種群的平均適應(yīng)值, GA算法選擇算子無法選擇其他染色體,導(dǎo)致種群多樣性降低,使得算法過早收斂,無法輸出最優(yōu)解。為了解決早熟收斂的問題,利用PSO算法搜索效率高,容易找到局部最優(yōu)解的特點(diǎn),引入PSO作為變異算子有條件的接受劣解,在染色體種群中保持染色體的多樣性,一定程度上減少GA算法本身容易出現(xiàn)的早熟收斂情況,使得優(yōu)化后的GA算法有效提高了云計(jì)算的任務(wù)調(diào)度性能。
通過實(shí)驗(yàn)可以看出,云計(jì)算環(huán)境下基于遺傳粒子群算法的DAG任務(wù)調(diào)度算法優(yōu)化后算法相較于原遺傳算法在完成時(shí)間和收斂后的迭代數(shù)量上有明顯的優(yōu)勢,在遺傳算法中,根據(jù)云計(jì)算DAG任務(wù)調(diào)度的特點(diǎn),使用粒子群算法作為變異過程的基礎(chǔ)性算法,有限度的接受不同基因的合法解,跳出GA算法的早熟收斂,并有效克服粒子群算法易陷入局部最優(yōu)的問題。
現(xiàn)實(shí)的云計(jì)算環(huán)境中,很多虛擬云計(jì)算節(jié)點(diǎn)因?yàn)榫W(wǎng)絡(luò)問題或者虛擬資源問題存在退出計(jì)算資源池的情況,就需要實(shí)時(shí)監(jiān)控云計(jì)算虛擬計(jì)算節(jié)點(diǎn)的狀態(tài)信息,進(jìn)行動(dòng)態(tài)任務(wù)再調(diào)度。本文只可考慮了靜態(tài)負(fù)載的調(diào)度,資源的動(dòng)態(tài)調(diào)度是將進(jìn)一步研究的方向。
桂林航天工業(yè)學(xué)院學(xué)報(bào)2020年1期