论文部分内容阅读
随着异构多核处理器计算能力的大幅度提升,能耗问题也成为制约其发展及应用推广的性能瓶颈。而低功耗设计技术越靠近顶层,抽象层次越高,对功耗的影响越大,因此针对异构多核处理器系统的实时低功耗调度算法的研究得到了国内外研究者的广泛关注。异构多核低功耗调度问题是一个典型的NP难问题,解决该问题的现有算法多采用两阶段的启发式策略:首先利用划分策略将任务分配到各处理单元,然后利用低功耗调度策略确定任务的执行顺序和处理单元的电压。然而,这些算法多忽略了算法的时间复杂度及任务相关特性对低功耗技术节能效果的影响。因此,本文针对异构多核处理器系统模型的特点,基于化学反应优化算法全局寻优能力强的特性,结合关键任务对调度长度的有效控制以及任务能耗和时间属性对低功耗技术节能效果的影响,研究一种节能效率高、收敛速度快的异构多核低功耗调度算法,主要工作如下:在算法的任务划分阶段,针对现有策略收敛速度慢、全局搜索能力不足等问题,本文基于全局搜索能力强的化学反应优化算法提出一种新的任务划分策略CROTM(Chemical Reaction Optimization for Task Mapping)。CRO是一种元启发式算法,它通过模拟化学反应中分子运动这种自然现象得到。算法的核心是四种基本操作:撞墙、分解、交换和合成。交换和撞墙操作可以对局部最优值进行有效的搜索。而为了不让搜索停滞在局部最优值里,合成和分解操作可以有效的拓展搜索的领域,从而尽可能的获取到全局最优值。CROTM充分利用CRO的优势,有效地扩展了搜索空间,从而大大提高了获取到全局最优解的可能性。在算法的低功耗调度阶段,针对现有策略时间复杂度高、忽略任务相关特性对低功耗技术节能效果的影响等问题,本文在分析现有算法的基础上,结合当前流行的动态电压缩放技术,基于关键任务能对调度长度进行有效控制的特性,提出一种综合考虑任务能耗和时间属性对节能效果的影响的低功耗调度策略。首先利用任务的关键性为优先级对任务进行调度,延长松弛时间,增大系统降低功耗的潜力;然后根据任务的能耗和时间属性,设计一种任务缩放优先级的计算方法,在满足截止期和依赖关系的条件下,反复选择具有最佳节能效果的任务进行电压调节,优化每次迭代过程中的系统能耗。为了验证上述算法,本文基于TGFF工具,利用C++程序描述语言分别实现了本文算法和对比算法,以运行时间和节能率作为性能指标,对算法进行对比分析,实验结果表明本文提出的任务划分策略有效地扩大了问题的解空间,为下一阶段的低功耗调度提供了更加丰富的任务分配方案;而本文提出的低功耗调度策略在显著降低系统能耗的同时也有效地降低了算法的时间复杂度。