（计算机科学与技术专业论文）数据挖掘网格中作业分配与调度关键技术研究.pdf

北京邮电大学博士学位论文摘要 数据挖掘网格中作业分配与调度关键技术研究 摘要 数据挖掘网格是一种专用网格，它是数据挖掘技术与网格技术的 有机结合，主要用来解决面向海量数据的、高计算能力要求的数据挖 掘问题，它能够在动态变化的多个网格节点间共享资源和协同解决面 向各领域的智能分析问题。 由于数据挖掘应用本身的复杂性和网格的异构性、动态性，使得 数据挖掘网格具有自己的特点，它的很多关键技术还有待进一步研 究，作业分配与调度技术便是其一作业分配与调度的核心功能是识 别作业的资源需求，查询、分配、调度和监视资源，以尽可能高效地 利用资源，提高整个网格系统的性能，保证资源使用者和提供者的利 益。作业的分配与调度分为三个阶段：资源发现、资源分配和任务调 度，这是一个完整的过程，本文围绕该过程所涉及到的关键技术，对 分配与调度架构、作业与调度建模、资源发现、资源分配和定价策略 等方面进行了系统而深入的研究。 论文的主要工作和贡献归纳如下： l 、提出一种基于可变结构p e t r i 网的作业模型 作业分配、调度和运行过程的形式化描述有助于过程的正确性检 验、性能评价和优化。根据数据挖掘网格中作业分配与调度的需求和 特点，论文中提出了一种基于可变结构p e t r i 网的作业模型和相应的 作业调度模型。它们不仅能够对作业分配与调度的过程和作业运行过 程进行精确定义，还能对整个过程进行各种正确性和性能分析，以处 理作业在使用数据挖掘网格中的动态、分布式资源时所产生的冲突、 异常等问题。论文对各粒度作业之间的分解规则进行了详细定义，并 通过设计变迁树来分析作业网的性能和优化作业的分配过程。 2 、提出了一种基于兴趣组的分布式信息服务 资源发现是作业分配与调度中必不可少的阶段。论文中提出了一 种基于兴趣组的信息服务，它为作业分配与调度提供可靠、高效的资 源信息管理与发现服务。该信息服务采用了信息备份和邻居分类机制 北京邮电大学通信软件工程中心 北京邮电人学博士学位论文 摘要 来有效地缩短查询距离，提高查询的成功率和保证系统的连通性。实 验结果表明，基于兴趣组的信息服务适合于大规模的、可靠性要求高 的网格系统。 3 、提出了一种基于性价比的资源分配机制 资源分配从可用资源集中为各个任务选择最合适的资源或资源 集，并为它们分配具体的工作量，它是作业分配与调度的重要组成部 分。论文中提出了一种基于性价比的资源分配机制，该分配机制在满 足任务时限和预算的前提下，使资源使用者在使用资源时达到个体的 效用最大化。实验分析表明基于性价比的分配在实现了用户使用资源 效用最大化的同时，在分配成功率、时间和费用优化方面也取得了不 错的效果。 4 、提出了一种基于资源负载预测和任务分类的动态价格机制 在作业分配与调度过程中，除了要保证资源使用者的利益外，还 要保证资源提供者的利益，并能实现系统资源的负载平衡。论文中提 出了一种基于资源负载预测和任务分类的动态价格机制。该机制基于 预测所得的资源未来负载和需求价格弹性理论提前对资源和任务进 行价格调整。论文中通过实验来验证了该机制的效果，结果表明该机 制不仅可以促进系统负载达到均衡，还可以有效地保障资源提供者的 利益。 关键词：数据挖掘网格，作业分配与调度，作业建模，资源发现，动 态价格，性价比 北京邮电人学通信软件t 程中心 北京邮电大学博士学位论文 r e s e a r c ho nk e yt e c h n o l o g i e so fj o b a l l o c 棚o na n ds c h e d u l i n gi nd a = i ：am i n i n g g l u d d m g ( d a t am i n i n gg r i d ) i sas p e c i a lg r i da n di ti n t e g r a t e sg r i d t e c h n i q u e sw i t hd a t am i n i n gt e c h n i q u e s d m gi su s e dt os o l v et h ed a t a m i n i n gp r o b l e m sw i t hm a s s i v ed a t aa n dh i g l lc o m p u t i n gr e q u i r e m e n t s d m gh a so w nc h a r a c t e r i s t i c sb e c a u s eo ft h ec o m p l e x i t yo fd a t am i n i n g a p p l i c a t i o na n dt h ed y n a m i ca n dh e t e r o g e n e o u sc h a r a c t e r i s t i c so fg r i d t h e r ea r em a n yk e yt e c h n i q u e sn e e df u r t h e ri n v e s t i g a t i o n ，o n eo fw h i c hi s j o ba l l o c a t i o na n ds c h e d u l i n g j o ba l l o c a t i o na n ds c h e d u l i n gi su s e dt o i d e n t i f yr e s o u r c er e q u i r e m e n t s ，f i n da n da l l o c a t er e s o u r c e s ，s c h e d u l ea n d m o n i t o rj o b s i ta i m st om a k ef u l lu s eo fg r i dr e s o u r c e sa n di m p r o v et h e e f f i c i e n c yo ft h ew h o l eg r i ds y s t e m t h ep r o c e s so fj o ba l l o c a t i o na n d s c h e d u l i n g i s c o m p o s e do ft h r e es t e p s ：r e s o u r c ed i s c o v e r y , r e s o u r c e a l l o c a t i o na n dj o bs c h e d u l i n g f o c u s i n go nt h ek e yt e c h n i q u e so fj o b a l l o c a t i o na n ds c h e d u l i n gi nd m g , t h i sp a p e rm a k e si n d e p t hr e s e a r c h e s o nt h et e c h n i q u e so fs c h e d u l i n gf r a m e w o r k , j o bm o d e l i n g , i n f o r m a t i o n s e r v i c e ，r e s o u r c ea l l o c a t i o n ，p r i c i n gm e c h a n i s m sa n dj o bs c h e d u l i n g t h em a i nw o r k sa n dc o n t r i b u t i o n so ft h i sp a p e ra r es h o w na s f o l l o w s ： ( 1 ) aj o bm o d e lb a s e do nap e t r in e tw i t hc h a n g e a b l es t r u c t u r ei s p r o p o s e d 1 1 1 cf o r m a ld e s c r i p t i o nf o rt h ep r o c e s so fj o ba l l o c a t i o na n d s c h e d u l i n gi sh e l p f u lt ov a l i d a t e ，a n a l y z ea n do p t i m i z et h e s ep r o c e s s e s a c c o r d i n gt ot h er e q u i r e m e n t sa n dc h a r a c t e r i s t i c so fj o ba l l o c a t i o na n d s c h e d u l i n gi nm a r k e t o r i e n t e dd m gt h i sp a p e rp r o p o s e saj o bm o d e l b a s e do nap e t r in e tw i t hc h a n g e a b l es t r u c t u r ea n dac o r r e s p o n d i n g s c h e d u l i n gm o d e lb a s e do nah i e r a r c h i c a lc o l o rp e t r in e t 砀e yd e f i n et h e 北京邮电大学通信软件工程中心 i l l 北京邮电大学博士学位论文 a b s t r a c t p r o c e s so fj o ba l l o c a t i o na n ds c h e d u l i n gs t r i c t l ya n dp r o v i d em e t h o d st o v a l i d a t e ，a n a l y z ea n do p t i m i z et h e s ep r o c e s s e s 。w ev a l i d a t et h el i v e n e s s a n dr e a c h a b i l i t yo ft h es c h e d u l i n gm o d e la n dt h ej o bm o d e lb ya n a l y z i n g t h e i rr e a c h a b i l i t yt r e e s at r a n s i t i o nt r e ea l g o r i t h mi sa l s op r e s e n t e dt o a n a l y z et h ec o s ta n d t i m ep r o p e r t i e so fj o bn e t ，w h i c hc a nb eu s e df o rt h e o p t i m i z a t i o no fr e s o u r c ea l l o c a t i o n ( 2 ) a ni n f o r m a t i o ns e r v i c eb a s e do ng r o u po fi n t e r e s tm e c h a n i s m i s p r o p o s e d r e s o u r c ed i s c o v e r yi sn e c e s s a r yf o rj o ba l l o c a t i o na n ds c h e d u l i n g t h i sp a p e rp r o p o s e san o v e li n f o r m a t i o ns e r v i c eb a s e do ng r o u po f i n t e r e s t ( g o i ) m e c h a n i s m , w h i c ha d o p t s i n f o r m a t i o n b a c k u p a n d n e i g h b o rc l a s s i f i c a t i o nm e c h a n i s m st op r o v i d et h er e l i a b l ea n de f f i c i e n t r e s o u r c ed i s c o v e r yf o rj o ba l l o c a t i o na n ds c h e d u l i n g e x p e r i m e n t a l r e s u l t ss h o wi ts u i t sl a r g e s c a l ea n dr e l i a b i l i t y b a s e dg r i d ( 3 ) ar e s o u r c ea l l o c a t i o nm e c h a n i s mb a s e do nc o s t - p e r f o r m a n c e r a t i oi sp r o p o s e d r e s o u r c ea l l o c a t i o ns e l e c t st h e p r o p e r r e s o u r c e sf o rt a s k sa n d a s s i g n st h ep r o p e rw o r k l o a df o rt h e m i ti s a ni m p o r t a n tp a r to fj o b a l l o c a t i o na n ds c h e d u l i n g t h i sp a p e rp r o p o s e sar e s o u r c ea l l o c a t i o n m e c h a n i s mb a s e do nc o s t p e r f o r m a n c er a t i of o rc o m m e r c ee n v i r o n m e n t s ， w h i c hc a ns a t i s f yt h er e q u i r e m e n t so fj o b sa n dl e tr e s o u r c eu s e r sh a v et h e m a x i m a lc o s t - e f f i c i e n c y t h ea n a l y s i ss h o w st h em e c h a n i s mc a ng e tt h e m a x i m a lc o s t e f f i c i e n c yw h e nu s e r su s er e s o u r c e sa n do p t i m i z et h ec o s t a n dt i m eo ft a s k sa tt h es a m et i m e ( 4 ) ad y n a m i cp r i c em e c h a n i s mb a s e do nd e m a n dp r e d i c t i o na n d t a s kc l a s s i f i c a t i o ni sp r o p o s e d i nt h ep r o c e s so fj o ba l l o c a t i o na n ds c h e d u l i n g ，b e s i d e sc o n s i d e r i n g t h eb e n e f i t so fr e s o u r c eu s e r s ，w en e e dt oe n s u r et h eb e n e f i t so fr e s o u r c e p r o v i d e r sa n db a l a n c er e s o u r c el o a d s t h i sp a p e rp r o p o s e sad y n a m i c p r i c em e c h a n i s mb a s e do nd e m a n dp r e d i c t i o na n dt a s kc l a s s i f i c a t i o n ， w h i c ha d j u s t st h ep r i c e so fr e s o u r c e sa n dt a s k si na d v a n c ea c c o r d i n gt o p r e d i c t e d r e s o u r c el o a d sa n dd e m a n dp r i c e e l a s t i c i t y r a t i o 北京邮电大学通信软件工程中心 北京邮电大学博士学位论文 e x p e r i m e n t a lr e s u l t ss h o wt h em e c h a n i s me n s u r e s t h eb e n e f i t so f r e s o u r c ep r o v i d e r sa n dp r o m o t e sl o a db a l a n c i n ga tt h es a m et i m e k e yw o r d s ：d a t a m i n i n gg r i d ，j o ba 1 l o c a t i o na n ds c h e d u l i n g ，j o b m o d e l i n g ，i n f o r m a t i o ns e r v i c e ，d y n a m i cp r i c e ，c o s t p e r f o r m a n c er a t i o 北京邮电大学通信软件工程中心 v 北京邮电大学博士学位论文目录 2 - 1g r a m 结构 图表索引 2 - 2c o n d o r - ( ；体系结构 2 - 3g r i d b u s 中间件组件图 2 - 4w e k a 4 w s 系统结构图 8 9 2 - 5 d at a m i n i n g g ri d 的调度结构 2 - 6c g s p 模块结构图 2 7 织女星网格的资源空间模型 2 - 8 上海网格中间件体系结构 3 - 1 数据挖掘网格的体系结构 3 - 2 作业树状结构图 1 0 1 0 l l 1 2 1 3 1 4 1 9 。2 0 2 0 2 l 2 3 2 3 2 4 2 4 2 4 2 5 2 5 2 6 。2 6 勰 2 9 3 0 3 2 。3 3 3 4 3 4 4 1 3 - 3 作业描述中复杂类型定义 3 - 4 作业元素的结构 3 - 5 子作业元素的结构 3 - 6 子任务元素的结构 3 - 7 参数元素的结构 3 - 8 预算元素的结构 3 - 9 时间约束元素的结构 3 - 1 0 并行计算标志元素的结构 3 - 11 并行计算约束元素的结构 3 - 1 2 资源描述元素的结构 3 - 13 子任务进展描述元素的结构 3 - 1 4 子作业关系元素的结构 3 - 1 5 客户流失分析描述实例 3 - 1 6 任务描述实例 3 - 1 7 子任务描述实例 3 - 1 8 分配与调度框架图 3 1 9 分配过程中模块交互序列图 3 - 2 0 状态查询过程中的模块交互 3 - 2 1 付费过程中的模块交互 4 - 1 变迁的变化约束 4 - 2 作业调度网 4 - 3 子作业调度网 4 - 4 任务调度网 4 4 4 - 5 子任务调度网 4 - 6 传输子作业分解示意图 4 - 7 计算子作业分解示意图 4 7 。5 2 4 - 8 外部数据传输任务分解示意图 4 - 9 外部数据传输子任务结构变化示意图 4 一l o 内部数据传输任务分解示意图。 5 3 “ 5 5 5 5 5 64 - 1 1 数据可分的可并行计算任务分解示意图 4 - 1 2 数据可分的可并行计算任务结构变化示意图5 7图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图 北京邮电大学博士学位论文目录 4 - 1 3 数据不可分的可并行计算任务分解示意图。5 7 4 - 1 4 数据不可分的可并行计算任务结构变化示意图5 8 4 - 1 5 不可并行计算任务分解示意图5 8 4 - 1 6 不可并行计算任务结构变化示意图。 4 - 17 可并行计算任务结构优化示意图。 ! i 9 ! ；9 4 - 1 8 作业调度网的一个可达树示例图6 3 4 - 1 9 子作业调度网的可达树示例图6 4 4 - 2 0 子任务调度网的可迭树示例图6 5 4 - 2 1 变迁树生成算法6 6 4 - 2 2 关键路径优化和分组算法6 7 4 - 2 3 基于变迁树进行关键路径优化实例。6 8 5 - 1 信息服务结构图7 2 5 - 2g i s 节点的状态图7 4 5 - 3 信息树的结构7 5 5 - 4 兴趣组分裂示意 5 - 5 超级节点更替示意图 5 - 6g i s 节点退出算法 5 - 7 信息查询算法 7 7 。7 8 5 - 8 查询响应时间与查询问隔的关系8 1 5 - 9 查询成功率与查询跳数的关系。 5 - 1 0 查询通信量， 6 - 1 资源分配算法 8 ：1 6 - 2 资源再分配算法 7 - 1 任务定价算法 7 - 2 各天负载预测结果图 7 - 3 各天状态预测图 9 1 9 ：1 7 - 4 动态价格对负载的影响1 1 2 表4 - 1 作业调度网库所与变迁的描述 表4 - 2 子作业调度网库所与变迁的描述 表4 - 3 任务调度网库所与变迁的描述。4 6 表4 - 4 子任务调度网库所与变迁的描述 4 8 表6 - 1 初始资源集合9 2 表6 - 2 任务描述9 3 表6 - 3 基于费用分配和价格感知性价比的分配结果。9 3 表6 - 4 基于时间分配和质量感知性价比的分配结果9 4 表7 - 1 原始负载数据。1 0 6 表7 - 2 第四天预测时的状态分类1 0 8 表7 - 3 第四天各周期负载和新的资源价格。1 1 0 表7 - 4 负载预测结果。1 1 0 图图图图图图图图图图图图图图图图图图图图图图图图图图图 北京邮电大学博士学位论文声明 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同学、同事对本 研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 起珥￥图日期：迈z ：z ：! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大 学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许学位论文被查阅和借阅：学校可以公布学位论文的全部或部分内容，可 以允许采用影印、缩印或其它复制手段保存、汇编学位论文。( 保密的学位 论文在解密后遵守此规定) 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 走迅纲 日期： 导师签名： 神，7 i 1 日期：坦 ：2 ：! ! 北京邮电大学博：t 学位论文第1 章前言 1 1 研究背景和意义 1 1 1 研究背景 第1 章前言 网格【1 】是继传统因特网、万维网之后的新一代因特网环境。传统因特网实 现了计算机硬件的连通，w e b 实现了网页的连通，而网格则试图实现因特网上所 有资源的全面连通，形成对用户相对透明、虚拟的高性能计算环境，最终实现网 络虚拟环境上的资源共享和协同工作，消除信息孤岛和资源孤岛。 网格的思想起源于电力等公共设施的应用，是一种“按需所得一的运行模式。 在电力等公共设施中，当人们需要用电时只需插上插头，打开电源开关即可，对 于使用者来说，完全不必考虑电来自何方，它们只是在人们需要时，自然地出现 在人们身边就可以了。网格的思想就是想用同样的方式来获得和使用复杂的网络 资源。如同构建公共设施一样，网格以构建共享、可靠的计算系统设施为最终目 的，这个虚拟计算机平台将由各种计算资源组成，这些资源对用户是不可见的， 是透明的。网格技术最终会给人类展现“按需所得一的前景，使用网络资源就像 使用电力资源那样方便。 网格技术从提出到现在虽然已经有1 0 年多了，但由于网格技术仍然处在不 断发展变化中，所以至今没有一个确切的概念来表述它。f a nf o s t e r 2 认为网格 就是在动态变化的多个虚拟机构间共享资源和协同解决问题的平台，并且需要同 时满足三个条件：( 1 ) 在非集中控制的环境中协同使用资源；( 2 ) 使用标准、开 放和通用的协议与接口；( 3 ) 提供非平凡的服务。中科院计算所李国杰院士和徐 志伟博士【3 】认为网格把整个因特网整合成一台巨大的超级计算机，实现计算资 源、存储资源、数据资源、信息资源、知识资源、专家资源的全面共享。中国网 格专家组组长金海博士【4 】则认为网格是继万维网之后出现的一种新型网络平 台，它将实现计算资源、存储资源、信息资源、知识资源、设备资源的全面共享， 为用户提供整合各类资源的基础设施。基于这种基础设旌，用户不需要了解资源 的具体细节就可以使用资源。这是一种广义上的网格，认为任何虚拟组织之间的 协同问题求解和资源共享都可以叫做网格。虽然网格的定义不统一，但建立网格 的目的却很明确，那就是建立一个资源共享与协同计算平台，来处理具有海量数 据和高性能计算要求的应用。它是信息社会的网络基础设施，是把整个因特网整 合成一台无形的超级虚拟计算机，实现因特网上所有资源的互联、互通，完成各 类资源智能共享的一种新型的分布式计算技术。 北京邮电大学通信软件工程中心 北京邮电大学博士学位论文第1 章前言 目前很多企业、科研院所和高校对网格技术进行了研究，并开发出了相应的 系统。这些系统现在已被成功地应用到许多行业和领域，如能源【5 7 】、交通【8 1 1 】、 气象 1 2 - 1 4 1 、水利1 1 5 1 、农林 1 6 ，1 7 】、教育【1 8 ，1 9 】、环保【2 0 1 、军事 2 1 ，2 2 1 、医 疗 2 3 1 等等。 按照网格提供的功能可将网格分为通用网格和应用网格两大类。通用网格主 要侧重于平台开发，它们在网格门户、网格开发环境、信息服务、作业管理器、 服务容器、数据管理和网格安全等方面提供了基本的服务。借助于它们，用户可 以构建大型的网格平台，并可以在上面开发自己的应用。应用网格主要是针对某 一具体应用而实现的网格系统，它们一般是在特定应用需求的驱动下建立起来 的，只对某一领域的某些具体应用提供支持。应用网格可以借助通用网格平台来 构建，也可以直接在操作系统上构建。 数据挖掘 2 4 ，2 5 1 是从大量的、不完全的、驳杂的、模糊的、随机的数据中 提取隐含在其中的、人们事先不知道的，但又对决策有潜在价值的信息和知识的 过程。目前数据挖掘技术已在很多领域取得了成功，但随着数据挖掘应用变得越 来越复杂，数据量也越来越大，目前数据挖掘面临高计算量的挑战，单机或基于 集群的计算模式已满足不了高计算能力的要求【2 6 】，计算问题成了数据挖掘进一 步应用的主要瓶颈。 网格的出现，正好为数据挖掘中计算能力不足的问题提供了一条解决途径。 目前已有很多研究把数据挖掘技术与网格技术结合起来，构建起了数据挖掘系统 【2 7 3 2 1 。数据挖掘技术与网格技术的结合方式主要可分为两大类：基于网格的数 据挖掘应用和数据挖掘网格。 基于网格的数据挖掘应用是在现有通用网格平台上构建数据挖掘应用系统。 在理论上，这种结合方式简单方便，并且容易实现，因为它不用关心底层基本服 务，如信息服务、数据服务、安全和作业运行管理等等，它只需要专注于数据挖 掘应用的业务逻辑和用户接口设计。但是在目前，由于缺少真正方便、可用的网 格平台，使得这种方式的优势并不能真正实现。无论是国外最著名的g l o b u s t o o l k i t 还是国内的c g s p 网格平台都过于复杂，并且安装和维护都十分困难， 所有这些都使得基于它们的应用系统不容易被部署和推广。 数据挖掘网格是北京邮电大学网格小组 3 3 1 研发出的一种数据挖掘系统。它 是按照网格思想从底层基本服务到上层应用构建的一个完整的应用网格，它解决 面对海量数据的、高计算能力要求的数据挖掘问题，它能够在动态变化的多个网 格节点间共享资源和协同解决智能分析问题。数据挖掘网格的优点是可以不借助 任何网格平台，直接在操作系统上构建数据挖掘系统，而且它是一种专用网格， 整个系统复杂度低，利于在各种环境下部署和推广。根据网格技术发展的趋势来 北京邮电大学通信软件工程中心 2 北京邮电大学博士学位论文 第1 章前言 看，在目前阶段，这种方式更现实一点，它有利于快速开发出可用的系统，让用 户真正体会到网格给他们带来的方便和好处，从而更进一步推动网格技术的发 展。 本文的研究工作是数据挖掘网格的主要研究工作之一，它对数据挖掘网格中 作业分配与调度的关键技术进行了深入地研究。 1 1 2 研究目的和意义 在数据挖掘网格环境中，每个用户作业中的数据挖掘任务都可能面临着多种 资源选择，用户作业中各任务间的关联在某种程度上可映射为资源之间的依赖关 系，不同的资源配置将产生不同的作业满意度，由此产生了作业分配与调度问题。 作业分配是指根据作业中各任务的要求，查询各种可用资源集，然后从中为各任 务选择最合适的资源或资源集，使得各任务在时限和预算内完成的同时，实现最 大的任务满意度。由此可见，作业分配分为两个阶段：资源发现阶段和资源分配 阶段。资源发现是指根据用户作业中各任务的要求，在网格系统中查询各种可用 资源集的过程。资源分配是指从可用资源集中选择最合适的资源或资源集，并把 它们分配给各任务的过程。数据挖掘网格中，作业调度是指在作业运行过程中， 对各任务进行状态监控，并对产生异常的任务进行再分配，保证任务的顺利进行 作业调度有两个目的，一个是作业运行监控，另一个是错误恢复，即对产生异常 的任务进行再分配。作业分配与调度虽是两个过程，但它们是紧密联系的，因为 调度过程中的主要工作就是根据需要对任务进行重新分配，它们的目标都是尽量 保证作业按照用户要求顺利进行，所以在数据挖掘网格中把它们作为一个整体来 研究。作业分配与调度所使用的各种机制和算法都将对系统的整体性能产生直接 影响，它是数据挖掘网格的关键组件之一 通用网格的重点是网格平台开发，它们在作业分配与调度方面一般只实现基 本的功能，如作业的远程提交和作业运行时管理等等。它们一般不提供作业分配 与调度的优化策略，它们只是为作业分配与调度提供了各种底层接口，不同的应 用可以根据自己的需要在上面开发满足自身要求的作业分配与调度组件。 在传统的分布式数据挖掘系统中，作业管理、分配与调度【3 4 】是在单台计算 机或小规模局域网范围内进行的，对资源有完全的控制，不用关心系统在运行过 程中通信所花费的开销，可在封闭的空问内实现高效的集中管理和调度。 数据挖掘网格是数据挖掘技术与网格技术的结合，由于网格系统具有广域 性、异构性、动态性和管理复杂等特点1 3 5 1 ，同时，数据挖掘网格应用多集中于 解决规模庞大的计算问题，这些问题可能在任何一个单一的超级计算机上都无法 得到解决，而是需要同时使用多台计算机上的多种异构资源。因此，数据挖掘网 ：l l - ：g l t g l g ) k - 翱瓣魂中心 3 北京邮电大学博上学位论文第1 章前言 格中的作业管理、分配与调度是在开放的广域网内进行，对资源无完全的集中控 制，对资源的状态变化和网络波动不可预料，且存在大量的异构资源以及不同的 价格管理策略，所有这些因素都使得作业的管理与分配变的更加复杂，同时也使 得传统分布式数据挖掘系统中的作业管理与分配机制无法胜任数据挖掘网格系 统的资源管理与作业调度。 本文对数据挖掘网格中作业分配与调度的关键技术进行了深入地研究，旨在 为实现数据挖掘网格的作业分配与调度提供理论上的指导。本文采用分层着色 p e t r i 网技术来建立一种分层的作业调度模型，使各粒度调度元素之间松耦合， 从而可以被方便地在网格环境下部署，同时便于调度器对不同粒度的作业元素进 行管理；采用可变结构p e t r i 网技术对作业进行建模，使其能根据资源分配结果 和任务实时情况对结构进行动态修改，同时支持子任务的动态合并与分裂，支持 任务的异常处理；采用信息备份和邻居分类机制来建立基于兴趣组的信息服务， 使其为作业分配与调度提供可靠的、高效的资源发现；采用基于性价比的资源分 配机制，在满足任务时限和预算的前提下，实现资源使用者的最大效用；采用一 种基于负载预测和任务分类的动态价格机制，来保证在资源分配过程中资源提供 者的利益和促进系统资源的负载平衡。 在理论上，本文提出了一个数据挖掘网格中基于市场机制的作业分配与调度 框架，并对其关键技术进行了研究，它为研究数据挖掘网格中作业分配与调度技 术提供了借鉴，同时也促进了数据挖掘网格作业分配与调度技术的发展。在实践 中，该研究能够指导具体系统的实现和实施，通过把整个或部分研究成果应用到 项目、工程中，能够提高整个系统的可靠性、可用性和运行效率。 1 1 3 主要研究内容 本文是作者在博士研究生在读期间参加的多个项目的经验总结与提炼。与论 文工作直接相关的项目包括北京市教委共建项目“基于网格技术的多媒体教育资 源应用平台 ( 编号：s y s l o o l 3 0 4 2 2 ) 的两期工作：f r p 数据网格研究和面向电 信的数据挖掘网格研究。这些项目为本文的作业分配与调度研究工作提供了直接 支持。数据挖掘网格中，作业分配与调度的核心功能是识别作业的资源需求，查 询、分配、调度和监视资源，以尽可能高效地利用资源，提高整个网格系统的性 能。作业分配与调度分为三个阶段，即资源发现、资源分配和任务调度，这是一 个完整的过程。本文围绕该过程所涉及的关键技术，对分配与调度架构、作业与 调度建模、资源发现、资源分配和价格策略等方面进行了系统而深入地研究，主 要研究内容如下： 1 、研究数据挖掘网格中分布式作业分配与调度架构。针对数据挖掘网格中 北京邮电大学通信软件丁程中心4 第1 章前言 的应用具有高计算量和数据传输量大的特点，设计一种分层的作业管理、分配与 调度框架来提高网格作业的运行效率和资源管理性能。 2 、研究数据挖掘网格中的作业与调度建模技术。采用动态的分层着色p e t r i 网对数据挖掘网格作业分配与调度过程进行建模；采用可变结构p e t r i 网对数据 挖掘网格中的作业过程进行建模；通过可达树来验证作业与调度模型结构的合理 性；设计变迁树算法来分析作业网的性能和优化资源分配过程。 3 、研究资源的信息管理和发现技术。引入兴趣组概念，设计信息备份和邻 居分类机制，来提高信息服务的可扩展性、可靠性和高效性，从而提高作业分配 与调度的可靠性和高效性：文中通过实验来验证信息服务的效率。 4 、研究资源分配机制。从资源使用者的角度来设计资源分配机制，使得用 户在使用资源时达到效用最大化。研究资源性价比的定义和基于性价比的资源分 配模型，同时设计一种作业分配、调度与再分配动态结合的算法来保证任务顺利 进行。通过实验来分析各种任务在同一资源集上的分配结果，从而分析该分配机 制的优缺点和适用场景。 5 、研究数据挖掘网格中资源和任务的动态价格机制。从资源提供者和系统 负载平衡的角度来研究资源和任务的定价问题，使得在资源分配过程中能促进资 源负载均衡的同时，还可以尽可能地保证资源提供者的利益，达到利益分配均衡。 研究基于马尔可夫链的资源负载预测方法，并依据负载预测结果研究资源价格调 整策略和任务定价方法。通过仿真实验对该动态价格机制进行验证 1 2 论文结构 本文的章节安排如下： 第一章，绪论。阐述了研究数据挖掘网格中作业分配与调度的背景和研究意 义，以及本论文的主要内容。 第二章，相关研究综述。介绍了当前主要的网格项目以及它们的作业分配与 调度技术研究现状，重点分析了与数据挖掘相关的网格项目，总结了它们在作业 调度与分配方面的特点。 第三章，作业分配与调度框架设计。介绍了数据挖掘网格的体系结构，分析 了它在作业分配与调度中的功能需求，定义了一种数据挖掘网格作业描述方法， 设计了一种基于分层结构的作业分配与调度框架，并对其模块功能、动态特性和 交互关系等进行了描述，它是作业建模、信息服务设计和分配与调度优化等下一 步工作的基础。 第四章，基于p e t r i 网的作业与调度模型。本章讨论作业与调度的建模问题。 5 北京邮电大学通信软件工程中心 北京邮电大学博士学位论文第1 章前言 提出了一种四层作业调度模型，并基于可变结构p e t r i 网技术对数据挖掘网格作 业进行建模和分析。文中通过可达树来验证作业与调度模型的结构正确性，并通 过设计变迁树算法来分析作业的性能和优化资源分配过程。 第五章，基于兴趣组的信息服务。本章讨论资源信息管理与发现问题。提出 一种基于兴趣组的信息服务机制用于资源的信息管理和发现。该机制重点在信息 服务的可靠性和连通性方面作了改进，使其能更好地为作业分配与调度服务。文 中通过实验来验证了信息服务的效率。 第六章，基于性价比的资源分配机制。本章讨论如何为资源使用者分配合适 的资源或资源集，来保证任务顺利完成的同时，实现资源使用的最大效用。文中 提出了一种资源分配机制，该机制根据任务的不同类别，定义了两类性价比和用 户使用资源的最大效用，并基于它们对分配优化问题进行了建模。最后，本章提 出了一种资源分配和再分配算法来实现我们提出的分配机制。文中通过实验来分 析各种任务在同一资源集上的分配结果，从而分析该分配机制的优缺点和适用场 景。 第七章，基于负载预测和任务分类的动态价格机制。本章讨论资源提供者如 何在资源提供过程中动态调整资源价格来保证自己利益的同时，促进资源的负载 平衡。文中提出了一种基于负载预测和任务分类的动态价格机制。该机制首先基 于马尔可夫链对系统资源未来的负载量进行了预测。然后在经济学中需求价格弹 性理论基础上给出了资源价格调整策略和任务定价方法。文中通过实验仿真的方 法来验证了该动态价格机制的效果。 第八章，总结。对论文进行了小结，并提出了进一步的研究工作。 北京邮电大学通信软件工程中心 6 北京邮电大学博上学位论文 第2 章相关研究综述 世界各国已有很多项目和文献对网格的相关技术进行了研究，这些研究各有 侧重点，涵盖了网格计算的各个方面。由于数据挖掘网格是一种新兴的应用网格， 其概念的提出到现在才不过两三年的时间，该领域研究成果的公开资料还比较 少。对于数据挖掘网格中作业分配与调度技术的研究还要更多地借鉴其它网格系 统中的技术。本章重点介绍了国内外较有影响的网格项目和它们在作业分配与调 度方面的技术，并在最后总结了作业分配与调度方面的研究现状和不足。 2 1 相关项目研发现状 2 1 1 国外现状 目前国外已有很多比较成熟的网格项目，如s e t i h o m e 3 6 ，g l o b u s 3 7 ， l e g i o n 3 8 ，h a w k e y e 3 9 ，n i m r o d g 4 0 i ，c o n d o r - g 4 1 ，n e t s o l v e 4 2 和欧洲数 据网格( e d g ) 1 4 3 等等，下面对几个比较有影响力的项目进行详细介绍。 2 1 1 1g l o b m g l o b u s 项目【3 7 】由美国a r g o n n e 国家实验室研发，是目前国际上最有影响力 的网格项目之一。在初始阶段，全美有十多所大学和研究机构参与了该项目的研 究工作。g l o b m 对信息安全、资源管理、信息服务、数据管理以及应用开发环 境等网格计算的关键理论和技术进行了广泛地研究，开发出了能在多种平台上运 行的网格计算工具包软件g t ( g l o b u st o o l k i t ) 。g t 能够用来帮助规划和组建大 型的网格试验和应用平台。自1 9 9 9 年推出g t l 0 后，相继在2 0 0 2 年推出了2