一種提高集群調度性能的改進型蟻群算法①

劉素芹, 張 千, 王俊爽

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

1 引言

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

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

2 蟻群算法及在集群調度中的應用

2.1 蟻群算法原理

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

2.2 蟻群算法用于集群調度的策略

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

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

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

(3) 異構集群系統中的管理節點在每個調度周期開始前就開始收集各節點的資源信息:

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

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

③ 若集群中作停用標記的節點恢復, 就重新為該節點設置啟用標志;

④ 集群中作業調度結束后, 依據作業的完成情況修改節點的信息素: 成功則獎勵, 失敗則懲罰.

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

(5) 調度策略的優化目標是所有任務的總體執行代價最小和系統資源的負載平衡性最優.

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

2.3 信息素更新帶來的問題

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

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

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

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

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

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

3 對蟻群算法的改進

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

3.1 PM-ACO算法

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

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

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

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

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

3.2 LB-ACO算法

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

其中,Ta表示計算節點成功完成的任務數,Tf表示該計算節點已經接收的所有任務總數.Tf一定時,Ta越大,計算節點成功完成的任務數越多,ωi也越小, 表明計算節點的作業完成率越高;Ta越小, 計算節點成功完成的任務數越少,ωi也就越大, 表明計算節點的作業完成率越低.

引入負載均衡因子后, 集群節點殘留信息素改變如公式(7)所示:

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

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

3.3 IACO用于集群調度的實現方案

改進后的蟻群算法應用于異構集群系統進行資源調度的實現方案如圖1所示.

圖1 IACO 用于集群調度的實現方案

調度開始前, 異構集群系統中的管理節點就開始收集各節點的資源信息素信息. 若有新節點加入, 則對該節點進行初始化. 集群系統對每組作業調度時, 都需要創建一個新的蟻群. 蟻群中的每個螞蟻找到一種調度方案后, 就計算該調度方案的執行時間和負載均衡性. 當所有螞蟻都找到調度方案后, 比較每個調度方案的執行時間和負載均衡性, 并以此修改各相關路徑的信息素. 選擇任務完成時間最短和負載均衡性最高的一組資源為最優方案.

4 實驗結果及分析

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

圖2 處理時間比較

圖3 各節點 CPU 平均利用率對比

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

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

5 結論

傳統調度算法已經難以滿足大規模異構集群的作業的調度, 蟻群算法比較適合于集群中的作業調度, 但是, 傳統的蟻群算法在作業匹配和負載均衡方面還存在問題, 改進的蟻群算法IACO較好地解決了這一問題, 有效地提高了集群調度的性能.