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

摘要

网络计算环境日益成为一种不受地域限制的廉价的超级计算环境。任务调度是目前网格计算中一个热点研究的问题，是能够高效使用网格资源的重要保证。本文在研究电力网格体系结构，网格任务特点等的基础上，针对网格的异构特性以及网格中任务间的依赖性,提出两种基于DAG的并行任务调度算法。这两种算法能够方便地应用于其他计算网格。 鉴于电力系统对计算任务的实时性、高效性的要求，如果把网格技术运用到电力系统计算中来，可以充分发挥网格计算的优势，构建了完全异构性的电力网格开发平台，以满足电力系统高性能计算的要求。电力网格中的应用服务可以分解为若干个互有依赖关系的子任务，这些子任务可以用DAG图表示。对网格中任务的调度问题可以转化为DAG的调度问题。 网格中存在着机器计算能力的异构性，表现在电力网格中的某些子任务只能在部分计算节点上运行，而某些子任务可以被同时分派到多个计算节点上并行执行。本文提出了任务可计算性和机器可计算性这两个概念来量化这种异构性。针对网格以上特性，本文提出了一种基于DAG的启发式调度算法，利用了任务可计算性和机器可计算性，支持网格资源的预留。 除了可计算性的不同，网格中还存在着网络连接的异构性，不同管理域间网络连接受限制而且不稳定。本文根据网格的这个特性，提出了另外一种基于表调度技术的启发式调度算法，算法把相关性强的任务调度到同一个域中，从而减少通信开销。 本文最后利用SimGrid仿真工具，在仿真实验中评估和比较了这些算法。仿真结果表明文中对表调度算法的扩展在异构网格环境中具有较优的性能和广泛的适应性。