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

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

1、·上海交通大学硕士学位论文网格环境中基于DAG的并行任务调度算法研究姓名：杜杰申请学位级别：硕士专业：计算机应用指导教师：李明禄20090101···上海交通大学硕士学位论文ABSTRACT网格环境中基于DAG的并行任务调度算法研究摘要网络计算环境日益成为一种不受地域限制的廉价的超级计算环境。任务调度是目前网格计算中一个热点研究的问题，是能够高效使用网格资源的重要保证。本文在研究电力网格体系结构，网格任务特点等的基础上，针对网格的异构特性以及网格中任务间的依赖性,提出两种基于DAG的并行任务调度算法。这两种算法能够方便地应用于其他计算网格。鉴于

2、电力系统对计算任务的实时性、高效性的要求，如果把网格技术运用到电力系统计算中来，可以充分发挥网格计算的优势，构建了完全异构性的电力网格开发平台，以满足电力系统高性能计算的要求。电力网格中的应用服务可以分解为若干个互有依赖关系的子任务，这些子任务可以用DAG图表示。对网格中任务的调度问题可以转化为DAG的调度问题。网格中存在着机器计算能力的异构性，表现在电力网格中的某些子任务只能在部分计算节点上运行，而某些子任务可以被同时分派到多个计算节点上并行执行。本文提出了任务可计算性和机器可计算性这两个概念来量化这种异构性。针对网格以上特性，本文提出了一种

3、基于DAG···上海交通大学硕士学位论文ABSTRACT的启发式调度算法，利用了任务可计算性和机器可计算性，支持网格资源的预留。除了可计算性的不同，网格中还存在着网络连接的异构性，不同管理域间网络连接受限制而且不稳定。本文根据网格的这个特性，提出了另外一种基于表调度技术的启发式调度算法，算法把相关性强的任务调度到同一个域中，从而减少通信开销。本文最后利用SimGrid仿真工具，在仿真实验中评估和比较了这些算法。仿真结果表明文中对表调度算法的扩展在异构网格环境中具有较优的性能和广泛的适应性。关键词：网格计算，任务调度，有向无环图，表调度技术，Si

4、mGrid···上海交通大学硕士学位论文ABSTRACTResearchforDAGBasedParallelTasksSchedulingAlgorithminGrid-ComputingABSTRACTGridcomputingenvironmenthasincreasinglygrownaverycheapsupercomputingenvironmentbeyondarealimit.Taskschedulinghasbecomeahotresearcharearecently,whichguaranteestheefficientus

5、eofgridresource.Thispaperisbasedontheresearchofpowergrid,proposestwoDAGbasedschedulingalgorithminconsiderationofheterogeneousofgridanddependencyoftasks.Itisconvenienttoapplyouralgorithmstoothercomputinggrid.Consideringrealtimeandefficiencyrequirementofcomputingtasksfrompower

6、system,ifgridcomputingtechnologyisappliedtopowersystemcomputingandsimulation,itcanbebenefitedfromthestrengthofgrid···computing,andconstructacompletelyheterogeneouspowergridplatformtosatisfyhighperformancecomputingrequirementfrompowersystem.LotsofJobsinpowergridcontainsub-job

7、sdependingoneachother,whichcanberepresentedasaDAG.Theschedulingprobleminpowergridcanbe···上海交通大学硕士学位论文ABSTRACTconsideredasschedulingtheDAG.Thecomputingabilitiesofmachinesonthegridaredifferent.Sometypesofsub-jobscanonlybescheduledtospecificmachines,andsomesub-jobscanbedistribu

8、tedonseveralmachinestoaccelerateitsexecution.Inordertomeasurethisheterogene