图 3. 2  包含10个任务的任务实例图（图片引用自[16]） 12

图 3. 3  HEFT算法下图3.2的任务调度图 13

图 4.1  输入随机图个数为2 19

图 4.2  随机图存入指定.txt文件 19

图 4.3  随机生成的输入参数 20

图 4.4  根据随机参数生成通信成本矩阵 20

图 4.5  根据随机参数生成计算成本矩阵 21

图 4.6  随机生成的输入参数 21

图 4.7  根据随机参数生成通信成本矩阵 22

图 4.8  根据随机参数生成计算成本矩阵 22

图 4.9  文件Input1.txt中参数 23

图4.10  文件Input1.txt中对应10个任务分别的ranku值 23

图4.11  文件Input1.txt中对应ranku值排序 24

图4.12  文件Input1.txt中对应任务调度 24

图4.13  文件Input1.txt中对应最终任务调度图 25

图 4.14  文件Input2.txt中参数 25

图4.12  文件Input2.txt中对应8个任务分别的ranku值 26

图4.15  文件Input2.txt中对应ranku值排序 26

图4.16  文件Input2.txt中对应任务调度 26

图4.17  文件Input2.txt中对应最终任务调度图 27

表 3.1  图3.2的示例计算成本表（表格引用自[16]) 12

表 3.2  HEFT算法下图3.2的属性值 13

表 3.3  HEFT算法中使用的算法定义 14

表 4.1  随机图生成器输入参数随机范围 19

1  绪论

1.1  研究背景和意义

随着并行化、网络化、智能化逐渐成为当今计算机发展的主要趋势,无论是解决大型和小型的科学计算问题,还是在汽车、航空航天器的设计制造、石油勘探、地震资料处理及国防核爆炸模拟等众多领域，分布式并行计算正变得越来越重要[1]。在处理计算密集型和数据密集型的应用时，传统的同构计算方法因其花费时间巨大，已无法满足现有的性能需求。因此，合理有效地调度对进行异构环境下的大批量计算相当有用。

任务调度即分配处理机和任务的映射关系[2]。一直以来，多任务调度是众多理论中的经典模型，但仍隐含某些限制，例如，将具有超过一个的时间单位的任务调度到两个处理器，并将单位时间的任务调度到任意数目处理器。因为处理单元有所区别，异构环境中任务调度时可能会遇到有差异调度限制，这更为有效地分配资源增加了难度。

1.2  研究现状

1.3  本文研究工作

本课题的主要工作是针对异构环境下多任务的调度问题进行研究，重点对异构最早完成时间算法（Heterogeneous Earliest-Finish-Time, HEFT）算法进行系统的研究和学习，深入了解在异构环境下的任务调度的运行原理，最终通过编程实现其算法流程。

本课题的工作将从以下几个方面展开：

一、在异构环境下建立相关模型，设计相关的运行流程和数据结构，通过对任务的向上秩值排序并对资源进行合理化分配，以得出最佳方案；

二、基于上述要求完成代码实现，具体需求内容为：使用有向无环图表征对应的工作流任务，确定任务调度模型中的目标函数、约束条件和决策变量。设计合理、有效的算法流程实现上述异构算法的各主要函数功能模块，包括计算向上优先级、优先级排序以及将任务合理分配给处理器等。

三、通过编程模拟实现任务调度过程，根据实验结果评估算法的性能。

1.4 算法方案及其社会影响

本课题实现的异构环境下基于最早完成时间的任务调度算法，其研究意义在于为当前不断发展的异构计算环境提供通用的支撑平台这一目标做出探讨。使用该算法的任务调度方案来进行任务的分配调度，能够很大程度地挖掘异构网络中基础设施的计算潜力。以合理地处理多个任务和多个处理器之间的映射关系为总体要求。在计算资源可用的前提下，对不同任务进行优化管理和调度，有效提高任务调度和执行效率，降低计算资源的使用成本。除此以外，本课题所实现的异构调度算法的调度思想和运行机制可扩展应用于工程领域的很多类似问题，对于提高工作效率和资源利用率、促进社会可持续发展具有一定的积极意义。