基于最早完成时间的网格任务调度算法

摘要

网格作为典型的分布式应用系统，由大量分布共享的异构资源组成，这些资源协同提供了巨大的计算能力。而这些具有广域上分布、自主管理、本质上异构、负载动态变化等特性的资源，也在一定程度上阻碍了计算网格的应用向纵深发展，同时也给计算网格的应用基础研究提出了新的挑战，使得网格环境下的任务调度所面临的问题比传统分布式环境要复杂得多。网格资源管理与调度是高性能网格计算领域中的一个重要研究课题。
　　 在网格任务调度中，通信的延迟是影响调度算法的一个重要因素，它导致任务间等待，还使得处理单元空闲间隔时间过多。另外，如何充分的利用资源，选择资源也是一个重要的因素。本文研究了网格环境下任务调度策略，考虑了通信延迟与资源预处理对算法的影响。主要工作包括以下两个方面：
　　 一方面，由于传统的网格任务调度，没有对资源进行预处理，不能根据资源特性，很好的对资源进行利用。因此，本文运用了模糊聚类的方法对资源进行了预处理，通过对资源特征进行模糊聚类，减少了调度过程中选择处理单元所花费的时间。
　　 另一方面，本文结合表调度技术与任务复制技术，提出了CFTD算法(Cluster EarliestFinish Time Duplication基于资源聚类的最早完成时间复制策略)。通过冗余调度前驱任务到处理器的空闲时间段来减少任务之间通信延迟。有利于保持任务的并行性，提高处理器的利用率，从而缩短整个任务图的并行完成时间。实验结果表明，本文算法优于HEFT任务调度算法。

目录

文摘

英文文摘

声明

第1章 绪论

1.1本课题的研究背景及意义

1.2网格计算研究现状

1.2.1国外网格计算研究

1.2.2国内研究现状

1.3论文的主要内容

1.4论文的组织结构

第2章 网格任务调度

2.1任务调度概述

2.1.1任务调度的特点

2.1.2任务调度的主要目标

2.2网格调度体系结构

2.2.1网格调度模型

2.2.2网格调度的体系结构

第3章 基于最早完成时间的网格任务复制算法预处理

3.1模糊理论

3.1.1截集

3.1.2相似度

3.1.3模糊综合评价

3.2算法资源预处理方法——资源模糊聚类

3.2.1网格资源模糊聚类

3.2.2其他网格资源聚类方法分析

3.2.3预处理性能比较

第4章 基于资源聚类的最早完成时间任务复制调度算法

4.1相关基于DAG网格调度算法简介

4.1.1表调度算法

4.1.2聚簇调度算法

4.1.3基于任务复制的调度算法

4.1.4启发式调度算法

4.2 CFTD算法

4.2.1 CFTD算法模型建立

4.2.2 CFTD算法描述

4.2.3 CFTD算法实例

第5章 模拟与仿真实验

5.1网格模拟与仿真工具

5.1.1 GridSim概述

5.1.2 Gridsim体系结构

5.2实验过程及结果分析

5.2.1实验评价

5.2.2实验结果及分析

第6章 总结与展望

参考文献

致 谢