网格环境中基于dag的并行任务调度算法.研究

《网格环境中基于dag的并行任务调度算法.研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、上海交通大学硕士学位论文ABSTRACTconsideredasschedulingtheDAG.Thecomputingabilitiesofmachinesonthegridaredifferent.Sometypesofsub-jobscanonlybescheduledtospecificmachines,andsomesub-jobscanbedistributedonseveralmachinestoaccelerateitsexecution.Inordertomeasurethisheterogeneousnessofg

2、rid,wedefinedtwoconcepts,jobandmachinecalculability.AndthispaperproposedaDAGbasedheuristic,whichutilizesthejobandmachinecalculability,andsupportsresourcereservation.Besidesdifferentcalculability,gridsuffersdifferentnetworkconnections.Networkbetweendifferentresourcedomain

3、sarerestrictedandunstable.Ourproposedanotherlistalgorithmbasedonthisproperty.Wetrytoschedulestrongrelatedtaskstothesamedomain,inordertoreducethecostofnetworkcommunication.AnextensivesimulationstudyinSimGridsimulationplatformwasconductedtoevaluateandcomparetheperformanceo

4、fthealgorithms.ItshowedthegeneralsuitabilityandbetterperformanceofourenhancedlistschedulingheuristicswithinheterogeneousGridenvironments.Keywords:GridComputing,DAG,listscheduling,SimGrid上海交通大学工程硕士学位论文攻读硕士学位期间已发表或录用的论文第62页上海交通大学工程硕士学位论文攻读硕士学位期间已发表或录用的论文第63页上海交通大学硕士学位论文网格环

5、境中基于DAG的并行任务调度算法研究第一章绪论1.1本文的研究背景网格正逐步成为一种新的技术和基础设施，可以充分利用集成的资源形成一个大规模的计算池，其目的是为了在分布、异构，自治的网络资源环境上构造动态的虚拟组织，并在其内部实现跨自治域的资源共享与资源协作，有效地满足面向互联网的复杂应用对大规模计算能力和海量数据处理的需求。在网格计算技术中，网格系统软件起着关键的作用，他提供单一系统映像、透明性、可靠性、负载平衡和资源共享等功能。网格系统软件中的网格操作系统层提供网格的底层管理功能，编程和使用环境可提供用户接口，从而使一般应用和专门为

6、网格开发的应用能方便和有效地利用网格资源。许多行业和领域，如能源、交通、气象、水利、农林、教育、环保等，以及涉及科研、开发、教育的诸多部门、单位和企业，对高性能计算网格以信息网格的需求是非常巨大的。无论是早期的计算网格还是目前的服务网格，都面临着如何有效地管理和调度网格资源问题[1-3]。通常是发现适合于给定任务的潜在资源集合，从那些资源中选择合适的资源子集，这些资源满足一个预先定义好的调度约束，找到一个这样的Makespan是NP完全问题[4]。目前常见的网格任务调度算法按照任务之间有无数据依赖关系可以分为独立任务调度和依赖关系任务调

7、度，前者在调度任务时不用考虑任务之间的依赖关系；而后者通常用有向无环图(DAG)表示任务之间的数据依赖关系，在调度过程中满足任务之间的数据依赖关系。针对以有向无环图DAG(directedAcyclicGraph)来表示的并行任务模型的研究在近20年得到了迅速发展。这种模型限制条件包括:任务执行具有非抢占性，即处理机只有在执行完某个任务之后才能处理另外一个任务，另外这些任务之间具有前驱后继的依赖关系，某个子任务只有在其所有的父节点任务处理完毕后才能开始执行;该模型的调度目标就是要使得整个DAG图的调度长度最短。早期的这种DAG调度模型只

8、引入了各个任务的执行时间(用每个节点权值表示)，而并没有考虑任务之间的通信时第1页上海交通大学硕士学位论文网格环境中基于DAG的并行任务调度算法研究间。但即使是在这种情况下，这种DAG调度仍然被证明是NP完