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

劉素芹, 王 婧, 李興盛, 碩 珺, 劉會(huì)會(huì)

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

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

劉素芹, 王 婧, 李興盛, 碩 珺, 劉會(huì)會(huì)

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

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

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

0 引言

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

1 集群調(diào)度策略

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

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

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

2 PSO算法分析

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

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

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

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

3 基于PSO算法的調(diào)度策略的設(shè)計(jì)

本文設(shè)計(jì)了基于PSO算法的調(diào)度策略.PSO算法操作的基本對(duì)象是粒子或個(gè)體,每個(gè)粒子代表求解問題的一個(gè)可能解.在應(yīng)用PSO算法時(shí),需要確定以下要素:①粒子的編碼方法,即如何由粒子的編碼體現(xiàn)問題的解;②選取適當(dāng)?shù)倪m應(yīng)度函數(shù)或者目標(biāo)函數(shù)來計(jì)算適應(yīng)值,適應(yīng)值是唯一能夠反映并引導(dǎo)優(yōu)化過程不斷進(jìn)行的參量;③針對(duì)不同的算法模型,選擇適當(dāng)?shù)目刂茀?shù),直接影響算法的優(yōu)化性能;④選擇粒子群模型;⑤確定算法的終止準(zhǔn)則.

3.1 粒子的編碼方式

在利用PSO算法求解問題時(shí),其關(guān)鍵步驟是將問題的解從解空間映射到具有某種結(jié)構(gòu)的表示空間,即用什么樣的粒子表示方式來表達(dá)所求解問題的解空間.文獻(xiàn)[3]中提出了3種間接表示調(diào)度問題解的粒子表示方法,根據(jù)集群調(diào)度問題的特點(diǎn),本文采用基于粒子位置取整操作的表示方法.

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

3.2 確定適應(yīng)度函數(shù)

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

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

3.3 確定算法的終止準(zhǔn)則

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

3.4 粒子解碼和調(diào)度方案的生成

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

3.5 算法描述

算法描述如下:

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

圖2 粒子位置與調(diào)度解的映射關(guān)系Fig.2 Themapping of particle location and scheduling solution

2)維護(hù)一個(gè)作業(yè)執(zhí)行列表,對(duì)應(yīng)項(xiàng)為各作業(yè)的預(yù)計(jì)執(zhí)行時(shí)間.

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

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

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

3.6 生成調(diào)度方案

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

5 小結(jié)

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

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

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

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

[4] 谷峰,陳華平,盧冰原.粒子群算法在柔性工作車間調(diào)度中的應(yīng)用[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-),女,副教授,博士,主要從事高性能計(jì)算及應(yīng)用研究,E-mail:liusq@upc.edu.cn;通訊聯(lián)系人:王婧(1985-),女,碩士研究生,主要從事高性能計(jì)算及應(yīng)用研究,E-mail:wangjing0326@163.com.