基于有向无环图的时间-费用优化调度算法.pdf

基于有向无环图的时间-费用优化调度算法.pdf

  1. 1、本文档共6页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
基于有向无环图的时间-费用优化调度算法.pdf

第31卷第3期 衡阳师范学院学报 No.3V01.31 20 1 of Normal 0年6月 JournalHengyangUniversity June.2010 基于有向无环图的时问一费用优化调度算法 王 樱1’2,李 琳2,王 杰2 (1.湖南大学计算机与通信学院,湖南长沙410082; 2.衡阳师范学院计算机科学系,湖南衡阳421008) 摘 要:在网格计算环境中,基于时间限制和费用最小的有向元环图(DAG)调度算法,运用了经济规律把网 格用户的任务映射到网格资源中运行。该文综合考虑时间、费用以及任务间的优先关系等诸多QoS需求,提出 了基于有向无环图的优化调度算法。通过仿真实例,论证了该算法的优越性。 关键词:有向无环图;网格计算;调度算法 中图分类号:TP301.6 文献标志码:A 文章编号:1673—0313(2010)03—0084—04 网格环境下任务间的依赖关系对传统的调度策略 0引言 提出了新的挑战。如何解决任务之间的优先关系? 在网格环境下,资源广域分布、异构、动态且有 有向无环图DAG是一个比较有用的工具。本文将 多个管理域,这些资源为不同的组织拥有,各组织 对DBC算法提出改进,用有向无环图DAG来表示 对资源的管理机制、策略、费用和目标都不尽相同。 任务问的依赖关系,同时考虑了时间、费用、任务间 传统调度只考虑系统性能,而忽视了用户的服务质 的依赖关系等因素,提出比较符合现实情况的基于 Greed— 量要求,如文献[1巧]介绍的OLB,UDA,Fast有向无环图的优化调度算法。 Y,Min—Min,Max-Min,Sufferage,GSA等,追求最 1优化调度算法 小Makespan是这些算法的主要目标。但这些资源 管理和调度算法均不能很好地满足实际网格环境。 1.1 算法基本思想 对网格用户而言,希望提交的任务在尽可能短的时 基于费用一时间优化的网格调度问题主要解 间内,以尽可能低的价格获得尽可能高安全可靠的 决在不增加总完成时间Makespan的基础上,减少 服务。而基于网格经济模型最有效的任务调度算 总的费用Cost。在网格环境中,一个网格应用T往 法是时间成本限制下的时间优化、成本优化调度算 往需要由多个任务协同完成。在一个由竹个任务构 法(DBC)[6{]。该算法可以简单表述为N个用户, 成的网格应用中,根据任务间的依赖关系可以生成 每个用户有M个任务,并且任务相互独立,无依赖 一个DAG图(图1所示),用户任务集合W={W。, 关系,可调度到任意资源上执行,同时每个用户都 Wz,…,W。}。从锄。到W。的有向边,表示任务硼。 有一定的终止时间和成本预算限制。然而网格计 和W。之间存在依赖关系,W。只有在W。执行完成 算[91中,一个大型的应用程序往往被分解为具有依 后才能执行。从图中可得到每个任务结点的入度 赖关系的多个任务。任务与任务之间可能存在着 和出度。如果结点的入度为0,出度大于0,则这个 优先运行的关系,在资源个体差异较大、广域互连的 结点称为源点;如果结点的人度大于0,出度为0,则 收稿日期:2010—03一01 基金项目:湖南省教育厅科研资助项目(07COl6) 作者简介:王樱(1970一),女,湖南龙山人,副教授,主要研究方向是网格计算. 万方数据 20lo年第3期

您可能关注的文档

文档评论(0)

我的文档 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档