第
4
章
基于粒子群算法的多核系统线程调度研究
导优化搜索,由
Kennedy
和
Eberhart
提出来的,并因算法实现简单、所需参数少及
具有全局优化能力等特点,迅速在许多领域得到了应用。在
PSO
算法中,依据每个
粒子对环境的适应度将个体逐步移到较优的区域,并最终搜索、寻找到问题的最优
解。
在解决优化问题方面,
PSO
算法设定每个优化问题的潜在解都是解空间中的一
颗粒子,粒子是无体积无质量的一个多维空间点,即粒子的位置就是一个潜在的解
每个粒子由一个被优化的函数获得一个合理的适应值,且每个粒子根据速度的方向
和大小来决定搜索的方向和距离。随后根据当前的最优粒子在解空间中进行搜索。
PSO
初始化为一群随机粒子
(
随机解
)
,利用迭代找到所有粒子群中的最优解。在每
一次迭代中,粒子利用搜索到两个极值来更新自己在解空间的位置。一个极值为个
体极值,它是粒子本身所找到的最优解。另一个极值是全局极值,它是整个种群目
前找到的最优解。另外,在整个种群中利用其中一部分作为粒子的邻居,因此所有
邻居中的形成的极值为局部极值。
粒子群是一类求解连续全局优化问题的进化算法,算法采用实数编码,解个体
用矢量表示,维数由问题的实际情况决定;而线程调度是一系列线程执行顺序列表
属于离散范畴。如何找到二者之间的对应关系,把粒子矢量信息转换为对应满足拓
扑关系的调度列表是目前基于粒子群算法的线程调度问题的研究热点,目前主要是
考虑将粒子中的矢量值与线程调度中线程的优先级联系起来,从而影响线程的调度
1.3
论文的主要研究工作及组织结构
本论文的主要研究工作是在熟悉多核处理器结构的基础上,了解多核系统线程
调度算法的基本功能,研究现有的多核系统线程调度算法的优缺点,并改进其中一
种多核系统线程调度算法。
论文的组织结构如下:
本文是关于多核系统线程调度算法的研究,文章共分为五章,具体结构如下所
示:
第一章是引言,主要介绍课题的研究背景及研究意义,介绍了多核系统线程调
度算法的国内外研究现状,并介绍了本论文的主要研究工作及组织结构,给出了本
论文的一个主要预览。
第二章首先是介绍了与多核系统线程调度技术有关的基本概念以及与多核处理
器结构有关的技术,并对本文的多核系统线程调度的研究模型做了简要的概述。
第三章是对现有的多核系统线程调度算法的研究,包括表调度算法、遗传算法
和粒子群算法,并详细的分析了各个算法的调度过程,最终给出了各种多核系统线
程调度算法各自的优缺点。
第四章选取了基于粒子群算法的多核系统线程调度算法进行了更加深入的研究
并在现有的基于粒子群算法的多核系统线程调度算法的基础上进行了改进和优化。
第五章是结束语,是对本论文的工作仅进行了归纳和总结,并指明了改进和完
善的方向。
3