基于麻雀搜索算法的异构多核处理器任务调度

程小辉 童辉辉 康燕萍*

1(桂林理工大学信息科学与工程学院 广西 桂林 541006) 2(广西嵌入式技术与智能系统重点实验室 广西 桂林 541006)

0 引 言

随着高性能计算的发展和AI、机器学习、云技术等技术的兴起,结构单一的处理器系统无法同时满足应用程序的并行计算等多样化需求[1]。因此异构多核处理器应运而生,逐步进入市场。异构多核处理器是由多种类型和不同计算能力的处理核心组成的非对称多核处理器,如何协调这些处理核心间的工作,将任务合理划分,分配到处理器上执行,是异构多核处理器研究的关键。任务调度技术的好坏决定系统执行效率的高低,异构多核处理器领域中针对任务调度策略的研究也是近几年众多学者关注和研究的热点。

任务调度问题已经被证明为NP-hard 问题[2]。目前在异构多核处理器间任务调度的研究领域中,应用较多的有调度技术[3-6]、遗传算法和粒子群算法等启发式算法[7-12]。根据任务优先权大小策略来构造调度序列,合理分配任务至处理器上,基于列表调度算法来迭代寻找最优解,在满足任务间依赖的条件下取得任务的最短完成时间。列表调度技术具有时间复杂度和空间复杂度低的优点,但是对于解质量的优劣无法保证。粒子群算法和遗传算法等智能优化算法通过不断搜索邻域来寻找最优解,在一定迭代中找得优质解的能力较强,深受异构多核处理器任务调度研究领域的欢迎。然而,遗传算法操作复杂、实时性差,难以保证寻优时间;粒子群算法虽然操作简单、容易实现,但易出现粒子陷入“早熟”现象和后期陷入局部最优等困境。

麻雀搜索算法[13]是由中国学者Xue等提出的一种最新的群体智能优化算法,其算法思想来自于麻雀的觅食行为和反捕食行为的启发。该算法主要具有数学模型简单、调用参数少、收敛速度快等特点。目前该算法在函数优化和解决多目标问题上有了初步应用,但在异构多核处理器任务调度领域中对于该算法的使用还是空白阶段。基于上述背景,在研究异构多核处理器平台的任务调度问题中,本文提出一种新的任务调度方法,使用麻雀搜索算法进行迭代寻优,在满足任务间约束依赖的条件下,使得调度任务完成时间最小,提升系统的执行效率。为了验证该算法的性能和可行性,对该算法与遗传算法和改进的粒子群算法进行了实验对比,结果表明该算法的调度能力更加优异。

1 异构多核处理器任务调度研究

1.1 异构多核系统任务调度问题描述

异构多核处理器由核架构模型、任务调度模型和任务调度算法三个部分组成,三者关系如图1所示。系统模型是根据系统的硬件环境搭建的数学模型,反映了处理核心的处理指令、执行操作、时间控制和数据处理能力的相关信息;任务调度模型是指根据子任务之间的约束关系和任务本身的调度属性建立的数据模型,它反映了任务的自身信息和任务间执行的顺序;任务调度算法指在系统模型和任务模型间建立起映射关系的约束规则。图1中,TM(Task scheduling model)表示任务调度模型,PM(Processor model)表示核架构模型,TPA(Task scheduling algorithm)表示任务调度算法。

图1 异构多核处理器任务调度模型

1.2 任务调度模型描述

异构多核环境下,不同处理核心的计算能力存在差异,任务在各处理器中的执行时间以及任务间产生的通信销量不同,因此,在研究任务调度问题上,一般采用有向无环图(DAG)[14]来表述任务之间的依赖关系。为了更清晰描述问题,定义异构多核处理器环境下有m个处理器和n个任务。其中P={P1,P2,…,Pm}为m个处理核心,节点集合T={T1,T2,…,Tn}表示有n个任务,Ti(1≤i≤n)表示第i个任务。节点间的带权有向边代表任务间存在依赖关系,用C={…Ci,j…}表示。C表示任务间的通信数据集合,Ci,j是任务间的有向边权值,代表着两任务间的通信开销。W={…WTi,pj…},表示任务在每个计算核心上处理时间的集合,WTi,pj表示任务Ti在处理核pj上的计算开销。对相关的调度属性做出如下定义:Tentry代表DAG图中的入口任务节点;Texit代表DAG图的出口任务节点;Pred(Ti) 代表任务Ti的前驱任务节点集合,若Pred(Ti)=∅,则该任务为入口任务节点;Succ(Ti)表示任务Ti的后继任务节点,若Succ(Ti)=∅意味着该任务为出口任务。

如图2所示,举例一个DAG图,任务数为9。T1到T9表示任务,有向边上的值用来表示通信开销,编号旁边数字代表任务处理需要的时间。同一处理器中的任务之间没有通信开销;不同处理器间任务具有依赖约束条件,通信开销不可忽略。例如,T1是T4的前驱任务,它们的处理时间分别为2和4,若它们在同一处理器上,通信销量为0,否则为1。

图2 DAG任务图实例

在考虑到任务间互联,具有约束关系的前提下,将n个任务分配到m个处理器上执行完成最短时间作为本文研究目标, 并且要满足以下约束条件:(1) 每个处理器都可执行任务;(2) 同一时刻,任务无法被多个处理器执行;(3) 任务间满足依赖约束条件。任务间有先序后继关系。任务调度的目标函数描述如下:

makespan(f)=min{makespan(s)}

(1)

式中:s表示为调度的任意一种方案,makespan(s)指在s调度方案中所有任务的最晚完成时间,也称作调度长度;makespan(f)表示求得一个最佳调度方案f,在满足任务间互联和通信的前提下,任务被合理分配到各处理器上处理,使所有任务执行的时间最短,即调度长度最短。

2 麻雀搜索算法

众所周知,群智能优化算法因其不受目标函数可微、可导、连续性等特性的限制,具有较好的稳定性、高效性和收敛速度快等优点。正是如此,群智能优化算法在求解实际工程设计优化问题中越来越受欢迎。

2.1 麻雀觅食行为描述

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

2.2 麻雀搜索算法数学描述

麻雀搜索算法的流程首先初始化种群并且定义相关参数,输出当前麻雀的全局最优位置和全局最优适应度值,并根据当前迭代次数小于最大迭代次数时,对适应度值排列次序,找出当前最好和最差的个体。根据觅食规则,发现者进行位置的更新。加入者则通过围绕在发现者周围获取食物或者从发现者的食物中获取食物,也可以通过争夺获取食物,并更新其位置。当群体的一些麻雀感知到危险后,也会进行相应位置的更新。

假设在d维解空间里有n只麻雀,X代表麻雀的位置。发现者职责;(1) 为种群寻找食物;(2) 为加入者指引觅食方向。根据这一规则,发现者的位置更新如下:

(2)

式中:itermax表示最大迭代次数,t为当前迭代数;Xij表示第i个麻雀在j维中的位置信息;R2和ST分别代表预警值和安全值,取值范围分别为R2∈[0,1],ST∈[0.5,1.0];Q和α∈(0,1]代表随机数,Q服从正态分布;L表示所有元素为1的1×d矩阵。由式(2):R2

加入者(追随者)的位置更新描述如下:

(3)

式中:Xp是当前发现者占据的最优位置,Xworst则表示当前全局最差的位置;A表示一个1×d矩阵,矩阵内元素随机赋值为1或-1,并且A+=AT(AAT)-1。若i>n/2,则代表第i个加入者未得到食物,适应度低,处于饥饿状态,此时需要飞往其他地方觅食来获得能量。

当意识到危险时,麻雀种群会做出反捕食行为,其数学表达式如下:

(4)

式中:fi代表当前麻雀个体的适应度值;fg和fw分别是当前全局最佳和最差的适应度值;Xbest代表当前的全局最优位置;作为波长控制参数的β是一个标准的0和方差分布的随机数;K∈[-1,1]是一个随机数,代表麻雀捕食方向;ε是最小的常数,以避免分母出现零。

fi>fg时,代表此时的麻雀位于种群边缘,极易被捕食者攻击。

fi=fg时,表明位于种群中间的麻雀意识到危险,需向其他麻雀靠拢以避免自己被捕食的风险。

SSA之所以拥有良好的优化性能与麻雀种群内部灵活的觅食机制联系密不可分。首先,发现者能够为整个种群的觅食提供正确的引导,即探索阶段;其次,麻雀察觉到危险后采取的反捕食行为增强了种群的局部搜索能力,即开发阶段;再者,加入者或者追随发现者进行局部搜索,或者改变自身的觅食行为转变为发现者进而对全局进行搜索。由此可见,该算法具有平衡局部开发和全局搜索的能力,以及收敛速度快、稳定性强等特点,为解决复杂的优化问题提供一种全新的方法。

3 基于麻雀搜索算法的异构多核任务调度

3.1 麻雀个体编码

异构多处理器任务调度问题是一种属于离散范畴的优化问题,而SSA是一种连续算法,主要用来解决寻解连续化的问题。在异构多核环境下,任务调度算法在考虑如何提高系统效率的同时,如何最大限度地减少任务执行时间、降低通信负载、提高资源利用率也是众多学者关注的热点。所以,使用SSA解决异构多核处理器任务调度问题,为清晰表述任务调度的潜在解决方案,必须设计合理的编码方案。考虑到任务调度问题的性质,本文根据任务的优先次序[15]设计编码表,由随机函数随机产生小于任务总数的正整数序列,将每一只麻雀觅食位置的矢量信息转换成满足一定互联结构的任务调度序列表。麻雀觅食位置矢量定义为一个矩阵X。

(5)

对于任务i赋予的1～d的随机数,表示任务i的优先权Pi,从而将群体中麻雀觅食的一个连续位置向量Xi=Xi,1,Xi,2,…,Xi,d]转化为一个任务优先级序列π=(p1,p2,…,pd)。每一个潜在解都是有效的,麻雀搜索算法在搜索进程中不会被修改信息。表1是P1、P2两个处理器上任务分配(见图2)时的编码方案。

表1 任务分配编码方案

3.2 解码方案

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

f(x)=max{eft(Ti)}i=1,2,…,n

(6)

式中:eft(Ti)表示任务Ti的最早执行完成时间。在计算调度长度时需要对编码方案进行解码,参照任务优先级规则排列任务的调度序列,要求前驱任务被执行完之后下一个任务才能调度;并且在满足任务间约束依赖的条件下,高优先任务被执行完后,下一级任务才会被执行,由此可以确定一个任务调度列表。

经过以上分析可知,最后一个任务执行完成的时间就是全部任务完成的时间,用eft(Ti)表示。ci,j表示任务在处理器上的通信开销。若任务为入口任务节点,则任务的全部完成时间为cTi,Pj。若任务存在先序任务节点,则任务完成的全部时间为任务Ti的直接前驱任务Tj的计算产生的开销与任务间通信开销和的最大值。计算公式如下:

(7)

任务优先级值和处理器数目被取余操作以获得对处理器的任务分配。任务分配解码方案如表2所示。

表2 任务分配解码方案

3.3 SSA异构多核处理器任务调度算法流程

基于麻雀搜索的任务调度算法流程如下:

(1) 读入应用程序的DAG图,根据优先级规则确定调度序列。

(2) 初始化种群及初始位置,设置SSA相关参数和迭代次数。

(3) 计算麻雀的适应度fitness(),将种群分为发现者和追随者,设置麻雀的Xbest。

(4) 计算预警值,根据预警更新发现者的位置。

(5) 根据式(3)更新跟随者的位置。

(6) 根据式(4)更新发现危险的麻雀的位置。

(7) 判断是否达到itermax,若达到,输出最优位置最优解,算法结束;否则转步骤(3)进行下一轮搜索。

SSA的流程如图3所示。

图3 SSA流程

4 实验仿真与分析

本文在MATLAB 2017a仿真环境下对SSA、GA和改进的IPSO[11]的性能进行了比较验证,对比标准选择任务完成时间的平均值和算法适应度和最优调度长度。

本文实验参数设置如下:麻雀搜索算法,PopSize为100,MaxGen为600,ST=0.8;文献[11]中改进的粒子群算法,PopSize为100,MaxGen为600,c1=c2=2,wmax=0.9,wmin=0.4;遗传算法: PopSize为100,MaxGen为600,pc=0.8,pm=0.3,该实验测试了分布在5个处理器上的100、200、300、400和500个任务调度结果,并在MATLAB 2017a模拟平台上执行了上述三种算法。为了减少数据随机造成的实验结果偏差,更精确反映出算法的性能,全部任务完成时间取50次重复测试中得到最优解的平均值。

图4为SSA、GA和IPSO在100个任务和5个处理器条件下适应度值-迭代次数曲线。可以看出相较于GA和IPSO,SSA寻得最优解的迭代次数更少、适应度更低、最优解质量高,从而全部任务执行完成的时间更短,SSA具有快速收敛、高效求解的特点。

图4 算法适应度值对比

图5为使用以上三种算法在5个处理器和5个不同任务规模下的最优调度长度结果,可以看出对于调度长度,SSA的调度长度最短、最优解质量最高,IPSO次之,GA调度长度最长、最优解质量最差,随着任务数的数量增加,这种效果越明显。GA和 IPSO易出现“早熟”现象,陷入局部最优,而SSA稳定性更好、收敛速率高。

图5 最优调度长度对比

图6为在不同任务数情况下三种算法的平均调度长度对比,即算法的平均执行时间。由图6可知,相较于GA和IPSO,SSA的平均执行时间更短,尤其是任务数量增多时,这种差异越发明显,SSA的性能明显优于GA和IPSO。

图6 算法执行时间对比

通过实验结果与分析,在异构多核任务调度问题上,SSA执行的完成时间(平均解)比GA执行时间缩短21.48%,比IPSO执行时间缩短17.52%。由此可知,相较于其他两种算法,SSA的收敛速度更快、寻优能力更强、稳定性更强、算法性能优良,适合异构多核处理器环境下的大规模任务调度应用工程。

5 结 语

为了提升异构多核处理器任务调度的效率,本文根据麻雀搜索算法提出一种新的异构多核处理器任务调度算法,充分利用其收敛速度快的特点来获得高精度解特性。在本文异构环境下的任务调度中,以全部任务的执行时间最短作为目标,根据任务优先权,设计任务分配编码方案,将麻雀搜索空间映射到离散空间,使麻雀搜索算法适用于离散的异构多核任务调度问题研究上。通过与任务调度研究中应用较多的遗传算法和改进的粒子群算法进行性能测试比较,SSA简单有效、求解的质量更高、收敛速度更快,有效缩短任务执行时间,在异构多核处理器任务调度领域中研究价值高,应用前景广阔。