一种面向异构多核处理器的混合式任务调度方法

摘要

本发明提供了一种面向异构多核处理器的混合式任务调度方法。该方法以麻雀搜索算法为基础进行优化，在异构多核环境下的任务调度中，对HEFT算法中任务节点的优先级别进行排序，构造一个任务调度列表，同时设计合理的任务分配编码方案，将麻雀搜索空间映射到离散空间，使麻雀搜索算法适用于离散的异构多核任务调度问题研究上。本发明将HEFT算法与麻雀搜索算法混合，将HEFT算法获得的任务列表加入到麻雀搜索算法的初始化种群中，利用麻雀搜索算法寻优能力强，收敛速度快，性能稳定等优势，执行算法的迭代，从列表中取出优先级最高的任务，将其分配给启动时间最早的处理核上。本发明有效缩短任务执行时间，提升异构多核环境下的任务调度效率。

说明书

技术领域

本发明涉及操作系统领域，具体为一种表调度算法和麻雀搜索算法混合的任务调度方法。

背景技术

随着高性能计算的发展和AI、机器学习、云技术等技术的兴起,结构单一的处理器系统，无法同时满足应用程序的并行计算等多样化需求。因此异构多核处理器应运而生，逐步进入市场。异构多核处理器是由多种类型和不同计算能力的处理核心组成的非对称多核处理器，如何协调这些处理核心间的工作，将任务合理划分，分配到处理器上执行，提升异构多核环境下的任务调度效率，是操作系统领域研究的重点。

任务调度技术的好坏决定系统执行效率的高低，在异构多核处理器间任务调度的研究领域中，传统的任务调度技术一般是基于列表调度算法或者粒子群算法和遗传算法来迭代寻找最优解，在满足任务间依赖的条件下取得任务的最短完成时间。列表调度技术具有时间复杂度和空间复杂度低的优点，但是对于解质量的优劣无法保证。粒子群算法和遗传算法等智能优化算法通过不断搜索邻域来寻找最优解，在一定迭代中找得优质解的能力较强，深受异构多核处理器任务调度研究领域的欢迎。然而，遗传算法操作复杂，实时性差，难以保证寻优时间；粒子群算法虽然操作简单，容易实现，但易出现粒子陷入“早熟”现象和后期陷入局部最优等困境。麻雀搜索算法具有数学模型简单，调用参数少，收敛速度快，寻优能力强等特点，具有较高的全局探索能力和局部开发能力。基于上述背景，我们将列表调度算法与麻雀搜索算法相结合，设计出一种更好的面向异构多核处理器的混合式任务调度方法来缩短总的任务调度长度，提高异构多核环境下的任务调度效率，提升操作系统的性能。

(1)异构多核处理器

异构多核处理器是由多种类型和不同计算能力的处理核心组成的非对称多核处理器，异由核架构模型，任务调度模型和任务调度算法三个部分组成，系统模型是根据系统的硬件环境搭建的数学模型，反映了处理核心的处理指令、执行操作，时间控制和数据处理能力的相关信息；任务调度模型是指根据子任务之间的约束关系和任务本身的调度属性建立的数据模型，它反映了任务的自身信息和任务间执行的顺序；任务调度算法指在系统模型和任务模型间建立起映射关系的约束规则。

(2)HEFT算法

表调度算法HEFT算法的基本思想是以最早完成时间最短为目标，对任务节点的优先级别进行排序，构造一个任务调度序列，从列表中取出优先级最高的任务，将其分配给启动时间最早的处理核上，重复以上步骤，直至多有任务被调度完毕。算法分为两个阶段，在任务排序阶段，通过计算任务节点的优先权值，对他们进行排序构建一个任务调度列表。在任务分配阶段任务分配至处理核心上执行时要对整个DAG图进行遍历，考虑任务间的依赖关系将任务分配到适合的计算内核上，实现任务的总的完成时间最短的目标。

(3)麻雀搜索算法(SSA)

麻雀搜素算法(SSA)主要模拟麻雀群觅食的过程，麻雀是群居类鸟类动物，根据其觅食特点，可分为探索者(发现者)和加入者(追随者)，定义为发现者-加入者行为策略，同时叠加了麻雀侦查预警机制。所有麻雀都只有一个属性：位置，代表麻雀找到食物的位置，每只麻雀有三种可能行为：1.作为发现者：负责寻找食物和引导整个群体的移动；2.作为加入者：过追随发现者来获取食物；3.警戒侦查：发现危险，告知同伴，并且放弃食物，转移到新的觅食区域。除此以外，有研究表明，麻雀深谙行为策略，可在发现者和加入者两种角色中任意转换。

发明内容

为提高异构多核环境下的任务调度效率，本发明提出了一种面向异构多核处理器的混合式任务调度算法。这种算法通过将表调度算法以及麻雀搜索算法混合，使用麻雀搜索算法进行迭代寻优前，对HEFT算法获得的任务调度列表进行编码，实现了麻雀与任务调度列表之间的映射。

本发明的技术方案为：

在HEFT算法中构建一个任务调度列表。在使用麻雀搜索算法进行迭代寻优前，要考虑任务调度的性质，设计合理的编码方案以完成麻雀与任务调度列表之间的映射。随机产生一定的麻雀数量，初始化种群，这些麻雀即为任务调度的探索空间；对种群中的麻雀进行发现者位置的更新，跟随者位置更新和侦查预警等操作，计算每一只麻雀的适应度值，在每一次迭代中，选取适应度值较大的麻雀作为发现者，将适应度值较小的麻雀从发现者行列中剔除。更新发现者-跟随者模式。经过多次迭代进化，最终选择种群中适应度值最高的麻雀位置作为任务调度中的最优解的编码。技术方案流程如下：

步骤1：遍历整个DAG图，标记出关键路径；

步骤2：计算当前任务到出口任务的通信开销和当前任务在处理器上执行的处理开销以及任务在不同处理器上执行时间的方差；

步骤3：计算步骤2中三者和的最大值作为rank

步骤4：对HEFT算法获得的任务调度列表，设计合理的编码方案以完成麻雀与任务调度列表之间的映射；

步骤5：随机产生一定的麻雀数量，初始化种群；

步骤6：计算种群中每只麻雀的的适应度值；将种群分为发现者和追随者，设置麻雀的X

步骤7：计算麻雀的适应度fitness(),将种群分为发现者和加入者，设置麻雀的X

步骤8：更新发现者、加入者意识到危险的麻雀位置；

步骤9：判断是否达到inter

步骤10：将步骤9得到的最优解分配到最早开始时间最早的处理器上执行，每一次任务分配执行后将其从调度列表中删除；判断任务调度列表是否为空，若列表非空则转到步骤4；若列表为空，则算法结束，任务调度全部完成。

附图说明

图1为任务调度模型，其中TM表示任务调度模型，PM表示核架构模型，TPA(表示任务调度算法；

图2为基于麻雀搜索算法任务调度的流程图；

图3为SSA算法、GA算法和IPSO算法在100个任务和5个处理器条件下适应度值—迭代次数曲线；

图4为使用以上三种算法在5个处理器和5个不同任务规模下的最优调度长度结果；

图5为在不同任务数情况下三种算法的平均调度长度对比，即算法的平均执行时间。

具体实施方式

下面将结合附图、表和具体实例对本发明作进一步详细描述。

步骤1：遍历整个DAG图，标记出关键路径；

步骤2：计算当前任务到出口任务的通信开销和当前任务在处理器上执行的处理开销以及任务在不同处理器上执行时间的方差；

步骤3：计算步骤2中三者和的最大值作为rank

步骤4：对HEFT算法获得的任务调度列表，设计合理的编码方案以完成麻雀与任务调度列表之间的映射，包括如下子步骤：

步骤4.1:编码方案

对HEFT算法获得的任务调度列表，设计合理的编码表，由随机函数随机产生小于任务总数的正整数序列，将每一只麻雀觅食位置的矢量信息转换成满足一定互联结构的任务调度序列表。麻雀觅食位置矢量定义为一个矩阵X。

对于任务i赋予的1～d的随机数，表示任务i的优先权P

表1任务分配编码方案

步骤4.2：解码方案

在得到麻雀觅食位置的信息之后，根据其适应度的好坏将麻雀分类成发现者和跟随者。以确定发现者未来新的觅食方向。本文将调度长度makespan，即任务调度的全部完成时间作为目标函数。makespan越小，全部任务的最晚完成时间越短，调度方案可行性越高。目标函数公式如下：

f(x)＝max{eft(T

其中，eft(T

经过以上分析可知，最后一个任务执行完成的时间就是全部任务完成的时间,用eft(T

其中，

表2任务分配解码方案

步骤5：随机产生一定的麻雀数量，初始化种群；

步骤6：计算种群中每只麻雀的的适应度值；将种群分为发现者和追随者，设置麻雀的X

步骤7：计算麻雀的适应度fitness(),将种群分为发现者和加入者，设置麻雀的X

步骤8：更新发现者、加入者意识到危险的麻雀位置；

步骤9：判断是否达到inter

步骤10：将步骤9得到的最优解分配到最早开始时间最早的处理器上执行，每一次任务分配执行后将其从调度列表中删除；判断任务调度列表是否为空，若列表非空则转到步骤4；若列表为空，则算法结束，任务调度全部完成。