论文研究-网格工作流调度算法研究综述.pdf

所需积分/C币:9 2019-07-22 21:33:50 259KB .PDF
收藏 收藏
举报

作为一个NP完全问题,通常采用启发式算法来解决网格工作流调度。首先对网格工作流调度算法进 行了分类,然后对其典型算法进行了分析和讨论,并阐述了一些典型网格工作流调度系统,最后指出了现有算法 中的一些不足之处,展望了该领域的进一步研究方向。
2818 计算机应用研究 体;最后采用贪婪策略在父代个体与试验个体之间进行选择操 a)大部分考虑的是DAG表示的网格工作流 作,选择具有更佳适应度的个体作为子代个体。与其他演化算 h)大部分优化的调度标准仅是响应时间和/或服务费用 法相比,具有原理简单、易实现、鲁棒性和适应性强等特点,具这两维QS属性。 有更好的仝局搜索和局部增强能力,但在演化后期,群体之间 c)大部分是单日标优化,即使考虑到了多维QoS参数也 的差异度减小、收敛减慢、陷入局部最优解。文献[19]提出了是通过某种聚合方法把多维QoS参数聚合在一个目标函数屮 一种采用多目标差分进化算法的、DAG表示的工作流执行计进行优化。 划方法,其目标是根据用户指定的QS(时间和费用)需求产生 系列均衡调度方案。 3网格工作流调度算法的应用分析 6)Sufferage 网格工作流调度算法在典型网格工作流管理系统屮的应 Sutera算法的主要思想是:个节点被分配给这样个用主要有 作业,如果该作业不分配到该节点上,将会蒙受最大的损大。 a)ASKALON 它是澳大利亚 Innsbruck大学开发的 算法为每个作业定义一个代表其优先权的 Sufferage值,该值一个网格应用开发和计算环境,其主要月标是简化网格工作流 等于作业的次好完成时间减去最好完成时间的差值。调度时应用的开发和执行。它提供了一系列支持网格科学工作流执 先选取对该作业具有最好完成时间的节点,计算 Sufferage 1,行的中间件服务,以透明和有效地访间网格;它包括资源管理 然后比较该节点上已经分配了的作业如果该作业 Sufferage服务、设定引擎服务性能分析服务、性能预测服务和调度器服 值高于已经分配作业的 Sufferage值,那么取消已经分配的作务。调度器服务是在性能预测和资源管理服务基础上,使用基 业,而将该作业分配给节点。重复以上过程,一直到作业集合丁图形的启发式优化算法,决定单个或多个网格工作流应用的 为空。算法的目标是让所有作业的损失度总和最小。它一球有效呋射。在 ASKALON调度器服务中合成了三种凋度算法: 追求最小的完成时间,而没有考虑任务的QS要求,这样就HEFT、GA和 myopIC即时算法。 ASKALON使用静态调度和动 会造成过多的任务达不到QS要求而被抛弃。文献[20]提出态调度混合的方法进行工作流的调度。静态调度方法是预先 了一种扩展的Q- Sufferage调度算法来对就绪队列进行网格给整个作流映射资源,动态调度算法是在静态调度算法的基 工作流调度,该算法只考虑任务优先级和 Deadline约束,且乜础上,根据系统性能预测的结果对网格工作流进行优化。此 只考虑了DAG表示的网格工作流。 外,调度器通过执行契约监控,动态地调节优化静态调度来满 7)HE上T 足网格基础设施的动态性以试图提供QoS IEIT算法是异构环境下典型的列表调度算法的扩展,包 b)K-Wf0.。调度器识别在该工程中使用基于有色Pe 括杈值分配、权值排序和任务映射三个阶段。文献[21通过i网表示的上作流,能应用不同的调度算法,能调度每一个 扩展HEF算法,在满足用户对工作流截止期限下,以支持协作流变迁,是面向性能的动态工作流调度。它包括五个可利用 作分配和高级资源预留的网格工作流调度。 的调度算法,两个基本算法,即easy和 random算法,三个基丁 8)融合算法 性能数据的高级算法,即 performance- based、 prediction- based和 近年来,融合优化策略得到了广泛的应用。算法融合的思 prediction- and-performance-based算法,后两个算法是扩展的 想已成为提高算法优化性能的一个重要而有效的途径,其出发HEF算法。 点是使单一算法互相取长补短,产生更好的优化能力和效率。 c)CEN323。调度服务负责具体化抽象工作流,调度器 文献「22]提出了一种将遗传算法和模拟退火算法相融合的调采用一组调度策略,根据执行时间和费用提供近优解,以映射 度算法,以尽量使完成时间最小化并能够允分利用资源。文献抽象工作流到组件实现和资源的结合,调度器考虑应用中的所 23]采用微粒群优化的种群搜索方式,融合了局部搜索和全有组件而不是独立组件。调度任务将组件映射到一组可用的 局搜索,引入了模拟退火算法和遗传算法思想,利用模拟退火资源上,已经实现了一些用于决定资源映射的调度算法,如 随机概率来避免陷入局部最优,提出了一种基于混合微粒群优rand、 best of n random、 simulated annealing和 game theory等算 化算法的网格工作流调度算法,以便更好地满足用户期望的服法,也可以有新的算法以插件的形式加入。 务质量,解决网格服务工作流调度问题。但该文简略了Web d) GrADS30。提供应用级的调度以映射工作流应用任 服务组合的各种依赖关系约束,此外也只是把将要优化的五维务到一系列资源。调度方法依据一个目标函数以最小化工作 QS参数(响应时间代价、可靠性、可提供性和置信度)通过简流应用中作业的总完成时间。调度器通过使用如MDs和 单组合成单目标。 NWS服务来获取资源信息且通过查询 GrADs信息服务来定位 除了上述算法之外,人们还提出了很多算法以求解网格必要的软件在调度的节点上。工作流调度器为每一个应用组 工作流调度冋题。文献24」提出∫基于市场驱动策略的动件排序每一个有资格的资源,通过使用“在该资源上期望执行 态调度算法来满足用户希望的期限和成本要求以提高网格时间和为该组件的数据移动的期望花费的权值总和”来计算 应用的服务质量。文献[25]提出了一个基于QS的工作流等级值,排序后,构建一个性能矩阵用于启发式调度以获取组 管理系统和在工作流应用与资源间寻找满足QoS需求的最件在资源上的映射。 GrADS中应用了三个启发式算法:min 佳匹配的调度算法。文献[26]提出了一种自适应双层网格min、max-min和 Sufferage,优化基于DAG的工作流,以期望获 工作流调度算法 得最小的完成时间。 上述算法应用于网格工作流度领域中,具有以下一个或 e) Pegasus3。系统使用随机匹配方法和基于性能预测 多个特性: 的方法来进行资源的匹配。它支持静态的和实时的调度,支持 第8期 李金忠,等:网格工作沆凋度算法研究综述 2819 可插入的任务调度策略,提供一个用户定义的调度器接口并包 b)启发式智能优化方法将是网格工作流调度的一个重要 括四种基本调度算法,即HT、min-min、omnd- robin和 random研究领域。目前,启发式调度算法的研究还处于仿真阶段,将 算法。 Pegasus系统能执行以下优化:任务集群、数据重用、数所提出的调度算法应用于实际的网格工作流应用中,以真实网 据清洗和任务划分。 格环境检验测试所提出算法的可行性和有效性,以在实践中不 f) DAG Man。它是以DAC方式组织 Condor作业的一个断完善该调度算法。 集中式的元任务调度器,通过不具有高级优化的 Matchmaking c)目前基于市场模型的调度方法大部分相对简单,需要 机制完成调度,不支持如分支和循环的控制流结构。 提出更复杂的市场模型,保证用户的QoS个性化需求,获取史 国外还有一些比较有名的网格工作流管理系统,如优的网格服务和为用户提供最优的QoS。 Gridant、Tina、 Taverna、 Gridflow、 Gridbus workflow、 Karajan d)日前支持QoS的工作流应用调度仍处于初级阶段。对 Kepler等,现有的网格工作流项目大多是为了一些学术研究目于工作流系统屮的许多高级能力和资源分配是一个需求,如支 的而开发的,大鄙分网格上作流管理系统并没有很好地解决持对工作流结构的循环和条件检测,支持基于动态协商模型的 QoS问题。可以发现“:(a)一些系统或项目没有考虑面自适应调度,支持高级SLA监控和重协商等 向服务的网格架构,因此在以网格服务为核心的网格研究中 e)在调度算法中嵌入一定的容错机制、高级预留机制、任 些研究成果已不能适应OCI的要求;(b)调度系统中使用务迁移技术、网格经济技术和重调度等,以改善调度性能,这方 的调度策略和调度算法单一,缺乏优化,难以满足网格工作流面还有很多工作要做。 应用的不同需求;(c)调度系统中绝大部分没有提供对服务质 f)网格环境的动态多变性、分布性和自治性等,网格服务 量QoS的支持,并且只提供了基于性能预测的调度策略。对(资源)和工作流仟务随时可能加入或离开,需在调度算法中 于口益发展的商业工作流应用,调度器势必要更多地考虑用户引入动态资源信息和多阶段预测信息,因此自适应动态调度算 的QoS需求,考虑成本和安全问题,因此调度策略也将渐渐转法也是一个发展方向。 向基于市场驱动和信任驱动的调度策略和调度算法的研究。 g)网格工作流调度系统必须貝有一定的安仝机制,以便 为网格提供女全可靠的调度服务。日前,安全的L作流调度技 4结束语 术有待于进一步研究。 1)存在的问题 h)设计一个通用标准调度模型和解决多工作流调度问题 网格工作流调度的关键问题是为一项活动(任务)何时、仍是未来的研究难点。 何地、如何进行、使用哪些网格服务(资源)。对于现存的一些 i)随着网格技术与Web服务技术的融合及WSRF、SLA等 调度算法,有在一个或多个以下缺陷 概念的提出,网格工作流应用已逐渐从科学应用领域拓宽到商 a)大部分只考虑DAG表示的工作流,对于含有史复杂的业领域。一旦商业工作流管理系统出现,支持QS将在工作 工作流结构(如循环、并行、分支等结构)支持力度不足。 流的规范层和执行层变得极其关键。在规范层,工作流语言需 b)大部分只考虑如何将网格工作流中的任务映射到能获要允许用户去表达他们的QS需求;在执行层,工作流调度必 得最优执行性能的资源上,只考虑响应时间或和服务费用这须能够在满足用户的O需求下映射工作流到资源上2。因 两维(S属性,少部分考虑到访问成本或和完成期限的限此,S驱动策略的调度将会变得极其重要。 制,对于如可靠性、可利用性和声誉等QoS属性涉及较少 为适用于所有调度问题类型开发一个单个高效上作的调 c)大部分是单月标优化,通过某种聚合方法把多维Ons度方法大体上是不可行的。综合考虑多种调度策略,将更 属性聚合在一个目标函数中。采用单目标优化算法进行优化多的因素加入到网格工作流调度算法中,使得新的算法能够更 求解,所产生的最优调度方案是满足约束条件的单目标最优加适合动态的网格环境和满足用户的QS需求,是网格工作 解,不能从真正意义上解决多目标的优化调度。 流调度发展的一个重要趋势。融合高级预留和容错机制、服务 )不少调度算法还没有完整的理论依据,一些调度技术等级协议出LA、网格经济技术等,设计一种更加适应网格上作 的结论还只是来自仿真结果。 流的动态调度算法仍是一个挑战。 e)考虑高级预留和容错机制,任务迁移技术等思想的调参考文献: 度算法较少。 [1 FOSTER I, KESSELMAN C, TUECKE S. The anatomy of the grid f)大部分调度算法仅考虑一个佔算的预测快照值,并假定 enabling scalable virtual organizations[J]. International Journal of 在作业执行期间其值不变,但由于网格环境的动态多变性,这 Supercomputer Applications, 2001, 15(3) 种假定是不可取的1。 [21 YU Jia, BUYYA R. A taxonomy of workflow management systems for g)设计成道用标准模型的方法较少,较少的工作解决多 grid computing[ J. Joumal of Grid Computing, 2006, 3(3-4) 工作流调度问题。 l71-200 [3 YU Jia, BUYYA R, RAMAMOHANARO K. Workflow scheduling 2)展望 尽管网格工作流调度已取得了一些研究成果,但随着网格 distributed computing environments. Berlin Springer, 200 应用的复杂性发展,网格工作流调度仍需要进行深入的研究 ]李超,朱巧明,李培峰,等.一个网格服务工作流的动态调度算 a)考虑包含如循环、并行、条件等更复杂的工作流结构 [J].计算机应用研究,2008,25(11):3285-3287. 包含如可靠性、可利用性、声誉等更多的QoS属性,更适应网[5]苑迎春,李小平,王茜,等,基于逆向分层的网格工作流调度算法 格环境的带多维QoS约束的多目标优化的网格工作流调度。 [J].计算机学报,2008,31(2):282-290 2820 计算机应用研究 [6 YUAN Ying-chun, LI Xian-scng, SUN Chen-xia. Cost-effective heu national Symposium on High Performance Computing Systems and A ristics for workflow scheduling in grid computing economy. C//Proc lications. Washington DC: IEEE Computer Society, 2007: 156-163 of the 6th International Conference on Grid and Cooperative Compu- [27 PRODAN R. Specification and runt ime workflow support in the ASKA ting.2007:322-329 LON grid environment[J]. Scientific Programming, 2007, 15(4) [7]张艳,李楠,一亼市场驱动的QS网格工作流任务度算法[J 93-211 计算机应用与软件,2008,25(4):162-164 28 WIECZOREK M, PRODA R, FAHRINGER T Scheduling of scien [8]国忠,于炯,侯勇,等,基于资源状态可靠度的网格工作流调庹 tifie workflows in the AsKaloN grid environment[J. ACM SIG 算法[J].计算机工程与应用,2008,44(18):115-118 MOD Record,2005,34(3):56-62 9]倪晚成,刘连臣,吴澄.网格工作流中基于商品市场的服务选择「29 PRODAN R, FAHRIⅠNFRT. Dynamic scheduling of scient ific work [J].计算机应用,2007,27(12):2973-2975 flow applications on the grid: a case study[ C]//Proc of ACM Sympo [10 KYRIAZIS D, TSERPES K. MENYCHTAS A, et aL. An innovative sium on A pplied Computing. New York: ACM Press, 2005: 687-694 workflow mapping mechanism for grids in the frame of quality of service [30 The K WfGrid Project. KWF- WP2-D2-UIBK-Scheduler stable user [JJ. Future Generation Computer Systems, 2008, 24(6): 498-511 manualpdfleb/oL.[2008-10-08.http://www.dps.uibk.ac [1]于明远,胡亚红,王子仁。基于自适应微粒群算法的网格工作流 at/- marek/kwf-grid/scheduler 调度[J].计算机应用与软件,2008,25(8):19-21 [31. The K-Wf Grid Project. KWF-WP2-D2-UIBK-v1 0-Scheduler stable [12]王勇,胡春明,杜宗霞.服务质量感知的网格工作流调度[J].软 developermanualR/ol].[2008-10-08].http://www.dps.uibk 件学报,2006,17(11):2341-2351 ac.at/ projects/kwfgriddeliverables/KWF-WP2-D2-UIBK-Scheduler 13丨肖志娇,常会友,衣杨.启发式规则与GA结合的优化方法求解工 User Manual. pdf. 作流动态调度优化问题[J],计算机科学,2007,34(2):157-[32 MAYER A, MeGoUGH s, FURMENTO N,e:al. icenI dataflow and workflow: composition and scheduling in space and time C// [14]郭文彩,杨扬.基于逗传算法的网格服务工作流调度的研究[J」 Proc of UK e-Science All Hands Meeting. Bristol TOP Publishing 计算机应用,2006,26(1):54-56 Ld.2003:627-634 [15]郭文彩,杨扬.一种面向服务的网格工作流调度算法[J].计算机[33. YOUNG L. MCGOUGH S, NEWHOUSE S,etal. Scheduling archi- 科学,2006,33(6):132-134. tecture and algorithms within the ICENI grid middleware[ C]//Proc of [16 YU Jia, BUYYA R. A budget constraint scheduling of workflow ap- UK e-Science All Hands Meeting. Bristol. TOP Publishing Ltd. 2003 plications on utility grids using genetic algorithms[ C]// Proc of the 15th IEEE International Symposium on High Performance Distributed [34] COOPER K, DASGUPTA A, KENNEDY K, et aL. New grid schedu Computing. 200 ling and rescheduling methods in the grADS project[ J]. Internatio- I 17 BENEDICT S, VASUDEVAN V. Improving scheduling of scientific nal Journal of Parallel Programming, 2005, 33(2-3): 209-229. workflows using tabu search for computational grids [J]. Information [35 BLYTHE J, JAIN S, DEELMAN E, et al. Task scheduling strategies Technology Journal, 2008, 7(1): 91-97 for workflow-based applications in grids[C]//Proc of IEEE Interna [18 BENEDICT S, VASUDEVAN V. Scheduling of scientific workflows tional Symposium on Cluster Computing and the Grid. Washington using simula ted annealing algorithm for computational grids [ J]. It DC: IEFF Computer Society, 2005: 759-767 ternational Journal of Soft Computing, 2007, 2(5): 606-611 [36 MANDAL A, KENNEDY K, KOELBEL C, et al. Scheduling strategies [19 TALUKDER A K M, KIRLEY M, BUYYA R. Multiobjective diffe for mapping application workflows onto the grid C //Proc of IEEE rential evolution for workflow execution on grid C|//Proc of the 5 th International Symposium on High Performance Distributed Computing International Workshop cn Middleware for Grid Computing. New ashington DC: IEEE Computer Society, 2005: 125-734 York: ACM Press. 2007: 944-953 37 DEELMAN E, SINGH G, SU Mei-hui, et al. Pegasus: a framework 20]胡志刚,陈俊.网格工作流中一种扩展的 oD- Sufferage调度算法 for mapping complex seientific workflows onto distributed systems [J] [J].计算机应用研究,2008,25(5):1504-1506 Scientific Programming, 2005, 13(3): 219-237 [21 DECKER J, SCHNEIDER J. Heuristic scheduling of grid workflows [38. DEELMAN E, GANNON D, SHIELDS M, et al. Workflows and e- supporting co-allocation and advance reservation C //Proc of the 7 th ience: an overview of workflow system features and capabilities J I IEEE International Symposium on Cluster Computing and the Grid Future Generation Computer Systems, 2009, 25(5): 528-540 Washington DC: IEEE Computer Society, 2007: 335-342 [39CondorProject.daGmanapplicationR/ol._2008-10-18].http:// [22]丁一呜,孙瑞志,基于遗传退火算法的网格工作流调度研究[J] www.cs.wise.eru/condor/manual/v6.8.7/condor-v6_8_7-manual.prlf 计算机应用,2007,27(s1):89-91 40ˉ李超,朱巧明,李培峰,等.网格工作流调度研究综述[冂.计算机 [23]于明远,朱艺华,梁荣华,基于混合微粒群算法的网格服务工作 应用与坎件,2008,25(10):279-282 流调度[冂].华中科技大学学报,2008,36(4):45-47 41 WIECZOREK M. HOHEISEL A prodan R. Towards a genera [24]李嘉菲、刘大有,虞强源.基于规划和动态调度的闷格工作流 model of the multi-criteria workflow scheduling on the grid J]. Fu [J].吉林大学学报,2007,37(2):407-412 ture Generation Computer Systems, 2009, 25(3): 237-256. [25 KHANLI L M, ANALOUI M. QoS-based scheduling of workflow ap- [42 YEO C S, BUYYA R, YU Jia, et al. Utility computing on global plications on grids[C]//Proc of the 3rd IASTED International Confe grids[ K]//BIDGOLI H. Handbook of Computer Networks. Hobo- rence on Advances in Computer Science and Technology. Anaheim ken, NJ: Wiley, 2007 ACTA Press. 2007: 276-282 [43 WIE CZOREK M, HOHEISEL A, PRODAN R. Taxonomies of the [26 DO\G Fang-peng, AKL S G. An adaptive double-layer workflow multi-criteria grid workflow scheduling problem[M//Grid Middle scheduling approach for grid computing C]//Proc of the 2 st Inter- ware and Service. Berlin Springer-Verlag, 2007: 237 -264

...展开详情
试读 5P 论文研究-网格工作流调度算法研究综述.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分,得勋章
最新推荐
论文研究-网格工作流调度算法研究综述.pdf 9积分/C币 立即下载
1/5
论文研究-网格工作流调度算法研究综述.pdf第1页

试读结束, 可继续读1页

9积分/C币 立即下载 >