计算网格资源管理优化技术和相关算法研究
境的适应性。
(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=[sTgT]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)获选集群和
任务提交节点间的总网络延迟应尽量小，即：
其中tj为全局标识为j的集群的延迟；
(3)HRMM为每个用户规定了计算资源占用量的上限，即：
其中W为该用户对计算资源占用量的上限，且W>0。
综合考虑上述三方面，局部资源分配可以描述为如下二次规划问题：
其中C是可以改变的加权系数，且C>0。由于f(i)为离散值且取值范围有限，因此提出以下优化方法，通过较少的计算来搜索近似的最优解。记候选集群组为ClusterList，则算法表示如下：
STEP1．对每个任务和候选集群，将静态和动态资源信息组合为综合资源信息；
STEP2．删除ClusterList中不满足总和资源需求的集群；
STEP3.，计算每个集群i,j的局部损失Cost[i,j]:=‖vi,j-ri‖+C·tij；
STEP4．并行地对Cost的每一列排序，并按从小到大的次序重排ClusterList中的集群链表；
STEP5．如果，则报告不存在满足条件的解，算法结束；
STEP6．∨i∈[1,n],并行计算Cost*[i]：=‖vi,k-ri‖+C·ti,k，其中k=aramin(‖vi,j‖<‖vi,1‖)；
STEP7．∨i∈[1,n]，并行计算d(i]：=
STEP8．置b:=argmin(d[j])，并删除ClusterList中任务b的集群链表中前k-1个集群节点；
STEP9．如果满足则转STEPl0，否则转STEP6；
STEP10．∨i∈[1,n]，将第i个任务分配给ClusterList中 《计算网格资源管理优化技术和相关算法研究(第2页)》
本文链接地址：http://www.oyaya.net/fanwen/view/174426.html
(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=[sTgT]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)获选集群和
任务提交节点间的总网络延迟应尽量小，即：
其中tj为全局标识为j的集群的延迟；
(3)HRMM为每个用户规定了计算资源占用量的上限，即：
其中W为该用户对计算资源占用量的上限，且W>0。
综合考虑上述三方面，局部资源分配可以描述为如下二次规划问题：
其中C是可以改变的加权系数，且C>0。由于f(i)为离散值且取值范围有限，因此提出以下优化方法，通过较少的计算来搜索近似的最优解。记候选集群组为ClusterList，则算法表示如下：
STEP1．对每个任务和候选集群，将静态和动态资源信息组合为综合资源信息；
STEP2．删除ClusterList中不满足总和资源需求的集群；
STEP3.，计算每个集群i,j的局部损失Cost[i,j]:=‖vi,j-ri‖+C·tij；
STEP4．并行地对Cost的每一列排序，并按从小到大的次序重排ClusterList中的集群链表；
STEP5．如果，则报告不存在满足条件的解，算法结束；
STEP6．∨i∈[1,n],并行计算Cost*[i]：=‖vi,k-ri‖+C·ti,k，其中k=aramin(‖vi,j‖<‖vi,1‖)；
STEP7．∨i∈[1,n]，并行计算d(i]：=
STEP8．置b:=argmin(d[j])，并删除ClusterList中任务b的集群链表中前k-1个集群节点；
STEP9．如果满足则转STEPl0，否则转STEP6；
STEP10．∨i∈[1,n]，将第i个任务分配给ClusterList中 《计算网格资源管理优化技术和相关算法研究(第2页)》
★读了本文的人也读了：