劉素芹, 王 婧, 李興盛, 碩 珺, 劉會會

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

基于粒子群優(yōu)化算法的集群調度策略

劉素芹, 王 婧, 李興盛, 碩 珺, 劉會會

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

針對集群調度問題的特點,設計了基于粒子群優(yōu)化算法的調度策略.與傳統(tǒng)backfill算法相比,粒子群優(yōu)化算法對作業(yè)比較公平,能避免對大作業(yè)響應慢的缺點,使得調度策略在生成速度和精度上都有明顯的提高.實驗結果表明,該調度策略能較好地提高CPU利用率和縮短作業(yè)平均響應時間.

集群;作業(yè)調度;backfill算法;PSO算法

0 引言

粒子群優(yōu)化(particle swarm op timization,PSO)算法是一種模仿鳥群社會行為的智能優(yōu)化算法,具有并行性、有效的全局/局部搜索平衡能力、計算簡單、魯棒性好等優(yōu)點,已經在函數優(yōu)化、神經網絡訓練、模糊系統(tǒng)控制等領域得以應用,并進行了不斷的改進[1].PSO算法已在并行多機調度中得到十分有效的應用,但在集群調度中的應用研究較少,集群和并行機的調度問題十分類似,把PSO算法應用在集群調度中有十分重要的意義.本文通過分析集群調度策略的原理、研究現狀以及PSO算法的原理,設計并實現了基于粒子群優(yōu)化算法的集群調度策略,取得了較好的效果.

1 集群調度策略

集群系統(tǒng)的主要目標是通過高效的資源管理和作業(yè)調度技術實現資源的有效共享,提高系統(tǒng)資源利用率,獲得高性能,因此作業(yè)調度技術是實現資源共享和提高計算效率的有效途徑.

圖1 集群作業(yè)調度模型Fig.1 Scheduling model of cluster

集群作業(yè)調度模型如圖1所示.在集群作業(yè)調度模型中,(M1,M2,…,Mn)是一組待處理的模塊或子任務, (P1,P2,…,Pm)是系統(tǒng)的m個處理機或節(jié)點機,它們通過網絡相互通信,調度機制S通過一定的策略把n個模塊或子任務合理地分配給m個處理機.集群作業(yè)調度是實際生產過程中的一類典型調度問題,以最大完成時間最小為優(yōu)化目標的集群作業(yè)調度問題已經被證明是NP完全問題[2].

2 PSO算法分析

PSO算法是一種基于迭代的優(yōu)化算法.其基本思想是:通過對個體最優(yōu)和全局最優(yōu)粒子的記憶,實現群體信息的共享和個體之間經驗和發(fā)現的交互學習,進而通過速度-位置模型來實現這種共享和學習,使得種群中的所有粒子快速向最優(yōu)解移動.

PSO算法的基本原理是:算法中每個粒子都是解空間(D維)的一點,并且都具有一個速度,不同粒子具有對應于目標函數的個體適應度.每個粒子根據自身的飛行經驗和群體的飛行經驗來調整自己的飛行軌跡,向最優(yōu)點靠攏.在每一步中,粒子根據式(1),(2)更新自己的位置.

其中,ω為慣性權重;random()為(0,1)之間的隨機數;c1和c2為學習因子,合適的學習因子可以加快收斂并且不易陷入局部最優(yōu);pi為當前粒子群中的個體最優(yōu)粒子;向量g為全局最優(yōu)粒子.粒子在每一維飛行的速度不能超過算法設定的最大值vmax.

PSO算法在優(yōu)化結果和收斂速度方面均要優(yōu)于遺傳算法[3].用PSO算法求解作業(yè)調度問題,尋找問題解和算法中微粒間的恰當映射,使得所有處理器的最大處理時間為最小.在解決作業(yè)調度問題中,PSO算法是一種有效的選擇.

3 基于PSO算法的調度策略的設計

本文設計了基于PSO算法的調度策略.PSO算法操作的基本對象是粒子或個體,每個粒子代表求解問題的一個可能解.在應用PSO算法時,需要確定以下要素:①粒子的編碼方法,即如何由粒子的編碼體現問題的解;②選取適當的適應度函數或者目標函數來計算適應值,適應值是唯一能夠反映并引導優(yōu)化過程不斷進行的參量;③針對不同的算法模型,選擇適當的控制參數,直接影響算法的優(yōu)化性能;④選擇粒子群模型;⑤確定算法的終止準則.

3.1 粒子的編碼方式

在利用PSO算法求解問題時,其關鍵步驟是將問題的解從解空間映射到具有某種結構的表示空間,即用什么樣的粒子表示方式來表達所求解問題的解空間.文獻[3]中提出了3種間接表示調度問題解的粒子表示方法,根據集群調度問題的特點,本文采用基于粒子位置取整操作的表示方法.

定義一個二維粒子,二維粒子中的第一維用自然數1,2,…,n表示n個作業(yè),第二維表示粒子的位置,即所選擇的節(jié)點資源的位置,粒子的長度為所有作業(yè)的數量.對于粒子種群中第i個二維粒子xi的一個向量可以表示為:,j=1,2,…,n,xij∈[1,m+1)是一個隨機實數,m為資源節(jié)點的數量,用自然數1,2,…, m表示不同的資源節(jié)點.

3.2 確定適應度函數

作業(yè)調度的目標為調度的最大完成時間(makespan)最小[4].對于n個作業(yè)、m個資源節(jié)點的集群調度問題,用Tj表示作業(yè)j的執(zhí)行時間,Wj表示執(zhí)行過程中該作業(yè)等待執(zhí)行的時間,Ej表示該作業(yè)的執(zhí)行完畢時間.如果用F表示調度問題的優(yōu)化目標,即最小化最大完成時間,則有

F=min f=min{max(Ej,j=1,2,…,n)}=min{max(Wj+Tj,j=1,2,…,n)}.

3.3 確定算法的終止準則

PSO算法中最常用的終止準則是預先設定一個最大的迭代次數,或者當搜索過程中解的適應值在連續(xù)多次迭代后不再發(fā)生明顯改變時,終止算法.本文采用的方法是:當|F(x)i-F(x)i-1|<ε時,終止算法.其中,ε為事先給定的充分小的實數.

3.4 粒子解碼和調度方案的生成

在生成調度方案之前,需要對上述二維粒子進行解碼.采用對粒子的第二維即粒子位置xij進行取整操作,用IN T(xij)表示,由于xij∈[1,m],因此,取整后,IN T(xij)即表示作業(yè)j所對應的資源的位置.通過上述方式,將所有作業(yè)分配到不同的資源上,進而可以得到各資源上的作業(yè)序列,即調度方案.并且根據慣性權重PSO算法的速度-位置模型進行迭代,生成新的調度方案,其過程如圖2所示.

3.5 算法描述

算法描述如下:

1)隨機在解空間產生初始粒子群X={x1,x2,…,xn},飛行速度vi,并初始化粒子群規(guī)模n、慣性權重ω、隨機因子random()、學習因子c1和c2、最大飛行速度vmax、迭代終止條件ε.

圖2 粒子位置與調度解的映射關系Fig.2 Themapping of particle location and scheduling solution

2)維護一個作業(yè)執(zhí)行列表,對應項為各作業(yè)的預計執(zhí)行時間.

3)對粒子進行解碼并生成調度方案.通過查詢作業(yè)執(zhí)行列表,并根據設置的適應度函數計算粒子的適應值,即作業(yè)最大完成時間,如果某個粒子所生成的調度方案是不可行的,則將該粒子的適應值(即最大完成時間)設定為一個較大的值,并確定個體最優(yōu)粒子pbest和全局最優(yōu)粒子g best.

4)根據式(1)和式(2)對種群中粒子的位置和速度進行迭代.如果被更新的粒子位置超過了限制范圍[1,m+1],就在[1,m]之間隨機取值.

5)判斷迭代是否結束,如果是,則輸出全局最優(yōu)粒子和makespan,根據全局最優(yōu)粒子生成最佳調度.否則,轉向步驟3).

3.6 生成調度方案

利用PSO算法求解集群調度問題的流程見圖3.PSO算法在優(yōu)化效率和縮短計算時間等方面均有良好的特性.用于調度策略能夠使系統(tǒng)快速收斂到最佳調度,因此基于PSO算法的調度策略在生成調度方案的速度和精度上都會有明顯的提高.

圖3 利用PSO算法求解集群調度問題的流程圖Fig.3 The flow chart of the cluster scheduling p roblem using PSO algo rithm

4 實驗結果及分析

為了驗證算法的有效性,在一個集群環(huán)境中進行了仿真實驗.采用8個資源節(jié)點構成的同構集群平臺,節(jié)點的硬件配置為2 G內存,操作系統(tǒng)為Linux Red Hat 4.0,網絡通信采用100 M pbs的標準以太網.在該集群平臺上,對提交的500個作業(yè)進行測試.在實驗過程中,對backfill和基于PSO算法的調度策略進行了測試,并記錄了各節(jié)點的平均響應時間和CPU的利用率(R代表資源號),實驗結果如圖4和圖5所示.從實驗結果可以看出:①基于PSO算法的調度策略中,各節(jié)點平均響應時間均小于backfill,總的執(zhí)行時間也明顯降低.并且前者各節(jié)點的時間起伏較小,說明各作業(yè)基于以時間為適應度值的優(yōu)化效果較好.②基于PSO算法的調度策略在CPU利用率上高于backfill,并且各節(jié)點CPU利用率的起伏減小,說明各節(jié)點的負載更加均衡.

5 小結

本文提出并實現了基于粒子群優(yōu)化算法的調度策略,由于算法比較出色的性能,使得調度策略在生成速度和精度上都有明顯的提高.實驗結果表明,它可以明顯縮短系統(tǒng)的平均響應時間,使得各作業(yè)基于時間更加優(yōu)化,在一定程度上提高了各節(jié)點的CPU利用率和系統(tǒng)吞吐率,使得系統(tǒng)負載較為均衡,具有很高的工作效率.下一步研究將致力于PSO算法解決集群調度策略中負載均衡問題和計算集群環(huán)境的動態(tài)性研究.

[1] 劉志雄,王少梅.基于粒子群算法的并行多機調度問題研究[J].計算機集成制造系統(tǒng),2006,12(2):183-185.

[2] 吳啟迪,汪鐳.智能微粒群算法研究及應用[M].南京:江蘇教育出版社,2005.

[3] 劉志雄.調度問題中的粒子群優(yōu)化方法及其應用研究[D].武漢:武漢理工大學,2005:46-64.

[4] 谷峰,陳華平,盧冰原.粒子群算法在柔性工作車間調度中的應用[J].系統(tǒng)工程,2005,23(9):20-23.

Scheduling Strategy Based on Particle Swarm Optim ization Algorithm

L IU Su-qin, WANG Jing, L IXing-sheng, SHUO Jun, L IU Hui-hui
(College of Com puter and Comm unication Engineering,China University of Petroleum,Qingdao 266555,China)

In cognizance of the characteristics of cluster scheduling p roblem,scheduling strategy based on particle swarm op timization is designed and imp lemented.Compared w ith backfill algorithm,PSO algorithm can better imp rove the fairness of jobs.It can avoid the p roblem that bigger jobs can’t be executed quickly.The speed and accuracy of strategy generation are imp roved significantly.The experiment results show that the algo rithm increases the utilization of the CPU and reduces average response time.

cluster;job schedule;backfill algorithm;PSO algorithm

TP 18

A

1671-6841(2010)02-0043-04

2009-10-28

劉素芹(1968-),女,副教授,博士,主要從事高性能計算及應用研究,E-mail:liusq@upc.edu.cn;通訊聯系人:王婧(1985-),女,碩士研究生,主要從事高性能計算及應用研究,E-mail:wangjing0326@163.com.