基于离散粒子群优化的可重构系统任务调度算法

祁晓峰,张兴明,高彦钊

(国家数字交换系统工程技术研究中心,郑州 450002)

1 引 言

可重构系统由通用处理器和可重构计算器件组成,支持不同应用程序灵活地配置和执行.可重构计算处理器在功能灵活性上类似通用处理器,在功耗能效上接近专用计算电路,兼具软硬件计算资源的优点,是高效能计算处理器研究的重要方向.在执行应用程序的过程中,可重构系统编译器将应用划分,按一定顺序配置和执行任务.由于可重构计算资源有限,为充分利用资源,划分到可重构器件上的任务需要动态配置.如何灵活地调度硬件任务,保持较高的资源利用率,以及如何通过调度策略保证软硬件任务合理配合,缩短任务完成时间是可重构系统任务编译的关键问题.

为解决可重构系统的任务调度问题,国内外学者已经做出丰富的研究.可重构系统任务调度问题属于NP(Non-Deterministic Polynomial)问题[1],需要优化算法的运行时间,同时保证算法解的质量.研究学者将启发式方法,尤其是智能种群算法和仿生算法[2-4],引入到可重构系统任务调度模型中,求解任务调度问题时间快并且能够得到较高质量的任务调度方案.评价启发式方法的性能主要从以下四个方面:求解质量、运行时间、可靠性和扩展性.大多数基于启发式方法的调度策略能够满足第一个因素,生成高质量的近似最优解.通过优化和调整,其中一些算法能够在较短运行时间内产生调度方案.但是由于启发式方法的结果是随机产生的近似解,因此缺少可靠性.此外,由于缺少扩展性,算法随任务规模增加而求解质量下降,运行时间增加.

另一方面,由于算法针对特定功能和特征的系统,新功能特征的出现导致以前方法不再适用.例如配置预取功能允许配置提前进行.下一个任务配置操作与当前任务的执行操作同时进行,因此配置时间能够有效隐藏在其他任务的执行过程中[5].文献[6]基于配置预取功能设计可重构任务调度策略,能够大幅降低任务调度时间,但是该调度策略的算法复杂度较高.文献[7]在带有配置预取的可重构系统中,使用蚁群算法求解调度策略,极大降低了算法运行时间,但该方法忽略了最优解的可靠性,并且解质量还有待进一步提高.针对以上问题,本文提出一种带有预生成策略的离散粒子群优化算法,充分利用算法优势设计适用于可配置预取的可重构系统的任务调度方案求解策略.

为使用粒子群优化算法解决任务调度问题,本文在第二节介绍可重构系统软硬件任务并行协同调度模型;第三节设计调度方案的编解码策略和离散粒子群算法,根据系统约束设计算法的评价机制,并且提出预处理策略提高算法求解质量和可靠性;第四节进行实验仿真,比较多个数据集下的算法性能;在第五节对全文进行总结.

2 问题描述

2.1 问题模型

任务调度策略面向异构动态部分可重构系统,系统组成架构如图1所示.可重构系统主要由主CPU控制器、通用处理器和可重构计算器件组成.主CPU生成任务调度策略的控制信息和配置信息,控制用于执行软件任务的通用处理器和用于执行硬件任务的可重构计算处理单元(RPU Reconfigurable Processing Unit)进行协同计算.RPU由若干个可以重复配置的可重构单元阵列(RCA Reconfigurable Cell Array)组成,每个RCA都由若干个运算单元(PE Processing Element)排列组合而成.

图1 可重构系统组成架构Fig.1 Framework of reconfigurable system

图2 可重构系统任务调度模型Fig.2 Task scheduling model of reconfigurable system

图2是可重构系统的任务调度模型.系统首先将应用程序代码划分为由可重构器件执行的硬件任务和由通用处理器执行的软件任务.调度器将硬件任务和软件任务协同调度生成调度方案.调度方案包括预配置队列、硬件任务队列和软件任务队列三组调度控制信息.预配置队列的控制信息加载到配置器中为硬件任务配置可重构计算资源.布局器按照硬件任务队列控制信息将硬件任务布局到运算单元阵列执行.软件任务按照软件任务队列控制信息依次在通用处理器执行.在可重构器件上执行的硬件任务需要配置完成后才能运行.配置预取操作指在任务模块运行的同时,同步进行下一个任务的配置,从而达到隐藏配置时间的目的.由于任务模块配置信息从配置资源池中调用,故称该操作为配置预取.配置时间指对可重构器件进行配置编程花费的时间,执行时间是计算任务花费的时间.由于配置时间相对执行时间不可忽略,因此对配置时间进行加速或隐藏是提高可重构系统调度性能的关键.

图3 任务图描述的应用实例

图3是使用有向无环图(Directed Acyclic Graph,DAG)描述的应用任务图实例.设任务图G={T,E}.T={T1,T2,…,Tn}表示任务模块.任务模块有两种类型,S表示软件任务,H表示硬件任务,即T=S∪H.对于任意Si∈S,Si可描述为二元组{tSi,texcute,Si},tSi是任务Si的执行开始时间,texcute,Si是任务Si的执行持续时间.对于任意Hi∈H,Hi可描述为六元组{wHi,hHi,tHi,texcute,Hi,cHi,cexcute,Hi},其中wHi和hHi是硬件任务Hi占用可重构资源的宽度和长度,tHi是任务Hi执行开始时间,texcute,Hi是任务Hi的执行持续时间,cHi是任务Hi的配置开始时间,cexcute,Hi是硬件任务Hi的配置持续时间.E={eij}表示任务Ti和Tj之间的数据依赖关系,|eij|是任务Ti和Tj的通信功耗.|eij|≠0时,任务Ti和Tj之间不存在数据依赖.|eij|≠0时,Ti执行完后才能执行Tj.

为简化表示任务模块在系统中的配置和执行时间,定义任务周期概念如下.

定义1.任务周期Δt是任务配置和执行的最小时间单位.任务配置或执行的时间通过任务周期的规整得到,是整数倍的任务周期.不妨假设任务的配置或执行时间为t,如果(n-1)·Δt

可重构系统采用配置预取隐藏任务配置时间.为用任务图描述配置预取功能,本文采用改进的有向无环图表示任务图.改进的任务图如图4所示.硬件任务的配置操作是一种新的任务模块C(m,n).C(m,n)表示任务Hm在RPUn中进行配置.C(m,n)可描述为二元组C(m,n)=(tc(m,n),texcute,c(m,n)),其中配置任务执行开始时间是任务Hm的配置开始时间,即tc(m,n)=cHm.配置任务的执行持续时间是任务Hm的配置持续时间,即texcute,c(m,n)=cexcute,Hm.配置信息从系统配置资源池中直接调用,配置任务执行持续时间无显著差异,可将配置任务的执行持续时间texcute,c(m,n)统一设置为一个任务周期,即texcute,c(m,n)=Δt.任务调度受到任务时间依赖关系和硬件资源面积的约束.系统基本约束如下:

图4 改进的任务图描述的应用实例Fig.4 An application represented by improved task graph

1)对于任意两个任务Ti和Tj,如果Ti和Tj之间存在数据依赖关系,Ti执行结束的时间不能超过Tj执行开始的时间.

∀eij≠0,tTi+texcute,Ti≤tTj

(1)

2)对于任意硬件任务Hi,Hi配置结束的时间不能超过Hi执行开始的时间.

∀Hi,cHi+cexcute,Hi≤tTi

(2)

3)∀RPUi,在同一时刻,RPUi只能配置或执行一个硬件任务.

4)∀Hi,配置或执行Hi时不能超出系统RPU个数的限制.

图5 可重构系统任务调度时序实例Fig.5 An example of reconfigurable system task scheduling solution

图5是图4所示应用的一个任务调度方案实例.调度方案不同,应用执行所花费的时间不同.任务调度问题的目标是生成一个合理的调度方案,最小化任务执行时间.该调度方案既要满足系统基本约束,又要充分利用空闲计算资源将任务配置过程隐藏.因此本文将任务调度问题看成一个多目标优化(Multi-objective Optimization,MOP)的NP问题,并使用粒子群优化算法解决该问题.

2.2 粒子群优化算法

任务调度问题是一个复杂的组合优化问题,其可能的任务调度方案随任务个数的增加呈指数型增长[8],并且由于任务之间受依赖关系和系统资源的约束,难以求出精确的最优解.因此,在较短时间内找到问题的近似最优解具有重要意义.粒子群优化算法(Particle Swarm Optimization,PSO)是解决该类问题的有效方法,使用PSO算法解决任务调度问题具有以下优势:1)参数简单,易于实现;2)解决指数爆炸问题;3)算法收敛速度快.

使用粒子群优化算法解决最优化问题,问题的解对应搜索空间中的粒子,每个粒子有一个速度决定他们进化的方向和距离.算法通过适应函数(fitness function)评价的每个粒子的适应值.粒子通过适应值评价机制追随当前的最优粒子,在解空间中逐代更新自身的速度搜索最优解.

图6 粒子群优化算法Fig.6 Particle swarm optimization algorithm

粒子群算法基本概念如下.一个由m个粒子(Particle)组成的群体(Swarm)在D维搜索空间中以一定的速度飞行,每个粒子在搜索时,比较自己搜索到的历史最好点和群体内其它粒子的最好点,在此基础上进行位置的变化.第i个粒子的位置表示为xi=(xi1,xi2,…,xiD);其速度为vi=(vi1,vi2,…,viD),1≤d≤D;其个体历史最优点为pi=(pi1,pi2,…,piD),1≤i≤m;群体粒子最优点pg=(pg1,pg2,…,pgD).粒子群优化算法的步骤见图6.

一般来说,粒子的位置和速度都是在连续的实数空间内进行取值,粒子的位置和速度根据如下方程进行变化:

(3)

(4)

其中,ω为惯性权重,c1和c2为学习因子,一般为正常数.学习因子使粒子进行自我学习并向群体中优秀个体学习,朝个体最优值和群体最优值靠近.ξ,η∈U[0,1],是在[0,1]区间内均匀分布的随机数.粒子的速度被限制在一个最大Vmax的范围内.

3 离散粒子群优化任务调度算法

3.1 任务编码

为使用PSO算法解决任务调度问题,首先需要将任务调度方案进行编码作为PSO算法的粒子.不妨假设待调度的任务个数为N,按照任务执行时间顺序和可重构单元阵列序号由小到大的顺序,列出描述调度方案的任务序列P:

P={Ti|i∈N}

(5)

以图5表示的调度方案为例,按照时间顺序,其编码的任务序列为:

P={S1,H1,H3,H2,H5,H4,H6,H7,S2}

(6)

该序列即任务调度问题的一个解.通过以下步骤将该序列表示的调度方案解码.

针对Step 3,具体操作如下:依次从第一个任务周期的第一块RCA开始检查是否有可配置空间.对于已经被占用的配置空间,从该任务配置开始直至任务执行结束是配置空间被占用的时间,该期间根据系统限制不能配置其他任务,任务执行结束后自动清除配置信息并释放配置空间资源.待执行任务一旦定位到空闲资源空间,判断空闲空间资源是否满足任务配置需求,配置需求根据任务的大小决定.若不能满足需求,则等待配置空间释放后配置任务.

表1 调度方案解码步骤
Table 1 Steps for solution decoding

输入：经编码的调度方案输出：解码后的调度结果Step1．载入待执行任务．Step2．判断是否是硬件任务．是，则跳转到Step3；否则，跳转到Step5．Step3．配置任务．Step4．判断是否满足依赖关系．是，则跳转到Step5；否则跳转到Step7．Step5．执行任务．Step6．判断是否是最后一个任务．是，则调转到Step8；否则跳转到Step1．Step7．输出调度结果花费时间．

针对Step 4,依赖关系指任务相关时间依赖关系,是系统的基本约束,包括任务之间的依赖关系和同一个任务配置时间和执行时间的依赖关系.任务调度算法按位依次循环判断该编码能否满足系统的约束条件.

对式(6)中的编码任务序列解码,得到调度方案为:

P:S1→{H1,C1,0,C1,1,C1,2}→{H3,C3,3}→
{H2,C2,0,C2,1}→{H5,C5,2},→{H4,C4,3}→
{H6,C6,0}→{H7,C7,1}→S2

(7)

综上可知,该解码策略保证了任务调度方案与PSO算法的粒子一一对应,构造出任务调度方案的解空间.可使用PSO算法在解空间求解任务调度问题的最优解.

3.2 离散粒子群优化算法

传统PSO算法适用于连续空间的优化问题,而任务调度问题的解是离散的.因此本文对PSO算法的运算符号和规则进行改进以适用任务调度问题.

定义2.交换子SF(i,j).设任务个数为N,任务序列P={Ti|i∈N},交换子SF(i1,i2),i1∈N,i2∈N.Ti1和Ti2是P中的元素,交换子SF的作用是交换任务序列P中任务Ti1和任务Ti2的位置,产生新的任务序列P′.即P′=P+SF(i1,i2).

定义3.交换序SS.交换序SS是多个交换子SF(i,j)的集合,即SS={SF1,SF2,…,SFn},表示按照交换子SFi在集合中的顺序依次进行交换操作.若干个交换序可以合并成一个新的交换序.不同的交换序作用于同一任务序列P上可能产生相同的任务序列,能产生相同效果的交换序的集合是交换序的等价集.在交换序等价集中,拥有最少交换子的交换序是该等价集的基本交换序.

可重构系统任务调度问题的优化目标是最小化应用执行时间,PSO算法的适应函数根据该优化目标,通过计算调度方案的执行时间得到每个调度方案的适应值.在解码过程中记录最后一个任务的执行开始时间,并加上其执行持续时间即整个调度方案实现的所花费的时间,即可得到任务调度粒子群优化算法的适应值.当不同任务调度方案的历史最优或全局最优值出现相同的情况时,算法默认该子代粒子的任务调度方案为最优.

3.3 预生成策略

由于任务调度问题受到的系统约束复杂,按照PSO算法的随机初始化策略存在一定概率不能产生满足系统约束的调度方案,PSO算法初期因搜索盲目而效率降低.本文提出预生成策略解决该问题,提高PSO算法求解任务调度方案的效率.

根据任务图中任务的编号规律可知,任意两个任务Ti和Tj,若i

表2 预生成策略步骤
Table 2 Steps for pre-generation algorithm

输入：按任务序列编号的任务调度方案输出：预生成任务编码调度方案Step1．按照任务编号顺序，载入待执行任务，并标记下一个任务为待执行任务．Step2．判断是否是硬件任务．是，则跳转到Step3；否则跳转到Step5．Step3．判断是否有资源空间满足任务配置．是，则跳转至Step6；否则跳转至Step4．Step4．将当前任务与待执行任务交换，并重新标记为待执行任务．Step5．判断是否满足系统约束条件．是，则跳转至Step6；否则跳转至Step4．Step6．配置执行当前任务，更新资源空间．Step7．判断是否是最后一个任务．是，则调转到Step8；否则跳转到Step1．Step8．输出调度任务编码．

经预生成策略,算法可以产生至少一个满足系统约束的解,该初始解引导粒子群体进化的方向.预生成策略可以产生至少一个初始解,能够避免粒子群算法不能产生满足系统条件的解的问题,同时提高算法收敛的速度.

4 实验及分析

4.1 实验建立

本文选取随机测试用例和实际应用数据集评估算法性能.随机测试用例的任务图由TGFF[9]随机生成,参考文献中设计的综合应用数据集[10],生成规模分别为20、50、80个任务的集合;实际应用数据集采用不同任务个数的LU分解[11]和Gauss-Jordan消元[12]作为待调度的应用算法任务集合.对比算法选取自适应蚁群算法(AACO)[7]、混合遗传算法(HPSO-GA)[13]和线性规划方法(MILP)[14],在不同任务规模下对算法求解质量、可靠性和运行时间进行比较.其中,在实验中采用MILP方法作为评价其他算法的基准.实验仿真在MATLAB中进行,操作系统为Windows7,4GB内存、2.5GHz Intel Xeon.

实验面向的可重构器件按照Xilinx Virtex XCV1000 规模定义,采用96*64 个RCU,分成四块RCA[15].异构架构的可重构系统在进行任务时域调度前需要对任务图进行软硬件划分,该划分操作以及随机生成的任务执行时间、配置时间和任务占用硬件面积资源等属性参数参考文献[7，13，16].

4.2 实验分析

4.2.1 求解质量

给定系统资源限制时,任务规模对算法的求解质量影响较大.实验采用不同任务规模的随机任务、LU分解和Gauss-Jordan消元数据作为实验数据集,比较几种不同算法的求解质量.在任务调度中,调度方案的适应值越小,求解质量越优秀.不同数据集中的任务执行时间和任务配置时间以各自数据集的任务周期大小为基准,因此不同的数据集产生的调度方案时间相互没有影响,本实验关注同一数据集下不同算法的性能.

图7-图9是不同算法使用三类数据集产生的调度方案用时的条形图.MILP算法是规划类的方法,可以求出精确的全局最优解.本文算法与AACO和HPSO-GA算法属于启发式方法,启发式方法在解空间中搜索收敛,具有较快的执行时间,但是只能求出近似最优解,解的质量低于MILP算法.表3是调度方案用时的具体数据,由实验数据可知,本文算法的求解质量同MILP算法的结果相近,即近似最优解收敛程度较高,求解质量较高.同属于启发类的三种算法相比较,本文算法的求解质量优于AACO算法和HPSO-GA算法,求解质量平均分别提高13.2%和32.3%.

图7 随机任务的调度方案用时Fig.7 Quality of random tasks scheduling solutions

图8 Gauss-Jordan消元任务调度方案用时Fig.8 Quality of gauss-jordan elimination scheduling solutions

图9 LU分解任务图的调度方案用时Fig.9 Quality of LU-decomposition scheduling solutions

表3 调度方案用时(单位:Δt)
Table 3 Scheduling solutions of algorithms(Δt)

随机任务8205080MILP8112240PPSO8132341AACO9152745HPSO⁃GA10183050LU分解14202735MILP17222535PPSO17242636AACO19242839HPSO⁃GA21273445Gauss⁃Jordan消元15212836MILP6142126PPSO6142126AACO8142530HPSO⁃GA10173033

4.2.2 算法可靠性

启发式方法能求出近似最优解,其结果具有一定随机性.如果算法产生的结果不稳定,调度结果甚至可能出现未能满足系统约束的情况.当解的变化范围趋于稳定时,可认为该算法是可靠的.为验证算法可靠性,对于随机任务个数为80的数据集,进行百次实验并记录算法的调度结果,统计算法产生满足系统约束的调度方案的次数,如图10所示.MILP可以得出全局最优解,其可靠性达100%,PPSO算法由于使用了预处理策略,也具有较高的稳定性和可靠性.AACO算法和HPSO-GA算法由于缺少预处理策略,在收敛过程中依赖初始化的程度较高,因此可靠性低于本文算法.

图10 算法可靠性Fig.10 Reliability of algorithms

4.2.3 算法运行时间

由以上实验可以看出,规划类方法MILP算法具有较好的求解质量和可靠性.本文算法的调度结果接近于MILP算法的实验结果,并优于AACO算法和HPSO-GA算法的实验结果.对比算法的执行时间,结果如表4所示.由表4可以看出,本文算法和AACO算法、HPSO-GA算法均具有较快的执行时间.尽管MILP算法在求解质量上具有优势,但其执行时间相比于三种启发式方法差距一个甚至数个数量级.其中,本文算法兼具高求解质量和可靠性,并且具有较快的执行时间,在时间和性能评价标准中取得了较好的综合效果.

表4 算法执行时间(单位:秒)
Table 4 Execution time of algorithms(s)

随机任务8205080MILP7．6>10>10>10PPSO0．730．891．372．00AACO0．730．891．31．82HPSO⁃GA0．861．051．622．31LU分解14202735MILP>10>10>10>10PPSO0．750．840．921．03AACO0．750．810．890．99HPSO⁃GA0．820．981．121．27Gauss⁃Jordan消元15212836MILP>10>10>10>10PPSO0．750．90．890．98AACO0．740．90．80．96HPSO⁃GA0．821．110．981．2

5 结 论

本文面向异构动态部分可重构系统,对带有配置预取的可重构系统任务调度问题进行研究,提出了带有预处理机制的离散粒子群优化算法解决任务调度问题.针对可重构系统的任务调度问题模型,设计适用于该模型的任务编解码策略,并提出预生成初始解的策略,提高算法的可靠性并降低执行时间.实验结果表明,对比MILP算法、AACO算法和HPSO-GA算法,本文算法执行时间短,可有效提高调度方案质量,并且具有较高的可靠性.本文尚有不足之处,在调度过程中以任务配置执行的时间作为调度策略优劣的评价标准,忽略了任务之间的线长和通信时间,即没有考虑任务配置的布局策略.在今后工作中,有待对可重构系统任务布局策略做进一步研究.

[1] Pan Z,Wells B E.Hardware supported task scheduling on dynamically reconfigurable SoC architectures[J].Very Large Scale Integration Systems IEEE Transactions on,2008,16(11):1465-1474.

[2] Ferrandi F,Lanzi P L,Pilato C,et al.Ant colony optimization for mapping,scheduling and placing in reconfigurable systems[C].Adaptive Hardware and Systems,IEEE,2013:47-54.

[3] Kumar N,Vidyarthi D P.A novel hybrid PSO-GA meta-heuristic for scheduling of DAG with communication on multiprocessor systems[J].Engineering with Computers,2016,32(1):35-47.

[4] Al-Wattar A,Areibi S,Grewal G.An efficient evolutionary task scheduling/binding framework for reconfigurable systems[J].International Journal of Reconfigurable Computing,2016,2016(2):1-24.

[5] Li Z,Hauck S.Configuration prefetching techniques for partial reconfigurable coprocessor with relocation and defragmentation[C].Acm/sigda Tenth International Symposium on Field-Programmable Gate Arrays,DBLP,2002:187-195.

[6] Liang Liang,Zhou Xue-gong,Wang Ying,et al.Pre-configuration based hybrid tasks scheduling in reconfigurable systems[J].Journal of Computer-Aided Design & Computer Graphics,2007,19(5):635-641.

[7] Mollajafari M,Shahhoseini H S.An efficient ACO-based algorithm for scheduling tasks onto dynamically reconfigurable hardware using TSP-likened construction graph[J].Applied Intelligence,2016,45(3):695-712.

[8] Sun Kang.Research on reconfigurable computing technologies[D].Hangzhou:Zhejiang University College of Computer Science and Technology,2007.

[9] ]Dick R P,Rhodes D L,Wolf W.TGFF task graphs for free[C].Hardware/Software Codesign,(CODES/CASHE ′98) Proceedings of the Sixth International Workshop on.IEEE Xplore,1998:97-101.

[10] Filho J G,Strum M,Chau W J.Using genetic algorithms for hardware core placement and mapping in NoC-based reconfigurable systems[J].International Journal of Reconfigurable Computing,2015，2015:1-13.

[11] Jin S,Schiavone G,Turgut D.A performance study of multiprocessor task scheduling algorithms[J].The Journal of Supercomputing,2008,43(1):77-97.

[12] Gerasoulis A,Yang T.Performance bounds for column-block partitioning of parallel Gaussian elimination and Gauss-Jordan methods[J].Applied Numerical Mathematics,1994,16(1-2):283-297.

[13] Bonyadi M R,Moghaddam M E.A bipartite genetic algorithm for multi-processor task scheduling[J].International Journal of Parallel Programming,2009,37(5):462-487.

[14] Deiana E A,Rabozzi M,Cattaneo R,et al.A multiobjective reconfiguration-aware scheduler for fpga-based heterogeneous architectures[C].ReConFigurable Computing and FPGAs (ReConFig),2015 International Conference on.IEEE,2015:1-6.

[15] Yang Zhi-hua,Wu Wei-guo,Wang Tao,et al.A double-arbiter time-sliced tasks scheduling algorithm for reconfigurable system[J].Chinese Journal of Computers,2013,36(9):1850-1867.

[16] Qi X,Zhang X,Yuan K.RLDRPSO:an efficient heuristic algorithm for task partitioning[M].Advanced Computer Architecture,Springer Singapore,2016.

附中文参考文献：

[6] 梁 樑,周学功,王 颖,等.采用预配置策略的可重构混合任务调度算法[J].计算机辅助设计与图形学学报,2007,19(5):635-641.

[8] 孙 康.可重构计算相关技术研究[D].杭州:浙江大学,2007.

[15] 杨志华,伍卫国,王 涛,等.一种基于双仲裁时间片策略的可重构硬件任务调度算法[J].计算机学报,2013,36(9):1850-1867.