计算网格资源管理优化技术和相关算法研究

(3)LDAP服务器支持分布式的结构，静态资源库可访问本地或全局的LDAP服务器，并能很方便地实现同步，即增强资源管理的分布性。

3．2 全局资源分配算法

根据任务组中每个任务的静态需求，全局资源分配器在静态资源库中搜索满足需求的集群。在搜索时首先随机选择搜索的起始位置，然后为每个任务分别返回最先发现的N个满足该任务需求的集群，形成候选集群组，并以ClusterList数据结构描述后提交给局部资源分配器；其中ClusterList是用来描述候选集群组的广义表结构，如图3所示。对于任何一个任务，如果只找到K(<N)个符合条件的集群，则只由这K个组成候选集群组；如果任何一个集群都不满足任务的静态需求，则向局部资源分配器提交空值，同时向作业并行分析器发送反馈信息，取消任务。设LDAP服务器所记录的集群数量为M，则全局资源分配的计算复杂度为O(MN)。

4 局部资源分配器

局部资源分配器在动态资源库中搜索候选集群组的动态信息，将这些动态信息和从全局资源分配器获得的静态信息相组合并进行综合分析，最终将任务组中的每个任务分配给最适合的集群。

4．1 动态资源库

动态资源库中的数据以XML描述，带来如下优点：

(1)XML针对更新操作进行了优化。因此，对于需要不断更新的动态资源库，可有效提高效率。

(2)XML和LDAP在存储结构上都是树状结构，可以很方便地相互转化。用XML描述数据，可使动态资源库和基于LDAP的静态资源库具有更好的耦合性。

(3)XML与平台无关，以XML表示的数据可很方便地被其他程序使用。

4．2 局部资源分配策略

局部资源分配器得到候选集群组ClusterList后，从动态资源库获取每个候选集群的动态信息，并将这些动态信息添加到相应集群的静态信息之后，然后将静态资源和动态资源信息相组合，形成集群综合资源信息。设一个集群的动态资源信息为h=[h1,…，hm]T，静态资源信息为t=[t1,…,td]T，其中m和d分别为动态和静态资源描述的字段数，则集群综合信息为υ=[tThT]T=[υ1,…,υp]T，其中P=m+d。如图3所示，集群2，2的综合信息表示为υ2.2。类似地，将任务静态资源需求和动态资源组合，设一个任务的动态资源需求为g=[g1,…，gm]T，静态资源需求为s=[s1,…，sd)T，则综合资源需求为r=[sT gT]T=[r1,…，rp]T。任务i的综合资源需求表示为ri。在确定分配策略时，将只考虑任务的综合资源需求和集群的综合资源信息。

首先，为了任务能够顺利完成，最终被选择的集群必须同时满足任务的静态资源需求和动态资源需求，即满足任务的综合资源需求：

∨i∈[1,n],∨j∈[1，p]，Vi,f(i)[j]≥ri[j]

其中，n为任务组中的任务数量，p为向量u／和r的维数，f(i)为任务i的候选集群(即ClusterList中Taski对应的集群链表)中最终被选择集群的序号。因此，首先在ClusterList中删除所有不满足上述条件的集群，并记第i个任务还剩余Ki个符合综合资源需求的候选集群，其中1≤i≤n，1≤Ki≤N。最后，局部资源分配器要为每个任务Taski从Ki个候选集群中选择最合适的一个。综合考虑计算网格的整体资源分配效率，在具体选择集群时采用如下决策机制：

(1)获选集群的综合资源信息应尽量接近相应任务的综合资源需求，避免资源的浪费，即：

(2)获选集群和任务提交节点间的总网络延迟应尽量小，即：

javascript:window.open(this.src);" style="cursor:pointer;"/>

其中tj为全局标识为j的集群的延迟；

(3)HRMM为每个用户规定了计算资源占用量的上限，即：

其中W为该用户对计算资源占用量的上限，且W>0。

综合考虑上述三方面，局部资源分配可以描述为如下二次规划问题：

javascript:window.open(this.src);" style="cursor:pointer;"/>

其中C是可以改变的加权系数，且C>0。由于f(i)为离散值且取值范围有限，因此提出以下优化方法，通过较少的计算来搜索近似的最优解。记候选集群组为ClusterList，则算法表示如下：

STEP 1．对每个任务和候选集群，将静态和动态资源信息组合为综合资源信息；

STEP 2．删除ClusterList中不满足总和资源需求的集群；

STEP 3. javascript:window.open(this.src);" style="cursor:pointer;"/>，计算每个集群i,j的局部损失Cost[i,j]:=‖vi,j-ri‖+C·tij；

STEP 4．并行地对Cost的每一列排序，并按从小到大的次序重排ClusterList中的集群链表；

STEP 5．如果javascript:window.open(this.src);" style="cursor:pointer;"/>，则报告不存在满足条件的解，算法结束；

STEP 6．∨i∈[1,n],并行计算Cost*：=‖vi,k-ri‖+C·ti,k，其中k=aramin(‖vi,j‖<‖vi,1‖)；

STEP 7．∨i∈[1,n]，并行计算d(i]：=javascript:window.open(this.src);" style="cursor:pointer;"/>

STEP 8．置b:=argmin(d[j])，并删除ClusterList中任务b的集群链表中前k-1个集群节点；

STEP 9．如果满足javascript:window.open(this.src);" style="cursor:pointer;"/>则转STEPl0，否则转STEP6；

STEP 10．∨i∈[1,n]，将第i个任务分配给ClusterList中相应任务集群链表中的第一个集群，算法结束。

该算法为资源分配查找到了近似的最优解，并在最大程度上利用了资源管理站点所在集群的计算资源，将大部分计算并行化。设资源管理站点所在集群的节点数为户，则该算法在每个节点上的计算复杂度为O(n2n／P)<O(N3)；如果在全局资源分配器中设置N≈P户，则计算复杂度为O(n2)。

5 分析与总结

本课题组采用基于分层模型的结构，将资源管理分为四个层次，然后在每个层次对模型的性能做出优化并提出了相应的算法。从总体上，HRMM对一个作业进行资源管理的最大计算复杂度不超过O(n3)，是一个优化而有效的网格系统资源管理模型。