张海燕　刘彦　陈晓明　赵一弘

摘 要：提出了基于遗传算法的面向动态异构多处理器的调度算法（Heterogeneous Scheduling Genetic Algorithm，HSGA），该算法利用连续的多个调度时间片完成遗传算法的迭代计算，在保证计算效率的同时获得较好的调度结果，从而为每个应用选择符合其计算特性的处理器内核.仿真实验表明，本文算法在4核、8核和16核的平台上相比较于经典的匈牙利算法ED2仅分别增加了0.4%，1.1%和1.3%，新的调度算法相比于匈牙利算法和Local调度算法具有更好的调度效果及更好的动态适应性.

关键词：遗传算法；任务调度；功耗控制

中图分类号：TP316.4 文献标识码：A

Abstract：This paper presented an improved scheduling algorithm for dynamic heterogeneous chip multicore processors（Heterogeneous Scheduling Genetic Algorithm，HSGA ）.The proposed scheduling algorithm uses time slices of OS scheduler to complete the iterative procedure of HSGA， which can obtain efficient task scheduling results and choose the best process core for each application task. The experiments using SESC simulator show that the ED2s of the proposed algorithm are only 0.4%， 1.1% and 1.3% higher than those of a baseline classic Hungarian Algorithm with 4 cores， 8 cores and 16 cores chip multiprocessor respectively with random degradation. And the proposed algorithm can generate more stable and adaptive results for unpredictable heterogeneity， compared with Hungarian Algorithm and Local Search Algorithm.

Key words：genetic algorithms；task scheduling；power control

半导体技术的飞速发展使得设计者可以将更多晶体管或者处理器内核集成到一个单芯片上从而构成片上多处理器芯片（Chip Multiprocessor，CMP）.多处理器芯片已经在服务器计算、桌面系统、甚至于嵌入式计算系统中占据了重要的地位，成为目前主流的处理器结构.多核处理器为计算系统带来高性能的同时，也在芯片可靠性方面带来了新的挑战[1-2].

随着片上多处理器芯片的规模逐渐扩大，芯片制造和使用过程中的不可控因素造成的同构处理器性能和关键参数的异构性，成为体系结构和系统层面不可忽视的因素和挑战.就算是在单个晶圆内，由于生产工艺和流程的影响也可能导致各个处理器内核的功耗、最大工作频率等关键参数不同.在这种情况下，原本按照同构片上多处理器设计的CMP芯片可能具有异构性[3-4].大规模同构CMP芯片将面……