论文部分内容阅读
随着用户对处理器需求的不断提高,性能、功耗等问题使得单核处理器的发展进入瓶颈,因而多核处理器开始得到关注。多核处理器的任务调度是从时间和空间两方面来分配任务到相应的处理器内核,合理的任务调度能够提高处理器的性能,降低系统损耗。多核处理器的任务调度包括分配和调度两步。其中,分配主要解决任务在哪个处理器核上执行,即将任务分配到合理的处理器内核；调度主要解决任务何时被执行,即给出任务在处理器核上的起止时间。影响任务调度的因素有：任务本身的执行时间、任务间的通信开销和任务之间的依赖关系等。国内外学者对多核任务调度问题进行了深入的研究,证明了该问题为组合优化问题,不能在多项式时间复杂度内得到最优解,属于NP-hard问题。本文以有依赖关系的多个任务为研究对象,对同构多核处理器系统的任务调度问题进行研究。鉴于智能搜索算法的并行性和全局搜索优势,本文将使用几种常见的智能搜索算法来解决多核任务调度问题,从而缩短任务的完工时间。主要工作如下：(1)提出了提高种群多样性的任务均衡遗传算法(Improve Population of Genetic Algorithm, IPGA),改进如下：首先,使用启发式的分层调度来初始化种群,提高种群的初始质量；其次,基于编号交叉并引入动态变异率,确保了个体的质量；再次,添加扰动策略,防止种群在选择后得到相似个体,提高了种群多样性；最后,将上一代种群中最优个体替换到下一代,始终保证全局最优个体在种群中参与轮盘赌。实验表明,与其他遗传算法(Genetic Algorithm, GA)相比,该算法可以得到较少的任务调度时间和较快的最优解搜索能力。(2)提出了一种集启发式算法、禁忌搜索算法(Tabu Search, TS),模拟退火算法(Simulated Annealing, SA)于一体的改进混合遗传算法(Modified Hybrid Genetic Algorithm, MHGA)。MHGA改进如下：首先,提出基于TS算法的随机编号交叉操作,提高种群的多样性；其次,采用基于SA算法的变异,提高个体质量；最后,将MHGA算法与IPGA算法进行了比较。实验结果表明,MHGA算法的任务完工时间更少、搜索最优解的能力更强。(3)提出了一种集启发式算法、SA算法于一体的改进混合粒子群算法(Modified Hybrid Particle Swarm Optimization, MHPSO),使用以下思路来优化：首先,采用启发式方法来初始化粒子群,提高初始粒子群的质量；其次,提出了离散粒子的编码规则；最后,使用SA算法来更新粒子位置和速度。仿真结果表明,MHPSO算法的收敛值明显优于HGA、PGA和ⅠPGA算法；收敛值虽然稍差于MHGA算法,但其仿真时间也小于MHGA算法。