论文部分内容阅读
性能不对称的单指令集异构多核处理器能够很好的适应程序行为的多样性,实现资源的按需分配,避免资源的过剩与不足,从而比同构多核处理器具有更好的性能功耗比,在低功耗绿色计算中拥有巨大潜力,得到了学术界和工业界的广泛关注。
单指令集异构多核处理器能效优势的发挥需要借助于操作系统的支持。操作系统必须合理调度,让所有程序尽可能运行在性能功耗比最佳的处理器核上。首先,操作系统要能够感知到异构多核,同时能够准确而快速地识别程序的行为,最后根据这些信息以及系统的实际运行状况进行合理的任务调度。目前常用操作系统中的调度算法都是针对同构多核处理器设计的,既不能感知异构多核的存在,也没有程序行为识别的功能,面向单指令集异构多核系统任务调度算法的设计十分必要。
本文以真实硬件和Linux操作系统为平台,从程序行为在线分析和离线分析两个视角设计了几种调度算法,同时应用多目标优化遗传算法对异构多核系统静态任务调度进行了仿真研究。本文的主要贡献和创新点有以下几个方面:
1、提出了一种基于程序行为在线分析的负载均衡调度策略。分析了现有的异构多核调度算法单一强调“快核优先”的不足,指出负载均衡是任务调度的基础。提出了不用阈值的任务迁移算法,克服了使用阈值区分程序类别存在的不足。提出使用绝对IPC作为任务属性的度量标准,解决了相对度量标准需要试探运行的弊端。实验结果显示,与现有的Linux调度算法相比,最大加速比超过10%。
2、提出了一种基于程序行为离线分析的调度框架。离线分析方法不依赖于性能计数器,运行时开销小,可扩展性强,适用范围广。给出了基于离线分析进行任务调度的基本框架以及具体方法,重点讨论了二进制文件的静态注入及程序行为感知的任务分配算法。该调度框架既适用于基于程序行为离线分析的调度算法设计,也适用于Shared-ISA异构多核任务调度。实验结果显示,当任务较少时,基于离线分析的长度感知任务分配算法比随机分配算法性能提升明显,甚至达到1倍。任务较多时性能提升不如任务较少时明显,但与负载均衡调度相结合,比随机分配算法平均性能提升7%左右。
3、提出了一种缓存感知和拓扑感知的负载均衡算法。现有Linux操作系统在迁移任务时不考虑访存行为的差异,简单的从队尾依次选择待迁移任务,可能造成共享缓存、访存带宽的争用,影响系统的整体性能。通过在线监测每个任务的每千条指令缓存失效次数(cache Misses Per Kilo Instructions,MPKI),当需要迁移任务时,首先比较源处理器核与目标处理器核的平均MPKI,然后决定迁移MPKI最大或最小的任务,从而将访存较多的任务与访存较少的任务分开,减少资源争用。该算法无需设定阈值,同时适用于单线程和多线程程序,运行时开销小。实验结果表明,与缓存不感知的默认调度算法相比,工作负载的整体性能平均提升5%左右。
4、将多目标优化遗传算法应用于异构多核处理器静态任务调度。基于Pareto优化的SPEA2算法,以时间和能耗作为优化目标,寻找异构多核任务调度的Pareto最优解集。针对现有算法使用高度值确定任务执行顺序的不足,提出使用先序关系矩阵表示任务之间的依赖关系,可以找到高度值方法可能漏掉的最优解。重新定义了染色体编码结构中表示任务先后顺序的基因位的含义,将所有任务的全局排序改为没有依赖关系的两个任务之间的局部顺序,使种群初始化时的有效个体所占比例变为100%。仿真结果表明,使用先序关系矩阵比使用高度值方法能够得到更优的调度序列。