随着科学技术的快速发展,信息技术也飞速发展起来,超级计算机在工业、农业、军事、航空航天、社会经济和我们的日常生活的各个领域都扮演了重要的角色,并成为计算机科学和信息技术的一个重要发展方向。资源管理模型和任务调度策略是异构高性能计算机系统的核心问题和关键技术。任务调度策略在满足任务优先级和资源约束的条件下,在可接受的性能指标范围内,有效地减少了总的执行时间并提高了资源的利用率。在过去几十年,资源管理模型和任务调度策略已成为高性能并行计算领域的重要热点研究问题。由于异构超级计算机的体系结构和应用程序软件的复杂性,再加上应用程序对不同资源需要的差异性,使得异构高性能计算系统的并行任务调度变得极为复杂。很多学者的研究结果证明,即便是在化简后的简单模型下,在异构高性能计算系统中的并行任务调度问题是一个NP难问题。因此,并行任务调度问题是一个在高性能并行计算领域的具有挑战性的研究问题。特别是针对现实世界问题的并行任务调度,在可接受的性能和计算复杂度下,要获得一个问题的最优解是不现实的。因此对于这类复杂的问题,往往采用启发式算法,其中最最要的一类就是列表调度算法。列表调度的基本思想主要包括:1)任务优先队列的生成。根据一些贪婪的启发式方法给每个任务分配一个优先级。2)任务到处理机的映射。选择任务优先队列中的最高优先级的任务并将其分配给一个最合适的处理器上,使其完成时间最早。但是由于基于启发式的算法的性能在很大程度上依赖启发的贪婪方式,对于复杂问题的处理时可能会产生不太理想的结果,特别是当任务调度问题的复杂性增加时。与基于启发式算法相反,基于指导的随机搜索算法(元启发式算法),利用在前期搜索结果的基础上寻找问题的解,能够获得比启发式方法更好的解,但算法效率低。所以,在调度质量与收敛速度之间的权衡是必需的。在本文中,提出了一个混合的方式任务调度算法,集成了智能元启发式和启发式算法的优点。所提出的混合方法的性能比启发式的调度质量要好,同时比一般的元启发式算法的时间开销要小,收敛速度更快。本文的主要研究工作如下:针对异构高性能计算系统中的复杂应用,提出一个有向无环图1.针对异构高性能计算系统中的复杂应用,提出一个有向无环图(Directed Acyclic Graph,DAG)任务调度的双螺旋结构的遗传算法(Double Helix Structure Genetic Algorithm,DHSGA),可以广泛地用于DAG应用程序的调度,该方法将启发式方法和元启发式算法进行有机的结合,用启发式的交叉算子和变异算子产生大量的任务优先队列。DHSGA算法有效地避免了现有启发式调度算法的缺点,具有较好的鲁棒性和较好的调度质量。2.为了进一步提高算法的性能,提出一个新的算法(Multiple Priority Queueing Genetic Algorithm,MPQGA)来生成初始种群。在算法中使用了三个评价标准:好的“种子”、均匀覆盖和遗传多样性。与从一个随机生成的解相比较,通过启发式技术获得一个高质量的解可以帮助MPQGA算法更愉快地找到目标的解。均匀覆盖可以使个体很均匀地分散并覆盖整个可行解空间。种群的遗传多样性可以帮助的遗传算法尽可能地达到所有的可行解空间。3.为了进一步提高调度性能,基于正态分布的概率模型,提出了正态随机步及正态分布选择思想,同时使用在两个分子之间进行异(XOR)操作来减少分子克隆的机会。最后通过一个伪随机洗牌方法来生成新的分子,以保持分子多样性,或消除近亲的分子。该混合化学反应优化(Hybrid Chemical Reaction Optimization,HCRO)算法在DAG任务调度问题上实现了更好的性能和调度质量。4.基于动态电压调节技术(Dynamic voltage and frequency scaling,DVFS),提出了具有回收机制的自底向上动态拉伸的节能任务再调度算法,用于解决DAG图任务调度的节能问题,从而在不影响调度质量的情况下减小系统的能量消耗的目的。5.如何在提升并行任务调度质量的同时,又降低系统能耗,是异构高性能计算系统性能评价体系中的两个重要指标。针对这个问题,提出了考虑makespan(调度长度)和能量消耗的双目标优化问题。实验证明了该NSGA-II算法针对任务完成时间和系统能耗这个双目标优化问题具有较好的性能。