基于多目标遗传算法的单指令集异构多核系统静态任务调度  

Static Task Scheduling for Single-ISA Heterogeneous CMP System Based on Multi-objective Genetic Algorithm

作　　者：徐远超[1,2] 张志敏[2] 蒋毅飞 

机构地区：[1]首都师范大学信息工程学院,北京100048 [2]中国科学院计算技术研究所计算机体系结构国家重点实验室,北京100190 [3]上海高性能集成电路设计中心,上海201204

出　　处：《小型微型计算机系统》2012年第10期2237-2242,共6页Journal of Chinese Computer Systems

基　　金：国家"九七三"重点基础研究发展计划项目(2011CB302501)资助;北京市教委科技计划面上项目(KM201210028004)资助

摘　　要：与同构多核处理器相比,单指令集异构多核处理器能够更好的匹配程序行为的多样性,从而具有更好的性能功耗比.异构多核处理器的能效优势依赖于操作系统合理而有效的调度,追求性能与功耗的统一,是典型的多目标优化问题.提出将多目标优化遗传算法应用于寻找异构多核环境下最优的静态任务调度方案,提出表征任务相对顺序的染色体编码结构,使种群初始化时的有效个体所占比例变为100%.提出使用先序关系矩阵来确定任务的执行顺序,克服了高度值方法存在的严重不足.仿真结果表明,先序关系矩阵方法能扩大搜索范围,在种群规模足够大时,可以找到高度值方法漏掉的部分最优解.Compared with homogeneous multi-core processor,single-ISA heterogeneous multi-core processor can achieve better performance per watt since they can adapt to workload diversity.Energy efficiency of this architecture depends on reasonable and intelligent task scheduling.This is typical multi-objective optimization problem since both performance and power are required.This paper applies the Pareto-based multi-objective optimization genetic algorithm to the static task scheduling on heterogeneous multi-core systems.Priority matrix is proposed to overcome the deficiency of using height to decide the execution order of tasks and also change the chromosome encoding and decoding structure.By using this method,the number of valid chromosomes from initial population increases to 100%.Simulation result shows that comparing to height,priority matrix leads to more optimized scheduling list.

关 键 词：异构多核 任务调度 多目标优化 遗传算法 性能功耗比 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]