一种多目标最优资源聚类的网格调度算法

邱 昕，赵俊杰，林 琳

（营口职业技术学院 辽宁 营口 115000）

0 引言

目前，网格技术在基础研究、制造业、工业等诸多领域，发挥了空前的作用。网格环境具有资源规模庞大的特点，在资源查找上所耗费的大量时间，对于调度是一大难题，因此对资源进行聚类预处理的方式，不但可以提高资源的定位效率，而且可以节省调度时间。

在构建模型方面，有文献提出用超图构建模型，这样可在问题描述方面提供很多便利，有利于实际问题的解决。超图（Hypergraph）是二元对H=(V,E)，其中V={v1,v2,...,vn}表示超图的n个顶点，E={e1,e2,...em}表示超图的m条超边，超图的图形表示[1-2]，见图1。

本文结合超图理论，提出了一种资源聚类算法MORC，该方法主要针对大规模任务调度，并且在资源规模庞大的情况下，能够快速有效地进行调度。首先运用超图理论，构建了资源超图模型，很好地描述了资源整合的能力，这对资源聚类、调度时间都有直接的影响；进而运用遗传算法对资源进行聚类预处理，追求类内距离小，类间距离大，并且类内节点数量均衡的多目标优化转单目标优化，能够充分结合网格资源的特点，自适应的寻优完成聚类；在负载均衡方面，设置阈值来控制资源的可用性；调度时，以最小化完成时间为目标。该方法与经典算法Min-min算法相比，缩短了任务与资源相匹配的时间，从而缩短了整个调度时间，并且在资源负载均衡方面有了很大提高。

1 任务模型

建立任务模型，在任务模型中描述了任务节点，任务均为计算任务，且都是元任务，即任务之间没有相互依赖关系，可以独立执行。任务描述如下：

任务描述：RV=｛rv1，rv2，……，rvrn｝是任务节点的集合，其中，rvi=｛rID，rCa，rS｝是任务的属性的集合，其中i∈[1，rn]。

（1）rID表示任务的ID标识。

（2）rCa是任务计算量。

（3）rS是任务的状态，表示方法见表1。

表1 任务的状态表示方法

任务调度的过程中，任务起初是空闲状态，储存在未调度集合T中，然后与资源进行匹配，匹配成功后传输到资源节点上，在等待列队中等待执行，待任务执行完毕后，任务的状态为完毕。

2 资源超图模型

利用超图理论构建资源超图模型，超图由资源节点和超边组成，资源节点是一个六元组，即资源ID、资源处理和通信能力、综合性能值、资源状态和负载[2]。资源描述如下：

H=（X，E）是资源模型的超图表示。

（1）X=｛v1，v2，……，vn｝是资源节点的集合，其中vi=｛ID，P，C，PC，S，Load｝是资源节点的属性集合，i∈ [1，n]。

①ID为资源的ID标识。

②P为资源的处理能力。

③C为资源通信的能力。

④PC是资源的综合性能值，由资源的处理能力和通信能力组成。考虑到处理能力与通信能力差值过大问题，采用归一化的方法得到综合性能值公式如下：

其中，r1、r2是权重系数，Pi是资源vi的处理能力，Ci是资源vi的通信能力。

⑤S是资源的状态，包括有效资源状态valid和无效资源状态invalid。表示方法如下，S=｛valid，invalid｝

有效资源状态是指此时资源可以接受任务，无效资源状态是指此时资源不可以接受任务。资源的状态由接受和拒绝阈值来控制，这样做的目的是为了均衡资源节点的负载问题[3]。当资源节点负载值大于拒绝阈值θa时，资源为无效资源，直到资源的负载值小于接受阈值θr时，资源才可以变为有效状态。

⑥Load表示资源的负载，等待列队中任务计算量和已匹配且未进入等待列队的任务计算量的和称为资源负载，公式表示如下：

其中，Loadk是资源k的负载，Rwaitk是资源k上等待集合中任务的计算量总和，Rmatchk是已经与资源k匹配，但是还未传到资源上的任务的计算量总和。

（2）E=｛e1，e2，……，em｝是超边集合，m=|E|是超边数，超边ej的权值Wj是该超边所包含的资源节点的平均性能值。

其中，PCi是vi的综合性能值，|ej|是超边ej内所包含资源节点的数量。资源聚类后，质心代表聚类的情况，因此质心的综合性能值就是Wj，|ej|是聚类中资源节点的个数，即聚类内节点的平均综合性能值。

3 资源聚类

对网格资源采用遗传算法进行聚类预处理，可以将资源很好地进行分类，节省任务与资源的匹配时间。本文用多目标转化为单目标的方式，采用遗传算法对资源进行聚类预处理，通过资源节点间的相似程度进行聚类，减少了调度过程中选择资源所花费的时间，从而提高调度的效率[4]。首先根据资源节点的相似程度，构建3个目标：类内距离、类间距离、类内节点个数方差，追求类内距离小，类间距离大，类内节点个数均衡，将三目标转为单目标函数，并作为遗传算法的评价函数，然后用遗传算法对资源节点进行聚类。

3.1 目标函数

网格资源聚类是将多个目标转化为单一目标函数的方式进行聚类。以类内距离和类间距离为指标，距离是指任意两个资源节点的性能距离，即两节点间性能距离越小，说明两节点综合性能值越相似。类内距离应该最小化，以确保聚类结果的密度，这样可以保证质心倾向密度区域。类间距离是质心节点间的平均距离，应该最大化使质心尽量分布均匀。同时，为了保证各类内节点数量均衡，引入了节点个数的方差公式，使之最小化，以保证节点数量均衡。以这3个目标为基准，最终转化为一个目标函数，再用遗传算法进行聚类。

资源节点之间的相似程度由性能距离来定义：

类内距离：

类间距离：

聚类内节点个数的方差：

其中，m为聚类数，n为节点数，hi：第i个聚类的中心结点，Di：节点i所在的聚类，xi是第i个聚类内节点个数，是平均值。

为了共同达到以上3个目标，还需将多目标转化为单目标并作为遗传算法聚类的评价函数：

在多目标聚类中，类内距离f1表示类内节点的性能距离，我们希望将性能值接近的节点放在一个聚类内，因此类内距离f1越小越好。类间距离f2表示类与类之间的性能值差异，因此类间距离f2越大越好。聚类内节点个数的方差f3表示类内节点的数量均衡程度，希望各个类内的节点数量均衡，方差表示均衡的差异性，因此聚类内节点个数的方差f3越小越好，综上所述，多目标转化为但目标之后，评价函数f的值应该越小越好。

资源聚类结合超图理论，就是比较资源超图中的各超边的权值，即综合性能值，应用遗传算法，将权值相近的超边进行合并，权值相差较大的超边进行分解，经过不断的超边合并分解，最终形成资源聚类超图。追求类内距离小，类间距离大，即超边内节点性能距离小，各超边权值性能距离较大，且各聚类内节点个数均衡。

3.2 遗传算法聚类

遗传算法聚类以资源节点ID编码，交叉时，为了避免实数编码产生后代的不合法性，采用部分映射交叉（PMX）。变异时，变异位的取值范围不包含其基因中其他位，即染色体X=（x1，x2，…，xn），变异位为xk（1≤k≤n），变异范围U=[1,N]，N为资源ID，且｛x1，x2，…，xk-1，xk+1，…,xn｝∉U。选择时，采用轮盘赌的方式，轮盘赌公式见式（9），采用父代子代一起选的方式。不断循环，直至染色体收敛。

经过遗传算法聚类后见图2，每个类称为超边，类内节点即为超边内节点，类心的综合性能值代表其所在超边内所有节点综合性能值的均值，类心还能显示其所在超边内是否有有效资源，所有类心形成另一条超边，即上层超边，称为超树。调度时，首先检索超树内的节点，再检索该类心所在超边的节点。

4 调度策略

针对大规模网格计算，先将资源节点进行聚类，聚类后各个聚类中心形成顶层超树。调度时，在超树中寻找有有效资源的综合性能值高的节点，然后在此节点所在聚类中寻找负载低的资源进行调度。

任务预计完成时间（ACT）包括传输时间、等待时间和执行时间三者之和。任务传到资源的时间（TM）是任务计算量与资源的通信能力的比值。等待时间（WT）是任务总计算量与资源处理能力的比值，这里的任务包括等待列队中的任务和已经与资源匹配但是还未传到资源上的任务[5]。任务的执行时间（ET）是任务计算量与资源处理能力之比。

因此，任务rvi在资源vj上的预计完成时间，见式（10）。

Makespan为任务的最优跨度，即任务的最大完成时间，见式（11）。

资源聚类在调度前只需执行一次，因此资源聚类预处理可以有效减少资源查找时间，从而减少调度时间，而且给资源设定负载阈值，还可以有效均衡资源负载。

5 仿真分析

假设当资源数为1 000时，聚类数为100时，在任务数不同的情况下，对比MORC算法和Min-min算法的makespan、runtime、加速度Speedup和资源利用率P，见图3。

由图3（a）可以看出任务数在3 000以内时，随着任务数的增加，MORC算法和Min-min算法的makespan都在不断增加，但是可以明显看出两种算法的makespan前者小于后者。由图3（b）可以看出runtime随着任务数的增加而增加，但MORC算法的整体runtime都要小于Min-min算法。图3（c）是任务数不同时，加速度Speedup的比较，Speedup是体现调度算法性能优劣的重要指标，表示串行执行时间与并行执行时间的比，并行执行时间越小则加速度Speedup越大，因此可以明显看出MORC算法的调度性能较好。图3（d）是资源利用率的比较结果，资源利用率是资源利用程度的性能指标，资源利用率越接近于1，表明资源的利用程度越广，由图可知MORC算法在资源利用程度上较优。经过以上4个图的详细分析，不论从任务最大完成时间makespan、调度时间runtime、算法加速度Speedup和资源利用率P这4个方面中的哪个方面来看，本文所设计的多目标最优资源聚类的网格调度算法MORC在各方面都要优越于Min-min算法。

6 结语

本文设计的一种多目标最优资源聚类网格调度方法MORC，针对元任务调度，资源首先进行多目标最优预先聚类，在此前提下设计了一种以最小调度时间为主要目标，并兼顾负载均衡的网格任务调度算法，在调度时间、资源利用率、负载均衡方面均有较大提高。