刘素芹, 王 婧, 李兴盛, 硕 珺, 刘会会

(中国石油大学计算机与通信工程学院 山东青岛266555)

基于粒子群优化算法的集群调度策略

刘素芹, 王 婧, 李兴盛, 硕 珺, 刘会会

(中国石油大学计算机与通信工程学院 山东青岛266555)

针对集群调度问题的特点,设计了基于粒子群优化算法的调度策略.与传统backfill算法相比,粒子群优化算法对作业比较公平,能避免对大作业响应慢的缺点,使得调度策略在生成速度和精度上都有明显的提高.实验结果表明,该调度策略能较好地提高CPU利用率和缩短作业平均响应时间.

集群;作业调度;backfill算法;PSO算法

0 引言

粒子群优化(particle swarm op timization,PSO)算法是一种模仿鸟群社会行为的智能优化算法,具有并行性、有效的全局/局部搜索平衡能力、计算简单、鲁棒性好等优点,已经在函数优化、神经网络训练、模糊系统控制等领域得以应用,并进行了不断的改进[1].PSO算法已在并行多机调度中得到十分有效的应用,但在集群调度中的应用研究较少,集群和并行机的调度问题十分类似,把PSO算法应用在集群调度中有十分重要的意义.本文通过分析集群调度策略的原理、研究现状以及PSO算法的原理,设计并实现了基于粒子群优化算法的集群调度策略,取得了较好的效果.

1 集群调度策略

集群系统的主要目标是通过高效的资源管理和作业调度技术实现资源的有效共享,提高系统资源利用率,获得高性能,因此作业调度技术是实现资源共享和提高计算效率的有效途径.

图1 集群作业调度模型Fig.1 Scheduling model of cluster

集群作业调度模型如图1所示.在集群作业调度模型中,(M1,M2,…,Mn)是一组待处理的模块或子任务, (P1,P2,…,Pm)是系统的m个处理机或节点机,它们通过网络相互通信,调度机制S通过一定的策略把n个模块或子任务合理地分配给m个处理机.集群作业调度是实际生产过程中的一类典型调度问题,以最大完成时间最小为优化目标的集群作业调度问题已经被证明是NP完全问题[2].

2 PSO算法分析

PSO算法是一种基于迭代的优化算法.其基本思想是:通过对个体最优和全局最优粒子的记忆,实现群体信息的共享和个体之间经验和发现的交互学习,进而通过速度-位置模型来实现这种共享和学习,使得种群中的所有粒子快速向最优解移动.

PSO算法的基本原理是:算法中每个粒子都是解空间(D维)的一点,并且都具有一个速度,不同粒子具有对应于目标函数的个体适应度.每个粒子根据自身的飞行经验和群体的飞行经验来调整自己的飞行轨迹,向最优点靠拢.在每一步中,粒子根据式(1),(2)更新自己的位置.

其中,ω为惯性权重;random()为(0,1)之间的随机数;c1和c2为学习因子,合适的学习因子可以加快收敛并且不易陷入局部最优;pi为当前粒子群中的个体最优粒子;向量g为全局最优粒子.粒子在每一维飞行的速度不能超过算法设定的最大值vmax.

PSO算法在优化结果和收敛速度方面均要优于遗传算法[3].用PSO算法求解作业调度问题,寻找问题解和算法中微粒间的恰当映射,使得所有处理器的最大处理时间为最小.在解决作业调度问题中,PSO算法是一种有效的选择.

3 基于PSO算法的调度策略的设计

本文设计了基于PSO算法的调度策略.PSO算法操作的基本对象是粒子或个体,每个粒子代表求解问题的一个可能解.在应用PSO算法时,需要确定以下要素:①粒子的编码方法,即如何由粒子的编码体现问题的解;②选取适当的适应度函数或者目标函数来计算适应值,适应值是唯一能够反映并引导优化过程不断进行的参量;③针对不同的算法模型,选择适当的控制参数,直接影响算法的优化性能;④选择粒子群模型;⑤确定算法的终止准则.

3.1 粒子的编码方式

在利用PSO算法求解问题时,其关键步骤是将问题的解从解空间映射到具有某种结构的表示空间,即用什么样的粒子表示方式来表达所求解问题的解空间.文献[3]中提出了3种间接表示调度问题解的粒子表示方法,根据集群调度问题的特点,本文采用基于粒子位置取整操作的表示方法.

定义一个二维粒子,二维粒子中的第一维用自然数1,2,…,n表示n个作业,第二维表示粒子的位置,即所选择的节点资源的位置,粒子的长度为所有作业的数量.对于粒子种群中第i个二维粒子xi的一个向量可以表示为:,j=1,2,…,n,xij∈[1,m+1)是一个随机实数,m为资源节点的数量,用自然数1,2,…, m表示不同的资源节点.

3.2 确定适应度函数

作业调度的目标为调度的最大完成时间(makespan)最小[4].对于n个作业、m个资源节点的集群调度问题,用Tj表示作业j的执行时间,Wj表示执行过程中该作业等待执行的时间,Ej表示该作业的执行完毕时间.如果用F表示调度问题的优化目标,即最小化最大完成时间,则有

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

3.3 确定算法的终止准则

PSO算法中最常用的终止准则是预先设定一个最大的迭代次数,或者当搜索过程中解的适应值在连续多次迭代后不再发生明显改变时,终止算法.本文采用的方法是:当|F(x)i-F(x)i-1|<ε时,终止算法.其中,ε为事先给定的充分小的实数.

3.4 粒子解码和调度方案的生成

在生成调度方案之前,需要对上述二维粒子进行解码.采用对粒子的第二维即粒子位置xij进行取整操作,用IN T(xij)表示,由于xij∈[1,m],因此,取整后,IN T(xij)即表示作业j所对应的资源的位置.通过上述方式,将所有作业分配到不同的资源上,进而可以得到各资源上的作业序列,即调度方案.并且根据惯性权重PSO算法的速度-位置模型进行迭代,生成新的调度方案,其过程如图2所示.

3.5 算法描述

算法描述如下:

1)随机在解空间产生初始粒子群X={x1,x2,…,xn},飞行速度vi,并初始化粒子群规模n、惯性权重ω、随机因子random()、学习因子c1和c2、最大飞行速度vmax、迭代终止条件ε.

图2 粒子位置与调度解的映射关系Fig.2 Themapping of particle location and scheduling solution

2)维护一个作业执行列表,对应项为各作业的预计执行时间.

3)对粒子进行解码并生成调度方案.通过查询作业执行列表,并根据设置的适应度函数计算粒子的适应值,即作业最大完成时间,如果某个粒子所生成的调度方案是不可行的,则将该粒子的适应值(即最大完成时间)设定为一个较大的值,并确定个体最优粒子pbest和全局最优粒子g best.

4)根据式(1)和式(2)对种群中粒子的位置和速度进行迭代.如果被更新的粒子位置超过了限制范围[1,m+1],就在[1,m]之间随机取值.

5)判断迭代是否结束,如果是,则输出全局最优粒子和makespan,根据全局最优粒子生成最佳调度.否则,转向步骤3).

3.6 生成调度方案

利用PSO算法求解集群调度问题的流程见图3.PSO算法在优化效率和缩短计算时间等方面均有良好的特性.用于调度策略能够使系统快速收敛到最佳调度,因此基于PSO算法的调度策略在生成调度方案的速度和精度上都会有明显的提高.

图3 利用PSO算法求解集群调度问题的流程图Fig.3 The flow chart of the cluster scheduling p roblem using PSO algo rithm

4 实验结果及分析

为了验证算法的有效性,在一个集群环境中进行了仿真实验.采用8个资源节点构成的同构集群平台,节点的硬件配置为2 G内存,操作系统为Linux Red Hat 4.0,网络通信采用100 M pbs的标准以太网.在该集群平台上,对提交的500个作业进行测试.在实验过程中,对backfill和基于PSO算法的调度策略进行了测试,并记录了各节点的平均响应时间和CPU的利用率(R代表资源号),实验结果如图4和图5所示.从实验结果可以看出:①基于PSO算法的调度策略中,各节点平均响应时间均小于backfill,总的执行时间也明显降低.并且前者各节点的时间起伏较小,说明各作业基于以时间为适应度值的优化效果较好.②基于PSO算法的调度策略在CPU利用率上高于backfill,并且各节点CPU利用率的起伏减小,说明各节点的负载更加均衡.

5 小结

本文提出并实现了基于粒子群优化算法的调度策略,由于算法比较出色的性能,使得调度策略在生成速度和精度上都有明显的提高.实验结果表明,它可以明显缩短系统的平均响应时间,使得各作业基于时间更加优化,在一定程度上提高了各节点的CPU利用率和系统吞吐率,使得系统负载较为均衡,具有很高的工作效率.下一步研究将致力于PSO算法解决集群调度策略中负载均衡问题和计算集群环境的动态性研究.

[1] 刘志雄,王少梅.基于粒子群算法的并行多机调度问题研究[J].计算机集成制造系统,2006,12(2):183-185.

[2] 吴启迪,汪镭.智能微粒群算法研究及应用[M].南京:江苏教育出版社,2005.

[3] 刘志雄.调度问题中的粒子群优化方法及其应用研究[D].武汉:武汉理工大学,2005:46-64.

[4] 谷峰,陈华平,卢冰原.粒子群算法在柔性工作车间调度中的应用[J].系统工程,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.