摘要：在对现有的网格资源办理模型进行剖析和比较的基础上，提出了一种依据分层结构的详细模型HRMM，将资源办理分为作业并行剖析、大局资源分配、部分资源分配和本地资源办理四个层次，并为每个层次规划了相应的优化战略和算法。该模型对资源办理的最大核算杂乱度为O(n2)~O(n3)，是一个优化而有用的网格资源办理模型。
核算网格是近年鼓起的一种重要的并行散布式核算技术，其关键技术之一是对网格中的资源进行办理。网格中的资源具有广域散布、异构和动态的特性，使得网格资源办理变得很杂乱。当时还没有一种模型能够处理一切的网格运用需求。现在，网格资源办理模型首要分为分层模型、笼统一切者模型和经济／商场模型三类。Globus项目组在网格协议拟定上有重要发言权，包含IBM、Microsoft、Sun、Compaq、SGI、NEC在内的很多重要公司都宣告支撑Globus Toolkit。因而Globus所选用的分层模型代表了网格资源办理的发展趋势。
本文在Globus分层模型规划思维的基础上提出一种优化的网格资源办理模型HRMM(Hierarchical Resource Management Model)，并给出了相应的资源办理算法。为了进步功率，在HRMM的首要模块中运用了Globus Toolkit 2．4供给的数据结构和接口。
1 HRMM的全体结构
HRMM的规划思维是：动态接纳来自用户的作业恳求，并为该作业分配契合条件的核算资源，一起供给整个核算过程中有关资源信息的在线反应，承受用户的在线操控。HRMM的体系结构如图1所示，将核算网格的资源办理使命分为四个层次：作业并行剖析、大局资源分配、部分资源分配和本地资源办理。
由图1可见，用户经过GUI(图形用户界面)向HRMM提交作业恳求，作业并行剖析器接纳用户的作业恳求，再按最大并行度将作业中的使命区分为若干使命组，提交给大局资源分配器。对多使命组中的每个使命，大局资源分配器在静态资源库中一次查找多个满意该需求的集群，组成候选集群组提交给部分资源分配器。部分资源分配器在动态资源库中读取候选集群组中每个集群的有关信息，并将相应使命分配给最契合条件的集群。然后，该集群运用本地资源办理器履行使命。在全体上，本地资源办理器每隔必定时刻向静态资源库发送静态资源更新信息。别的，部分资源分配器读取动态资源库前，动态资源库会从本地资源办理器读取更新信息。
在这个分层模型中，一方面，用户提交的作业能够以最大的并行度履行，然后高效表现了并行核算的思维；另一方面，选多个集群组成候选集群组，再确认其间某一分配资源的计划，因为归纳考虑了使命的静态需求和动态需求，防止重复的查询操作，然后进步了资源分配的功率。
2 作业并行剖析器
如图1所示，用户经过GUI向作业并行剖析器提交作业恳求。这个恳求包含该作业中所含的多个使命的相关信息、使命间的依靠联系及每个使命的核算资源需求。作业并行剖析器剖析该作业中的使命及彼此联系，依据各使命的依靠联系将作业中的使命区分为不同的使命组，并对每个使命组进行恰当描绘后提交给大局资源分配器。
2．1 作业的拓扑表明
一个作业由一个或多个使命组成。作业的拓扑界说为一个满意如下条件的有向无环图：该图的节点与作业中的使命一一对应；若使命B直接依靠于使命A，则存在一条由节点A到节点B的有向边，称A为B的直接前驱，B为A的直接后继；假如存在一条从A到B的由多条有向边组成的有向通路，则称A为B的前驱，B为A的后继。
图2表明一个作业的拓扑结构。设该作业由标记为A~G的7个使命及其彼此联系组成。如图2所示，使命D需求在使命A和B完成后才干开端，而使命G有必要在使命正和F完成后才干开端。
为了进步作业的并行履行功率，需求重视使命在拓扑界说中的深度。记使命T的直接前驱集合为Pd(T)，则其深度d(T)为：
若Pd(T)=φ，则d(T)=1；
若Pd(T)≠φ，则d(T)=max {d(R)}+1．
R∈Pd(T)
2．2 作业的最大并行度区分
作业的并行区分是指：一个作业拆分后构成的一系列对应每个使命、前后有序且彼此独立的使命组。一个作业能够有一个或多个并行区分计划，构成该作业对应的并行区分集，记作Θ，I(Θ)为Θ中的使命组数。 称为作业的最大并行度区分，假如：E∈Θ,且 ξ∈Θ。I（ ）≤I（ξ）将作业中的多个使命依照相应的深度进行区分，构成一个最大并行度区分。如图2中的作业，其最大并行度区分为： ={(A，B)，(C，D，E)，F，G}。
3 大局资源分配器
大局资源分配器接纳到以RSL描绘的使命组后，马上进行剖析和解说，取得每个使命的静态资源需求。体系依据每个使命的资源需求在静态资源库中查找满意条件的多个集群，并将成果提交给部分资源分配器。
3．1 静态资源库
体系中的静态资源库选用依据轻量目录拜访协议LDAP结构。在HRMM模型中，网格体系的一切静态资源都在LDAP服务器的DIT(目录信息树)中建立了相应的目录项，并用特点，值>的组合描绘各种资源特点。静态资源库挑选LDAP能够在功能上带来以下长处：
(1)LDAP专门对读操作进行了优化，在读操作频频的情况下，能够进步读取功率。
(2)LDAP是跨渠道协议，可在任何核算机上运用。然后添加体系对异构网格环境的适应性。
(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)获选集群和使命提交节点间的总网络推迟应尽量小，即：
其间tj为大局标识为j的集群的推迟；
(3)HRMM为每个用户规则了核算资源占用量的上限，即：
其间W为该用户对核算资源占用量的上限，且W>0。
归纳考虑上述三方面，部分资源分配能够描绘为如下二次规划问题：
其间C是能够改动的加权系数，且C>0。因为f(i)为离散值且取值规模有限，因而提出以下优化办法，经过较少的核算来查找近似的最优解。记候选集群组为ClusterList，则算法表明如下：
STEP 1．对每个使命和候选集群，将静态和动态资源信息组合为归纳资源信息；
STEP 2．删去ClusterList中不满意总和资源需求的集群；
STEP 3. 
，核算每个集群i,j的部分丢失Cost[i,j]:=‖vi,j-ri‖+C·TIj；
STEP 4．并行地对Cost的每一列排序，并按从小到大的次第重排ClusterList中的集群链表；
STEP 5．假如
，则陈述不存在满意条件的解，算法完毕；
STEP 6．∨i∈[1,n],并行核算Cost*[i]：=‖vi,k-ri‖+C·TI,k，其间k=aramin(‖vi,j‖‖vi,1‖)；
STEP 7．∨i∈[1,n]，并行核算d(i]：=
STEP 8．置b:=argmin(d[j])，并删去ClusterList中使命b的集群链表中前k-1个集群节点；
STEP 9．假如满意
则转STEPl0，不然转STEP6；
STEP 10．∨i∈[1,n]，将第i个使命分配给ClusterList中相应使命集群链表中的第一个集群，算法完毕。
该算法为资源分配查找到了近似的最优解，并在最大程度上利用了资源办理站点地点集群的核算资源，将大部分核算并行化。设资源办理站点地点集群的节点数为户，则该算法在每个节点上的核算杂乱度为O(n2n／P)O(N3)；假如在大局资源分配器中设置N≈P户，则核算杂乱度为O(n2)。
5 剖析与总结
本课题组选用依据分层模型的结构，将资源办理分为四个层次，然后在每个层次对模型的功能做出优化并提出了相应的算法。从全体上，HRMM对一个作业进行资源办理的最大核算杂乱度不超越O(n3)，是一个优化而有用的网格体系资源办理模型。
