摘 要

随着半导体技术和嵌入式系统的广泛应用、以及应用设备的功能性增强，人们对操作系统、处理器的性能上的需求也越来越高。当下，多核处理器代替单核系统几乎普及各行各业，多核技术也趋于成熟，能耗问题在计算机系统的设计和使用中有着越来越重要的作用。如何充分发挥多核系统的优势，提高处理器效率，在当下仍是一个炙手可热的课题。

尽管现在对于多核处理器的任务调度技术已经被广泛讨论，很多研究给出了独立的任务调度算法，但是在多核系统中至今没有明确的任务调度的规范，基于多核处理器的算法研究，还有很长的路要走。

本次设计中，我结合遗传算法对多核系统的任务调度提出自己的一套解决方案，这个任务分配策略是基于划分法和负载均衡的，在异构多核系统中，由于各处理器核之间的差异，以及任务之间的相关关系，首先需要对任务集进行合适的划分，将多任务划分至匹配程度较高的处理器中，然后在构成多核系统的单核处理器上进行任务调度，及时处理空闲时间，在最大程度上利用多核处理器资源，提高多核系统的运行效率。

算法在matlab上进行测试，通过大量数据的仿真后，初步验证了算法的有效性，然后借与前人的算法功能进行比较得出该算法在任务的划分上有一定的作用。

关键词：任务调度，多核处理器，DVS，遗传算法

Abstract

With the widely application of the semiconductor technology and embedded systems, equipment and application of functional enhancements, the demand on the performance of the operating system, processor, more and more is also high. And multi-core processors and almost universal in all walks of life, instead of a single core system of nuclear technology, tend to be more mature, the energy consumption problem in the design and application of the computer system is more and more important role. How to give full play to the advantages of multi-core systems and improve processor efficiency is still a hot topic in the present.

Though the task scheduling for multi-core processor technology has been widely discussed, a lot of research is given independent task scheduling algorithm, but in a multi-core system has not been clear specification of task scheduling, based on the study on the algorithm of multi-core processors, there is still a long way to go.

Genetic algorithm combining with the design, I for multicore systems of task scheduling is put forward a solution, the task allocation strategy is based on dividing method and the load balance, in a heterogeneous polynuclear system, due to the difference between each processor cores, and the correlation between tasks, first of all need to the appropriate division of the task set, match the multitasking division to high degree of processors, and then constitute a multicore systems on a single core processor scheduling, timely deal with free time, and using the maximum multi-core processor resources, improve the efficiency of multicore systems.

Algorithm in matlab to test, through large amounts of data simulation, preliminary to verify the effectiveness of the algorithm, and then by comparing with previous algorithm function it is concluded that the algorithm has the certain function on the division of tasks.

Key Words：Task scheduling, multi-core processor, DVS，genetic algorithm

目 录

第1章 绪论 1

1.1研究目的及意义 1

1.2 国内外研究现状 2

1.3 研究内容说明 3

1.4 论文结构 3

第2章 方案论证及选择 5

2.1遗传算法 5

2.2 动态电压频率调节DVS 6

2.3划分法并行调度方案 7

2.4 方案规划 8

第三章 基于多核处理器的任务调度算法 9

3.1基本思想 9

3.2 实验模型 9

3.2.1 系统模型 9

3.2.1 任务集模型 10

3.3 算法分析 11

3.4 算法伪代码 12

第四章 软件设计实现 13

4.1 问题具体范例模型 13

4.2 遗传算法在matlab上的设计实现 15

4.2.1 交叉算子 16

4.2.2 变异算子 17

4.2.3 选择算子 17

4.2.4 适应度函数 17

4.3 运行结果分析 18

第五章 总结 20

参考文献 21

致谢 22

第1章 绪论

在对单核处理器的性能进行完整全面的发掘后，单核处理器已经不能再适应人们对于CPU的需求，随着并行策略的提出，多核技术走进了人们的视线，多核处理器现在已经应用在生活、生产、科技领域中的方方面面。在多核处理器研究领域,任务调度问题一直是经久不衰的课题。多核处理器存在同构多核处理器和异构多核处理器两种形态，因为结构的不同，在CPU资源的分配上也会有不同的调度方法。本题目通过将遗传算法结合异构多核处理器的特征，尽最大能力将任务与处理器进行匹配，进而达到处理器资源的充分利用。

1.1研究目的及意义

随着科学的进步和计算机技术的高速发展，人们对于计算机的性能的要求也提出了更高的要求，在对单核处理器提升性能的过程中，由于处理器性能等于系统主频与IPC的乘积，IPC是指每个时钟周期内可以执行的指令数，主频则是每秒中周期性变化的次数，那么在提升处理器的运行效率时，可以考虑提高系统的主频或者IPC值。但由于电磁学知识，我们知道主频并不能无限提高，进而在改进处理器时开始着眼于IPC的提升，IPC和系统的架构有很大的联系，但对单核架构来说，IPC的提升幅度也是很有限的。IPC可以通过提高并行度实现，并行度启发了多核架构的出现，从而人们发明出了双核乃至多核处理器。与单核处理器相比，由于并行架构的实现，一方面增加了同时可以运行的进程数，另一方面还能降低频率分摊功率，多核处理器拥有更强的并行计算能力、更高的计算密度和更低的时钟频率。

现在多核处理器主要有同构多核和异构多核两种核心结构，同构多核结构采用对称设计，其中的处理器核都是相同的，硬件结构较为简单，异构多核则是将不同单处理器结合起来通过总线连接在一个系统中。任务集在进入多核系统前或多或少会对其进行判定，从而决定分配的方向。