基于主机负载预测的动态任务调度算法研究

摘要:提出一种基于遗传神经网络的主机负载预测模型,并基于该模型设计了集中式任务调度算法CJD-HLP。CJD-HLP采用预测法提前获得主机负载信息,保证了任务调度时使用决策信息的实时性、准确性,避免了负载迁移的抖动问题。实验结果表明,该算法较基于实测法的其他任务调度算法在性能上有较大提高。

关键词:负载预测;动态任务调度;网络并行计算;PVM

中图分类号:TP301.6文献标识码:A 文章编号:1009-3044(2010)02-388-03

Research on Dynamic Task Scheduling Algorithm Based on Host Load Prediction

XIE Fang-qing, TAN Yi

(Zhongkai University of Agriculture and Engineering, Guangzhou 510225, China)

Abstract: A host load prediction model based on heredity-neural network is proposed, and center task scheduling algorithm CJD-HLP based on the model is designed. CJD-HLP algorithm adopts prediction method to get the host load information earlier, ensure that the information for decision-making is real-time and accurate and avoid the load transfer jitter problem. Experimental results demonstrate that the algorithm performance is greatly enhanced compared with the algorithm based on actual measurement.

Key words: load prediction; dynamic task scheduling; network parallel computing; PVM

1 概述

网络并行计算由于可以利用网络中空闲资源进行计算而得到广泛研究,然而经常会出现某些处理机负载过重而另外一些处理机很轻甚至空闲的情况,即负载不均衡现象。负载的不均衡大大降低了整个系统的资源利用率,直接影响到并行计算的性能。而实现负载均衡的关键是设计好的任务调度算法。PVM本身只提供了静态任务调度方法[1],即在进行任务分配时采用二次均分法,该方法不考虑处理机负载情况,将待分配任务平均分配到各个结点上,并且在运行时负载不能重新分配;而在目前提出的动态任务调度方法中,大都采用实测法收集结点负载的实时值作为任务调度的依据,但实测法存在以下几个缺点[2]:

1)实测法系统开销大。需要直接或间接利用系统调用来测量负载,系统调用需要从用户态到核心态的切换,时间开销很大,极大地影响了系统效率。

2)实测法存在信息过时问题。负载信息从开始收集到传递给调度结点存在传递时延,调度结点依据负载信息进行调度决定又存在决策时延,过多的时延使收集的实时负载信息与调度后的负载状况有较大的差异,从而造成依据实时负载信息作出的调度决定不能实现有效的负载平衡。

3)实测法存在收集代价问题。指任务调度方法带来的性能上的提高与信息收集带来的系统消耗之间的比较关系,如果信息收集的系统消耗太大,将抵消动态任务调度带来的性能上的提高。

因此,如果能够采用快速高效的预测算法,预先获得结点的负载信息,则在进行动态任务调度时就会有提前量,就可以避免因各种时延使决策信息过时而引起进程迁移的抖动,从而使整个系统的负载均衡性能得到较大提高。本文基于Windows XP+WPVM平台组成的机群系统,采用遗传神经网络预测主机结点的负载,并基于负载预测提出CJD-HLP算法实现任务的动态调度,有效提高了网络并行计算的性能。

2 负载的选择

负载指标被负载平衡机制用于决定任务放置的位置,目前对结点机负载指标的评价还没有统一适用的标准。一般常用的负载指标包括CPU处理能力,CPU利用率,运行队列中的进程数,磁盘及内存可用空间,I/0利用率,进程响应时间等。考虑到通常的实验环境是在同一个实验室的局域网内,各机器一般都是由实验室统一购买,机器之间的性能差别很小,故CUP和内存等负载指标的影响处于次要地位。同时,为了降低收集系统负载的开销,避免各负载指标因量纲和单位不同难以统一标准化的问题,本文采用单一指标法进行负载定义,即将运行队列中的进程数作为负载指标。

3 主机负载预测模型

主机负载由于受到多种因素的影响,对主机负载预测是一件非常困难的事。负载的变化具有严重的非线性、极大的不确定性和随机性,因此很难对其建立起精确的数学预测模型,而应用遗传神经网络则可以较好地解决这一问题。

遗传神经网络是将遗传算法应用到BP神经网络中,以实现对BP神经网络初始权阈值的优化。由于遗传算法具有全局搜索、收敛速度快的特点,将其与BP神经网络相结合,不仅能发挥神经网络的泛化映射能力,还可以使神经网络克服收敛速度慢和容易陷入局部误差极小点等缺点[3]。

就主机负载的短期预测而言,如何允分利用单因索时间序列所提供的信息就显得至关重要。为此,本文采用将一维时间序列通过向空间扩维,变化为多维时间序列模式的分析思想,充分挖掘一维时间序列所提供的信息,根据时间序列数据重建动态模型以实现对负载变化的预测。可以通过实验测试,确定某一时间延迟k,使序列中下一个抽样时刻t+T时刻的观测值与当前时刻t之前的k个时段的观测值(l(t),l(t-T),l(t-2T),...,l(l-KT))之间有较好的相关关系。并以l(t),l(t-T),l(t-2T),...,l(l-kT)为控制参数作为网络的输入变量,l(t+T)为网络的输出变量,由此来建立一个k个输入,1个输出的遗传神经网络。

应用遗传神经网络对主机负载建立一种非线性自回归预测模型,其模型的差分方程可表示为:

l(t+T)=f(l(t),l(t-T),l(t-2T),...,l(l-kT)) (1)

其中t为当前时间,l(t)为当前时刻t时的负载;l(t+T)为输出向量,表示t+T时刻的预测负载;f是非线性函数。现已有资料证明大部分的非线性系统都可用式(1)表示。实验证明,通过对历史样本数据进行反复训练,可以使该遗传神经网络的负载误差控制在10%以内。建立的主机负载预测模型如图1所示。

4 算法实现与调度策略

在PVM环境下,通过研究PVM的函数以及PVM的实现机制发现,PVM主要是利用函数pvm_spawn()来实现子任务的生成的,其函数说明如下[4]:

int numt=pvm_spawn(char*task,char **argv,int flag,char*where,int ntask,int tids)

通过修改主结点中的该函数,可以实现动态任务调度算法。另外,负载信息收集和负载信息的预测以及进程的迁移都以守护进程Daemon方式运行在机群系统中的各个结点上。遗传神经网络学习过程可以事先进行,所以学习速度并不是关键所在。为了便于算法的描述,先给出以下名称定义:

定义1 负载状态:为了避免抖动,达到稳定性,本文采用了双阈值Lmax和Lmin,它们是根据系统总的负载情况动态可调的。根据结点的负载与阀值的关系,将结点分成分为三类:

1)重载:负载值L>Lmax

2)适载:Lmin

3)轻载:负载值L

其中,Lmax是根据系统的整体负载水平动态变化的,任务主要由处于重载的结点迁移到申请任务的轻载结点上。

定义2 发送者和接收者:在一次任务迁移中,任务迁移的源结点为发送者,任务迁移的目的结点为接收者。

本文在充分借鉴集中式任务调度算法CJD(Center Job Dispatcher)[5]的基础上,对该该算法加以改进,设计出基于主机负载预测的集中式任务调度算法CJD-HLP(Center Job Dispatcher Based on Host Load Predicted)。在该算法中,主结点中维护着两个信息表(子节点中无需信息表),即发送者表和接收者表,其中发送者表记录系统中的发送者结点的数据结构,接收者表记录接收者结点数据结构。算法采用接收者驱动和子结点主动汇报的方式,并且只有子结点的负载状况由忙变闲时才向主结点主动汇报负载情况,汇报周期可以采取自适应方式。图2为CJD-HLP算法模型。

下面分别描述主结点与子结点调度算法。

4.1 主结点调度算法

Step1:系统初始化,将主结点中的发送者表和接收者表清空,

Step2:等待子结点发送来的请求任务消息。

Step3:if(在t时刻收到子结点iNode发来的请求任务消息) 转(1)进行处理;

else转Step2;

1)更新信息表,向系统内的所有其他子结点广播任务请求信号,包括接收者iNode的地址Raddr,请求的任务数量Rtask;

2)指示系统内其他子结点机停止抽样,并询问它们在下一时间段t+T的负载情况;

3)主结点转入wait状态;接收响应信号,更新信息表。将t到t+T时间段内收到的所有重载结点发来的响应信息(包括发送者地址Saddr、待分配的任务数Wtask等)记录到发送者表中。

4)根据构造的效益函数f=benifit(i,j)-cost(i,j)计算发送者表中的所有发送者的任务迁移效益,其中benifit(i,j)和cost(i,j)分别为从结点i迁移到结点j带来的收益和系统开销。根据f的值对各发送者进行排序;

5)选择效益最高的发送者jNode,指示其将过载任务迁移到iNode,更新信息表。

Step4: 算法结束

4.2 子结点调度算法

Step1:所有子结点在抽样时刻t调用守护进程对下一个抽样时间段t+T内的负载进行预测。

Step2:if(预测到在t+T时间段内处于轻载)转Step3,调度接收者算法;

else if(预测到在t+T时间段内处于重载) 转Step4,调用发送者算法;

else (子结点处于适载) 转 Step1

Step3:接收者算法:

1) 向主结点发送任务请求信号,包括接收者iNode的地址Raddr,请求的任务数量Rtask;

2) 停止抽样,进入wait状态;

3) 收到主结点的响应指令,接收从发送者迁移的任务;

4) 转 Step1

Step4:发送者算法:

1) 向主结点发送响应信号(包括发送者地址Saddr、待分配的任务数Wtask等信息);

2) 停止抽样,等待主结点发来的迁移指令;

3) if(收到迁移任务指令)向接收者iNode迁移任务;

else转Step1

Step5: 算法结束

5 实验结果及分析

本文作者组建了一个机群系统,软硬件配置如下:1)软件环境:WPVM 3.4 on Windows XP,VC++6.0,TCP/IP,2)硬件环境:P4 2.66 CPU,512M DRAM,100Mbps Ethernet。

对BP神经网络进行如下参数设置:根据仿真实验,1)式中的k取10效果最好,抽样周期取T=2秒,这样BP神经网络的输入层节点数为10;根据Hecht-Nielsen理论,隐含层节点数为2N+1,其中N为输人节点数。综合考虑网络的收敛速度和输出精度,将隐含层节点数设置为18;输出层为预测负载(主机上运行的进程数),所以输出为1。这样,得到网络的拓扑结构为10×18×1。网络隐含层神经元变换函数采用tansig型,输出层采用purelin型线性函数。

为了测试该算法的性能,现取5台上述配置的PC组成一个机群系统,并以典型的求素数做为算例。由于求素数程序的循环迭代相互独立,而且每次迭代的执行时间也不相同,能够很好的反映在实际的并行系统上任务的运行情况。本文分别采用二次均分法,CJD算法和本文提出的CJD-HLP算法并行执行求素数程序,并采用加速比做为各算法在不同规模下进行比较的指标,比较结果如表1所示。

实验结果显示,在当计算的规模比较小时,以上三种算法的并行效果没有显著差别,但是当数据规模非常大时,尤其是各结点任务变化很大时,动态任务调度算法加速比高于静态调度算法,并且基于预测的任务调度算法加速比明显高于其他两种算法,这主要是由于:

1)随着计算规模的增大,动态任务调度带来的好处远远大于调度带来的额外开销。

2)采用接收者主动汇报方法,各子结点之间无需交换信息,降低了通讯开销。

3)通过有效调度,各结点不会出现空闲状态,从而提高了机群系统的整体并行效率。

6 结束语

本文提出基于遗传神经网络的主机负载预测模型,并基于该模型设计实现了CJD-HLP算法。采用预测法获得主机负载,有效地避免了因各种时延导致决策信息陈旧而引起进程迁移的抖动,提高了任务调度的实时性、准确性,提高了机群系统的并行性能。

参考文献:

[1] 鞠九滨,王勇.调度PVM任务[J].计算机学报,1997,20(5):470-474.

[2] 李庆华,郭志鑫.一种面向工作站网络的系统负载预测方法[J].华中科技大学学报,2002,30(6):49-51.

[3] 阎平凡,张长水.人工神经网络与模拟进化计算[M].北京:清华大学出版社,2000:396-421.

[4] 张建军,蒋廷耀,郭志鑫.PVM中动态负载平衡的设计和实现[J].计算机工程,2005,31(7):63-64.

[5] 李庆华,尹杜红.一个基于预测的负载平衡策略[J].计算机与数字工程,2003,31(4):54-57.