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

 摘要：在对现有的网格资源管理模型进行分析和比较的基础上，提出了一种基于分层结构的具体模型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描述的任务组后，立刻进行分