劉素芹, 張 千, 王俊爽

(中國石油大學(xué)(華東) 計算機與通信工程學(xué)院, 青島 266580)

1 引言

集群資源進行調(diào)度成為影響集群性能的重要因素之一[1]. 文獻傳統(tǒng)的調(diào)度算法先來先服務(wù)算法(First Come First Serve, FCFS)等傳統(tǒng)的調(diào)度算法難以滿足大規(guī)模異構(gòu)集群對資源調(diào)度的需求[2–4], 尤其是負載均衡問題更為突出[5,6], 蟻群算法 (Ant Colony Optimization,ACO)等仿生型智能調(diào)度算法受到越來越多的關(guān)注.

國內(nèi)外學(xué)者對蟻群算法在集群調(diào)度中的應(yīng)用做了一定的研究[7,8], 認為其分布并行性、健壯性、可擴展性都比較適合于集群調(diào)度, 但是蟻群算法沒有充分考慮資源與作業(yè)的匹配度和負載均衡問題, 導(dǎo)致集群的整體性能不能得以充分發(fā)揮, 所以需要對蟻群算法深入研究并加以改進, 以進一步提高集群調(diào)度的性能.

2 蟻群算法及在集群調(diào)度中的應(yīng)用

2.1 蟻群算法原理

蟻群算法[8]是由意大利學(xué)者于1991年首先提出的一種具有群體智能的仿生優(yōu)化算法, 借鑒生物界中螞蟻在覓食過程中總能找到最短路徑的思想. 蟻群算法用螞蟻行走的路徑軌跡求解問題的最優(yōu)解, 螞蟻的每條路徑軌跡代表所求問題的一種解, 所有的螞蟻都在解空間中獨立地搜索, 當螞蟻在行進過程中遇見尚未經(jīng)過的路口時, 就從該路口延伸出的路徑中隨機地選擇一條尚未走過的路徑繼續(xù)前進, 同時釋放與該路徑長度有關(guān)的信息素增強該路徑的被選概率, 該路徑長度越短, 釋放的信息素就越多. 當后來的螞蟻再次經(jīng)過該路口時, 就選擇信息素濃度高的路徑, 同時釋放更多的信息素, 形成正反饋機制. 同時引入信息素揮發(fā)機制,避免殘留信息素太多使啟發(fā)信息失去參考價值的現(xiàn)象.蟻群算法的這種自催化行為不需要外界提供其他的信息, 應(yīng)用起來比較簡單, 現(xiàn)已在旅行商問題、組合優(yōu)化問題、二次分配問題等領(lǐng)域得到了良好的發(fā)展.

2.2 蟻群算法用于集群調(diào)度的策略

用蟻群算法解決集群調(diào)度問題的策略[9,10]為:

(1) 設(shè)組成蟻群的螞蟻數(shù)量為M, 每只螞蟻均可獨立求得一組作業(yè)調(diào)度方案.

(2) 集群系統(tǒng)初始化, 集群中所有節(jié)點都需提供自身的CPU個數(shù)及每個CPU的處理能力等參數(shù), 為每個節(jié)點設(shè)置初始信息素.

(3) 異構(gòu)集群系統(tǒng)中的管理節(jié)點在每個調(diào)度周期開始前就開始收集各節(jié)點的資源信息:

① 若有新節(jié)點加入集群, 就為這個新加入集群的節(jié)點根據(jù)它所提供的CPU個數(shù)及處理能力等參數(shù)設(shè)置初始信息素;

② 若集群中有節(jié)點因故障等原因掉線, 則將該掉線節(jié)點作停用標記;

③ 若集群中作停用標記的節(jié)點恢復(fù), 就重新為該節(jié)點設(shè)置啟用標志;

④ 集群中作業(yè)調(diào)度結(jié)束后, 依據(jù)作業(yè)的完成情況修改節(jié)點的信息素: 成功則獎勵, 失敗則懲罰.

(4) 螞蟻個體根據(jù)概率公式隨機選擇一個可用的計算節(jié)點作為第一個作業(yè)分配的節(jié)點, 并且依據(jù)信息素計算出轉(zhuǎn)移概率的大小, 按順序決定下一個作業(yè)分配的節(jié)點. 重復(fù)此步驟, 直到所有的作業(yè)分配完成.

(5) 調(diào)度策略的優(yōu)化目標是所有任務(wù)的總體執(zhí)行代價最小和系統(tǒng)資源的負載平衡性最優(yōu).

當一個螞蟻找到一種調(diào)度方案后, 就計算該調(diào)度方案的執(zhí)行時間和負載均衡性. 當所有螞蟻都找到調(diào)度方案后, 比較每個調(diào)度方案的執(zhí)行時間和負載均衡性, 并以此修改各相關(guān)路徑的信息素. 選擇任務(wù)完成時間最短和負載均衡性最優(yōu)的一組資源為最優(yōu)方案.

2.3 信息素更新帶來的問題

在蟻群算法中, 信息素的更新非常重要, 集群系統(tǒng)直接根據(jù)信息素更新后的大小決定下一個作業(yè)選擇該集群節(jié)點的概率. 蟻群算法的信息素更新公式如式(1)和式(2):

從公式(1)和公式(2)可以看到, 信息素的更新方式有時會帶來以下兩方面的問題:

(1) 作業(yè)需求與集群節(jié)點資源性能不匹配

從公式(2)中螞蟻根據(jù)作業(yè)完成情況釋放信息素可以看出, 作業(yè)成功完成, 就對該集群節(jié)點進行獎勵;作業(yè)完成失敗, 就對該集群節(jié)點進行懲罰. 但這種情況并沒有考慮作業(yè)需求和集群節(jié)點資源性能的匹配問題,很可能會出現(xiàn)小作業(yè)在大資源上執(zhí)行的這種“大炮打蚊子”式的性能不匹配的問題.

(2) 集群各節(jié)點之間負載不均衡

公式(1)中信息素揮發(fā)系數(shù)ρ通常是固定的常數(shù),也即各集群節(jié)點上的信息素揮發(fā)程度相同. 但集群各節(jié)點的性能不同, 作業(yè)又是隨機到達的, 系統(tǒng)運行一段時間后, 很可能會出現(xiàn)集群各節(jié)點之間負載不均衡的情況.

3 對蟻群算法的改進

針對信息素更新中存在的問題對蟻群算法進行改進, 稱之為該進型蟻群算法 (Improved ACO, IACO)算法, 這種改進包括兩個方面: 一方面引入性能匹配因子提高性能匹配度, 把這種算法稱為 P M-A C O(Performance Matching-ACO); 另一方面引入負載均衡因子優(yōu)化負載均衡, 把這種算法稱為LB-ACO (Load Balance-ACO).

3.1 PM-ACO算法

為了使得分配的資源和作業(yè)的需求更好的匹配,達到物盡其用, 從而更好的發(fā)揮集群的整體性能, 進行資源調(diào)度時, 根據(jù)作業(yè)的需求計算每個作業(yè)到各個集群節(jié)點的匹配程度, 引入性能匹配因子 λij. λij即用戶作業(yè)i所需資源與集群空閑節(jié)點j擁有資源的匹配度.

其中,realExetime表示作業(yè)的實際運行時間,estimatedTime表示作業(yè)的預(yù)期運行時間, 作業(yè)對資源的需求與集群節(jié)點所擁有資源越接近, 性能匹配因子λij也就越小.

引入性能匹配因子后, 螞蟻根據(jù)作業(yè)完成情況釋放信息素的公式(4)和公式(5)如下:

其中,λij為性能匹配因子,λ0為匹配度閾值為信息素增量,c為獎勵因子或懲罰因子,k為所需計算資源.

當作業(yè)在資源節(jié)點上執(zhí)行完成后, 計算作業(yè)與該集群節(jié)點的性能匹配因子λij的值, 并把λij的值與匹配度閾值作比較. 如果λij的值小于匹配度閾值, 信息素調(diào)節(jié)因子就取獎勵因子, 增大該資源節(jié)點的信息素濃度,使得此資源節(jié)點被選中的概率增大. 如果λij的值大于匹配度閾值, 信息素調(diào)節(jié)因子就取懲罰因子, 減小資源節(jié)點的信息素濃度, 使得此資源節(jié)點被選中的概率降低. 這樣, 對于資源處理能力需求小的作業(yè)就可能選擇更匹配的處理能力低的集群節(jié)點. 隊列后面對資源處理能力需求大的作業(yè)也就會到處理能力高的集群節(jié)點上去執(zhí)行, 從而較好地解決了資源與作業(yè)不匹配的問題.

3.2 LB-ACO算法

在蟻群算法中, 揮發(fā)系數(shù)的大小直接影響著算法的收斂速度. 揮發(fā)系數(shù)較小時, 計算節(jié)點的信息素較大,算法收斂的也較快. 為了滿足蟻群算法作業(yè)調(diào)度中負載均衡的要求, 系統(tǒng)需要不斷的檢測計算節(jié)點的負載及其作業(yè)完成情況. 為了保證負載均衡, 我們需要把各計算節(jié)點負載完成率的差值控制在一個較小的閾值之內(nèi). 為了動態(tài)的調(diào)整蟻群算法的揮發(fā)系數(shù), 提高負載均衡性能, 引入負載均衡因子, 表達如公式(6)所示:

其中,Ta表示計算節(jié)點成功完成的任務(wù)數(shù),Tf表示該計算節(jié)點已經(jīng)接收的所有任務(wù)總數(shù).Tf一定時,Ta越大,計算節(jié)點成功完成的任務(wù)數(shù)越多,ωi也越小, 表明計算節(jié)點的作業(yè)完成率越高;Ta越小, 計算節(jié)點成功完成的任務(wù)數(shù)越少,ωi也就越大, 表明計算節(jié)點的作業(yè)完成率越低.

引入負載均衡因子后, 集群節(jié)點殘留信息素改變?nèi)绻?7)所示:

其中,ω0為負載均衡因子的初始閾值.

在為作業(yè)選擇集群節(jié)點時, 需要計算該集群節(jié)點的負載均衡因子ωi的值, 并將ωi的值與初始閾值ω0作比較. 若ωi小于初始閾值時, 應(yīng)該減小揮發(fā)系數(shù),增大集群節(jié)點的信息素值, 使該集群節(jié)點被選概率增大, 作業(yè)分配收斂于此資源節(jié)點; 反之, 若ωi大于初始閾值時, 應(yīng)該增大揮發(fā)系數(shù), 減小計算節(jié)點的信息素值,使該集群節(jié)點被選概率降低, 使算法的全局搜索能力增強, 以便找到更加匹配的資源.

3.3 IACO用于集群調(diào)度的實現(xiàn)方案

改進后的蟻群算法應(yīng)用于異構(gòu)集群系統(tǒng)進行資源調(diào)度的實現(xiàn)方案如圖1所示.

圖1 IACO 用于集群調(diào)度的實現(xiàn)方案

調(diào)度開始前, 異構(gòu)集群系統(tǒng)中的管理節(jié)點就開始收集各節(jié)點的資源信息素信息. 若有新節(jié)點加入, 則對該節(jié)點進行初始化. 集群系統(tǒng)對每組作業(yè)調(diào)度時, 都需要創(chuàng)建一個新的蟻群. 蟻群中的每個螞蟻找到一種調(diào)度方案后, 就計算該調(diào)度方案的執(zhí)行時間和負載均衡性. 當所有螞蟻都找到調(diào)度方案后, 比較每個調(diào)度方案的執(zhí)行時間和負載均衡性, 并以此修改各相關(guān)路徑的信息素. 選擇任務(wù)完成時間最短和負載均衡性最高的一組資源為最優(yōu)方案.

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

為了對改進的蟻群算法在集群調(diào)度中的應(yīng)用效果進行測試, 在100個節(jié)點的異構(gòu)集群上對真實的地震資料進行處理, 調(diào)度算法分別采用先來先服務(wù)算法FCFS、蟻群算法ACO、引入性能匹配因子的PMACO算法、引入負載均衡因子的LB-ACO算法和最終改進的蟻群算法IACO, 主要對處理時間和CPU平均利用率進行對比, 實驗結(jié)果如圖2和圖3所示.

圖2 處理時間比較

圖3 各節(jié)點 CPU 平均利用率對比

從實驗結(jié)果可以看出, 蟻群算法ACO考慮到資源和作業(yè)的實際情況, 比傳統(tǒng)的先來先服務(wù)算法FCFS有明顯的優(yōu)勢; 引入性能匹配因子后的PMACO算法解決了“大炮打蚊子”的問題, 使得性能有所改進, 但負載均衡問題沒有解決; LB-ACO算法考慮了負載均衡問題, 但還有可能存在“大炮打蚊子”現(xiàn)象;IACO較好地解決了這兩方面的問題, 不論是處理時間還是CPU利用率均有明顯提高.

由此可見, 傳統(tǒng)的蟻群算法應(yīng)用于集群調(diào)度時確實存在資源匹配和負載均衡的問題, 在這兩個方面進行改進后能夠較好地提高集群的調(diào)度性能.

5 結(jié)論

傳統(tǒng)調(diào)度算法已經(jīng)難以滿足大規(guī)模異構(gòu)集群的作業(yè)的調(diào)度, 蟻群算法比較適合于集群中的作業(yè)調(diào)度, 但是, 傳統(tǒng)的蟻群算法在作業(yè)匹配和負載均衡方面還存在問題, 改進的蟻群算法IACO較好地解決了這一問題, 有效地提高了集群調(diào)度的性能.