基于资源结点性能预测的启发式调度算法研究

魏妮妮，宋 翌

（武汉生物工程学院 计算机与信息工程系，湖北 武汉 430415）

由于网格系统中的资源本身具有的动态性、分布性、异构性以及自治管理的特点，使得资源分配和任务调度问题一直是各界研究的核心。任务调度是个复杂问题，虽然已有深入和持久的研究，还是没有得到很好的解决。有学者提出了一些调度算法，这些算法往往是基于假设条件下提出的，比如在文献[1-4]中的调度模型是在假设任务得到处理机独享、通信没有费用、网络容量无限和独占网络带宽等条件提出的，这些算法用在现实网格系统中往往是不实际的，不但不能体现网格系统的优越性，甚至会导致网格系统的性能急剧下降。另外，任务调度问题也已经被证明是NP难题[5－6]，往往采用启发式算法，或是启发式算法的各种组合。在文献[4-7]中对一些经典的启发式任务调度算法进行了性能模拟试验，证明这些启发式算法花费的代价相对较小，但是这些已有的经典启发式调度算法，比如 OLB、Min-Min、Max-Min、MCT、SA算法和遗传算法等，往往是没有考虑资源结点性能度量，虽然在某些领域得到较好的应用，但也有一定的缺陷存在，特别是对于大吞吐量任务调度应用效果不佳。同时上述调度算法在制定时忽略了网格中各个资源结点的性能度量，然而任务调度策略制定的重要依据就是资源结点的性能度量。为此，本文针对高吞吐量应用问题提出了一种新的任务调度。

1 网格资源结点性能预测模型

在制定任务调度策略时考虑资源的性能预测，并建立精准的性能预测模型，这在网格复杂的多任务并行处理环境中是非常重要的。通过对网格计算任务调度问题的深入分析，对在文献[8-9]中提出过的考虑资源结点负载的任务完成时间的性能预测模型结构的基础上进行改进，引入了资源带宽监测和任务信息接收2个模块。应用此模型可以预测出资源结点的任务完成时间，也可以监测结点负载情况，使用该模型进行任务调度不仅可以兼顾任务长短和结点负载平衡，而且用户可以改变抽样率、所需的资源性能参数、带宽监测模式、调度策略等，用户只需提交应用任务的相关描述信息和设置一些参数即可。

该模型的系统结构由8个模块组成：用户控制子模块、测量子模块、任务信息接收子模块、结点负载预测子模块、结点网络带宽监测子模块、应用子模块、实时预测子模块和调度子模块。任务完成时间的预测系统结构如图1所示。

图1 任务完成时间预测系统结构

用户控制子模块用以实现其他子模块和用户之间的信息交互。用户可以改变抽样率、所需的资源性能参数、带宽监测模式、调度策略等，这些操作主要通过一种异步的请求／响应机制实现。测量子模块用以实现对各个资源结点当前负载情况的测量和周期取样，并把测量得到的量值存入到指定文件中。任务信息接收子模块用以接收用户提交应用任务的相关描述信息，比如任务完成的时间要求、任务需求的特殊资源等，并把接收的任务信息发送给调度子模块。结点负载预测子模块用以根据接收到的测量子模块发送的测量值，预计下一时间段资源结点潜在的负载情况。结点网络带宽监测子模块用以实现对各个资源结点带宽使用情况进行周期性监测，并把监测值存入到指定文件中、发送给实时预测子模块。应用子模块用以把一些结点和应用的性能参数传送给实时预测子模块。实时预测子模块根据网络带宽监测子模块传送的网络带宽和结点负载预测子模块发送的结点负载情况、应用模块传送的资源结点的性能参数等来预测任务的完成时间。调度子模块根据实时预测模块得到的预测值和可用候选资源结点及任务信息接收模块传送的信息制定调度策略，以实现任务与资源结点的最佳匹配执行。

在完成时间预测模型的基础上，得到任务执行时间的预测公式：

其中用load（t）表示在t时刻资源结点的负载，tunload表示任务在资源结点完全没有负载情况下的执行时间，它可体现出任务对当前资源结点的CPU的需求，texe表示任务的执行时间。

如果给出tunload，测量子模块通过周期采样资源结点的负载，并把测量结果传送给结点负载预测子模块，就可计算资源结点在t时刻可能具有的负载load（t），实时预测子模块根据结点负载预测子模块传送的数据，就可预测该任务的执行时间texe。

带宽监测子模块通过定期地发送一些数据包给资源结点，当某个资源结点接收到数据包后，不进行计算而是直接把接收到的数据包反传给资源结点的带宽监测模块，这样监测模块可以根据传送数据包来回的时延计算当前时刻结点所具有的网络带宽。

通过上述分析可知，使用任务完成时间预测模块中的实时预测子模块可以计算出各个任务在不同资源结点上的预测完成时间。本文提出的算法即是以此为依据来实施任务调度。

2 资源结点性能度量任务调度算法——BNPP算法

对于相同的资源和任务，在理想状态下，当把任意一个任务gi分配到一个可用资源结点pj上执行时，任务gi是独占结点pj的CPU处理能力和网络带宽的，网格资源发现服务的资源属性表中提供了相应结点的网络带宽和CPU处理能力。这种条件下可求出任务的总的执行时间，即任务到达资源结点时间＋任务在资源结点上执行时间。任务总的执行时间为

其中：βij表示任务总的执行时间；Aij表示任务gi到达pj的时间，Aij＝gi的任务量／pj的网络带宽；Rij表示任务gi在pj上的执行时间，Rij＝gi的任务量／pj的CPU处理能力。

求出实际网格计算系统中1次任务调度的总的完成时间为

其中，cij表示任务gi分配给结点pj处理任务总的完成时间，aij表示实际的到达时间，rij表示任务的预测完成时间。

通过任务完成时间预测模型中的带宽监测子模块可得到aij的值，rij的值也可通过性能预测求得。可以定义1次任务调度完成时间为 maxt∈｛t1，t…，tn｝icij。显然完成1次任务调度的时间越少，系统的性能就越好。

资源结点的性能是以处理所有任务的完成时间的平均值来进行度量的，对于资源集P中的任意一个资源结点pj处理任务集G中的所有任务总的平均执行时间为。avej的大小可以表示出资源结点处理能力的强弱。假设有2结点p1和p2，如果ave1＜ave2，则说明p2结点空闲时间比p1少，即资源结点p1的性能低于资源结点p2。

定义wj表示资源结点pj的性能的权值，则wj为pj处理任务集G中的所有任务总的平均执行时间除以资源集P中每个结点处理任务集G中的所有任务总的平均执行时间之和，用公式即可表示为：

坡向对于太阳的光照、住宅的采光度有着重要的影响。客家人对住宅选址、布局、门的朝向上讲究“风水”，坡向(图4b)也是影响客家人的建筑分布的一个因子。对DEM数据进行坡度提取得到梅县区内地形的坡度数据(图4c)。使用ArcGIS的分类功能，按照城市建设划分标准中划分为地平地、平地、平坡地、缓坡地、中坡地、陡坡地6种类型分别占总面积的0.21%、5.48%、14.22%、23.58%、48.03%、8.48%，平均坡度为12.5°，坡度标准差为8.23°。

其中，k表示资源结点的个数，且k≥1的正整数。

通过此式可求出资源集中的任意一个结点的性能的权值，资源集中所有资源结点的性能的权值之和为1。显然结点的性能的权值越小，说明它完成任务所用的时间越小，则表明结点的性能就越好。

下面定义判断任务完成的难易度。任务gi在资源集中所有结点上总的执行时间加权平均值用di表示，则。对于任意的2个任务g1和g2，如果d1＞d2，意味着相同的资源结点处理g1所花费的时间长于g2，表明任务g1相比于任务g2更难完成。通过上述计算和分析，就以任务完成的难易程度来进行排序，di的值越大表明其越难完成，在进行调度时与使它具有最快完成时间的资源进行匹配实施调度。

给出基于资源结点性能度量最难完成的任务分配给执行时间最短的结点算法的具体描述如下：

设网格计算系统中有n相互独立的任务形成的集合G＝｛g1，g2，...，gn｝，m 个可用资源形成的集合P＝｛p1，p2，...，pm｝。di表示任务gi在所有结点上总的执行时间加权平均值，avej表示资源结点pj处理任务集G中的所有任务总平均执行时间。则算法调度实施简要步骤描述如下：

（1）利用任务完成时间预测模型，计算任务集里的各个任务在可用资源集中各个资源结点上的预测完成时间；

（3）计算任务集中所有任务的难易指标di；

（4）找出具有最大di的任务及使它具有最小执行时间的对应结点，得出此时的任务最小预测完成时间；

（5）调度最难完成任务到性能最好的结点上；

（6）从任务集中删除执行完任务，重复此过程直到完毕；

（7）更新任务集和资源信息；

（8）转到（4）重复执行，直到任务集中所有任务完成。

3 仿真实验与性能分析

针对BNPP算法，使用SimGrid进行仿真。创建1个中心结点，创建10个用户结点作为计算资源，任意给出20个相互独立的任务，任务采用文献中使用的方式，即泊松分布进行提交。在实验中规定任务的计算长度介于1000MI到100000MI之间。针对于相同的任务在仿真平台上分别调用min-min、max-min、Sufferage和BNPP 4种调度算法在任务完成总的时间和系统资源利用率方面进行比较。仿真结果见表1和图2。

表1 4种算法资源结点执行任务所花时间

图2 4种算法任务总的完成时间对比

从图2及表1中可得到分别应用上述4种启发式算法调度总的任务完成时间：min-min算法为5.3s，max-min算法为4.5s，Sufferage算法为4.1s，BNPP算法为4.0s。因此，min-min算法、max-min算法和Sufferage算法的总的任务完成时间都大于本文的BNPP算法。min-min算法将具有最短完成时间的任务分配给最早完成此任务的结点，这就导致完成时间较长的任务被分配给负载重的结点去完成。本文提出的算法中大部分结点的任务完成时间要小于max-min算法，且各个资源结点随时间变化比较平稳。

在资源结点数量性能不变的前提下，现将上面的仿真条件进行如下改变：将提交的相互独立的任务的数量增加到1000个（高吞吐量应用），定义调度周期为6s，其他约束不变，4种算法进行任务调度资源利用率Y的对比见图3。

图3 网格系统资源利用率对比

图3中，用任务完成率来进行资源结点的性能比较，Y轴的值为各个资源结点任务完成率的最大值与最小值之差。差值小说明资源结点利用率高，差值大说明资源结点的利用率低，可以既简便又准确地表示出资源结点性能好坏。由图3可以看出，本文提出的BNPP算法从系统资源利用率方面也优于其他3种算法。

4 结论

文中的BNPP调度算法在综合考虑了网格系统自身特点、构成网格系统资源的动态特点，以及任务的某些要求下而设计的。通过仿真实验并和以往应用较多的经典启发式调度算法min-min、max-min及Sufferage进行比较，结果证明BNPP算法在任务总的完成时间和系统资源利用率方面都优于上述3种方法，BNPP算法既减少了任务总的完成时间，又平衡了资源结点的负载、提高了资源利用率，所以BNPP算法非常适合解决高吞吐率应用问题的任务调度。

（References）

[1]金海，袁平鹏，石柯译.网格计算[M].北京：电子工业出版社，2004.

[2]Casanova H.Network Modeling Issues for Grid Application Scheduling[J].The International Journal of Foundations of Computer Science，2005，6（2）：145-162.

[3]丁敏敏.网格计算中改进 Min-Min算法的研究[D].西安：西北大学，2010：16-21.

[4]Li Lingjuan，Shi Xiangning，Wang Ruchuan.An Improved Ant Algorithm-Based Task Scheduling Strategy in Grid[J].Journal of Nan Jing Unicersity of Posts and Elecommunications：Natural Science，2008，28（3）：18-20.

[5]Yin Fei，Jiang Changjun，Deng Rong，et al.Gird resource management policies for load＿balanceing and energy＿saving by vacatior queuing theoy[J].Computer and Electrical Engineering，2009（35）：966-976.

[6]罗红，慕德俊，邓智群.网格计算中作业调度研究综述[J].计算机应用研究，2005，22（5）：16-19.

[7]彭云海，李骞，李强.网格环境下资源负载均衡和优化调度研究[J].计算机工程与应用，2009（19）：104-106.

[8]吴成茂.基于免疫原理的网格任务调度算法 [J].计算机工程，2011（1）：164-166.

[9]唐阔.网格计算资源与任务的实时监测预报系统[D].长春：吉林大学，2010：32-37.