异构分布式环境下协作任务的调度算法

《异构分布式环境下协作任务的调度算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、异构环境下科学工作流的启发式调度算法龙浩汪浩（江西师范大学软件学院江西南昌330029）E-mail：hhlong2010@hotmail.com摘要：针对资源个体与网络链路差异较大、广域互连的分布式系统下科学工作流的时间费用优化问题，提出改进的相对效比调度算法。利用任务配置图描述关联科学工作流过程模型的资源模型，利用任务-资源分配图作为科学工作流调度模型，采用相对效费比迭代调整任务-资源分配图，最终得到优化的工作流调度方案。算法能够避免共享资源访问冲突，合理地筛选候选资源、优化费用，能够很好地适用科学工作流的

2、资源差异较大及任务间存在大量数据传输的特征，模拟实验表明算法性能有较大的提高。关键词:科学工作流；任务配置图；任务-资源分配图；相对效费比中图法分类号：TP393文献标识码：AASchedulingHeuristicofScientificWorkflowunderDistributedComputingEnvironmentLONGHao,WANGHao(SchoolofSoftware,JiangxiNormalUniversity,Nanchang,330022,China)Abstract:Data-i

3、ntensivescientificworkflowsarequitecommonindistributedcomputingenvironments,consideringtheinterconnectedisomericphysicalresourcesandtheintensivedatatransferbetweensubtasks,animprovedheuristicbasedonrelativetime-costrate(RTCR)isproposed.Firstlyatask-deploymen

4、tdiagram(TDD)isusedtodepicttheworkflow’smodelandthedeploymentenvironment,andaTask-ResourceAssignmentGraph(TRAG)isusedtodescribepossiblesolution,theoptimizationschedulingcanbeachievedbyadjustediterativelyaccordingtotheRTCRvalue.Theheuristics’efficiencyisrevea

5、ledbycomparingwithILHAalgorithm.Keywords:scientificworkflow;task-deploymentdiagram;task-resourceassignmentgraph;relativetime-costrate1．概述随着信息技术的发展和科学研究方法的日益丰富，使用大规模计算资源和大容量存储设备的计算型科学实验成为科学探索、工程设计验证的重要手段。科学工作流(ScientificWorkflow)[1]借鉴传统工作流技术，可以自动化科学任务的编排、执行、监

6、控以及追踪，支持科学工作分布协同和资源共享。科学工作流是数据驱动的，前后序子任务之间存在大量的数据传输，具有计算密集、数据密集等区别于传统工作流的特点[2]。科学工作流调度问题研究如何利用计算资源最优地完成一个由一组彼此之间存在数据关联的子任务，不同约束条件和用户需求构成不同的组合优化问题，其中完工时间和费用是用户最为关心的两个性能指标。分布式系统下工作流的时间费用优化调度，实质是一个NP-hard问题[3]，对于这类大规模复杂问题，利用启发式算法能够获得较好的性能。文献[4]利用列生成技术给出一种工作流上下界

7、求解方法，并用最大收益规则对列生成算法得到的初始解做改进，文献[5-6]使用不同优先级规则对调度方案进行迭代改进，个体资源的性能差异较大时，调度结果受优先级规则选择的影响很大；截止期分解方法[7-11]按工作流模型结构对子任务分层，将截止期按比例分解到各层，通过优化各层的局部费用最终得到全局较优解。文献[12]证明工作流划分策略并不优于full-graph调度，尤其对不平衡工作流。文献[13]用相对效费比算法解决截止期约束下的网格工作流费用优化问题，对初始调度方案不断调整，当方案完工时间小于截止期时，用时间换成

8、本，当方案完工时间超过截止期时，用成本换时间，能够得到更精确的结果。这些研究没有考虑子任务存在的通信时间与花费，文献[14]假设子任务间的数据传输时间固定、传输费用为0，采用部分关键路径法对截至期进行分解并选择满足截至期约束的最便宜资源以优化费用；CostGradient算法[15]假定子任务间的数据传输成本固定，子任务选择不同节点时计算成本、时间（含计算时间和数据传输时间）严格负相关