论文部分内容阅读
在传统的多处理器调度系统当中，应用程序所追求的主要目标是该应用程序的完成时间尽可能的少。然而近些年来，应用程序在执行过程中所消耗的能量越来越引起人们的广泛关注。因此，在现代多处理器调度系统当中，以应用程序的完成时间和能量消耗为目标多目标工作流调度问题就成为调度领域的热点前沿问题。动态电压缩放技术(Dynamic Voltage Scaling, DVS)作为人们研究调度算法的有效技术之一，更是受到人们越来越多的关注。DVS技术支持动态调节处理器的电压等级值，这就为在应用程序的完成时间和能量消耗之间取得较好的平衡提供了技术支持。因此，本课题研究的主要问题:如何将具有子任务间数据依赖关系限制的工作流映射到数量有限的异构的具有DVS技术的处理器上，同时以该工作流的运行时间和能量消耗尽可能的少为目标。本课题的研究成果主要有以下两个方面: 1、针对具有实时性要求的多处理器调度系统，本文提出一种全新的基于启发式的多目标工作流调度算法(enhanced energy conscious heuristic，EECS)。该算法不仅具有较好的调度效果（较少的完成时间和能量消耗），而且具有较快的调度时间。通过仿真实验表明，EECS算法在满足用户的实时性要求的前提下，比现有算法具有更优的运行时间和能量消耗。 2、由于粒子群算法(Particle Swarm Optimization，PSO)本身的简单性和较低的计算复杂性，PSO算法被广泛的应用于解决各种组合优化问题。因此，本课题尝试着用PSO算法解决面向运行时间和能耗的多目标工作流调度问题，从而形成一种全新的基于粒子群的多目标工作流调度算法(PSO-heuristic)。通过仿真实验表明，PSO-heuristic比现有的混合遗传调度算法在工作流的完成时间和能量消耗上都具有较大的优化。