摘要：本课题以用于有限数量的异构处理器的任务调度算法为研究对象，着重对异构环境下最早完成时间算法的实现和应用进行了调研，以符合异构环境下任务调度中高性能和快速调度时间的需要。本课题使用基于插入的手段，缩短工作流中的最早完成时间，减少相邻处理器之间的间隙。该算法在各个步骤中获取含最高向上值的任务，并将其分配给对应处理器。此外，在处理器选择阶段，该算法将关键任务分配到处理器上，从而最大限度地减少关键任务的总执行时间。本课题设计了参数图生成器来生成具有各种特征的加权有向非循环图以提供相关工作的鲁棒性和无偏差比较，并基于部分随机生成图和实际应用图表，显示了异构最早完成时间调度算法在任务调度质量和成本方面的优越性。

关键词  任务调度  任务图  异构系统  列表调度  异构最早完成时间

毕业设计说明书外文摘要

Title  Research on the Implementation of Task Scheduling Algorithm Based on Earliest Completion Time in Heterogeneous Environments

Abstract：This thesis conducts a research on a task scheduling algorithm for a limited number of heterogeneous processors. This project focuses on the implementation and application of Heterogeneous Earliest-Finish-Time, for the purpose of meeting the requirement of both high-quality task schedule and fast scheduling time in heterogeneous environments. This project uses an insertion-based approach to minimize the earliest completion time of workload task.The algorithm obtains the task with the highest value in each step and assigns it to the corresponding processor. In addition, during the processor selection phase, the algorithm assigns critical tasks to the processor, minimizing the total execution time of critical tasks.In this work, a task graph generator is implemented to generate a weighted directed acyclic graph with various features to provide robustness and unbiased comparison. Based on both the randomly generated graphs and graphs of some real application, experimental results demonstrate the advantage of Heterogeneous Earliest-Finish-Time scheduling algorithm on schedule quality and cost.

Keywords  task scheduling  task graphs  heterogeneous systems  list scheduling  Heterogeneous Earliest-Finish-Time

目   次

1  绪论 1

1.1  研究背景和意义 1

1.2  研究现状 1

1.3  本文研究工作 1

1.4 总体技术方案及其社会影响 2

1.5 技术方案的经济因素分析 2

1.6  本文结构安排 2

2  相关的理论基础 4

2.1  静态任务调度算法 4

2.1.1  列表调度启发式算法 4

2.1.2  聚类启发式算法 4

2.1.3  任务复制试式启发式算法 5

2.1.4  有引导的随机搜索技术 5

2.2  异构环境下启发式任务调度 5

2.2.1  动态级调度算法 5

2.2.2  映射启发式算法 6

2.2.3  等级化最小时间算法 6

2.3  任务调度模型 6

2.4  本章小结 8

3  HEFT的流程设计及具体实现 9

3.1  HEFT算法设置优先级的图形属性 9

3.2 异构最早完成时间（HEFT）算法详细流程 10

3.2.1  HEFT算法流程 10

3.2.2  HEFT算法实现步骤 10

3.2.3  HEFT算法的具体实现 13

3.3  本章小结 17

4  实验过程 18

4.1  实验环境和工具 18

4.1.1  实验环境 18

4.1.2  实验工具 18

4.2  实验数据 18

4.2.1  随机图生成器 18

4.2.2  HEFT算法的实现 23

4.3  本章小结 27

结  论 28

致  谢 30

参 考 文 献 31

图 2. 1  静态任务调度算法分类 4

图 3. 1  HEFT算法流程图 10