混合粒子群算法的异构多核处理器间任务调度

田 辉

(桂林理工大学 机械与控制工程学院,桂林 541006)

混合粒子群算法的异构多核处理器间任务调度

田 辉

(桂林理工大学 机械与控制工程学院,桂林 541006)

针对异构多核处理器间的任务调度问题，为了更好地发挥异构多核处理器间的平台优势，提出一种基于将有关联的且不在同一处理器上的任务进行复制的思想，从而使每个异构多核的处理器能独立执行任务，来减少不同处理器之间的通信开销，并且通过混合粒子群算法(HPSO)来调度异构多核处理器中的任务，避免由于当任意一个异构多核处理器由于任务分配过多而导致计算机不能及时且准确地得出结果。最后实验证明，对比传统的启发式分配方案和常见的遗传算法(GA)，基于任务复制思想分配方案和混合粒子群算法(HPSO)具有更好的求解能力，并且可以提供执行时间更少的调度分配方案，具有较好的应用价值。

异构多核处理器；任务调度；混合粒子群算法

引 言

目前异构多核处理器是处理器发展的前沿方向，而且一个计算机里也同时包含着多个异构多核处理器。在多个异构多核处理器平台下，如何将不同的任务分配到不同的合理处理器上以获得最小的运行时间或者最大的输出权重，是多核处理器能否发挥性能优势的首要问题。目前任务调度问题已经被证明为NP-hard问题，无法在多项式内求得最优解。所以异构多核处理器环境下的任务调度问题成为了异构多核技术方面的研究热点。目前在异构多核处理器间任务调度的研究方向大多采用了启发式算法、布谷鸟算法等。杨辉华、张晓凤提出了基于布谷鸟搜索的多处理器任务调度算法[5]；刘朝华、张英杰、吴建辉提出了一种求解TSP问题的改进克隆选择算法[9]，用来求解处理器中的多任务优化组合问题；徐成等人结合遗传算法的交叉、变异操作改进了标准蚁群算法[4]，并应用于异构多核平台下的周期多帧任务模型的调度问题。

而上述提出的算法在处理器面对被分配的任务数量过多时，处理器不能快速有效地求出准确的结果。因此本文提出了在任务分配环节，通过将不在同一处理器的任务，但与任务之间存在着联系，通过任务复制的思想将任务复制到有关联的处理器内进行处理，从而减少处理器间的任务通信开销，并且每一个相互独立的处理器采用混合粒子群算法来对各自的任务进行调用，避免当处理器任务量过大时，导致不能迅速、准确地求出相应的结果。为了验证本文提出的混合粒子群算法(HPSO)在异构多核处理器间的任务调度算法，并在MATLAB仿真平台进行实验不失一般性，与比较经典的遗传算法(GA)进行了对比分析。

1 任务调度问题描述

异构多核处理器系统任务调度的研究主要集中在具有约束关系的任务模型，一般使用 DAG 表达任务的约束关系，不失一般性。假设一个具有3个异构多核处理器和14个有约束任务关系的系统模型，DAG图的节点表示任务，边反映了任务间的数据依赖性，如图1所示。

图1 具有14个任务的DAG例图

以图1为例，节点框内的数据表示任务编号和任务执行所需时间，有向边上的数据表示其一个任务到另一个任务间的通信开销。为了方便理解，分别给出了各个任务在相应处理器上的处理时间。T0、T1、T2、T3、T4、T5、T6属于进程P0，被分配给处理器R0；T7、T8、T9、T10属于进程P1，被分配给处理器R1；T11、T12、T13属于进程P2，被分配给处理器R3。3个处理器的有些任务存在相互联系，本文在研究异构多核处理器间的任务调度问题时认为同一个异构多核处理器之间的内核是紧耦合的，它们之间通过共享Cache或高速通信通道的内连接紧密联系在一起，而不同处理器之间内核的连接并不紧密，它们之间的通信时间要远远大于紧耦合内核之间的通信开销，所以设定T0到T1间的10、0分别表示内核间通信次数为10，通信开销为0。T11和T8之间的4、11分别表示通信次数为4，内核间通信开销为11。

由图1可知，在不同处理器中的任务之间,必然存在相互联系，为了减少不同处理节点间的任务之间通信所带来的开销，本文采用任务复制思想原则，将不在同一处理器上的任务复制到另一个处理器上执行，其实质就是增加处理器的计算量来消除不同处理器间的通信开销。例如图2所示的一个任务DAG图，存在不同处理器间的任务通信，对于这种结构的DAG图采用通常的任务调度算法进行执行，其节点之间的通信开销不可小视，因此采用任务复制思想来消除任务节点间的通信开销。

图2 存在不同任务之间通信的DAG图

经过任务复制后的DAG图如图3所示。

图3 经过任务复制后的DAG图

如图3所示，处理器R0的T4任务与处理器R1的T3任务之间有联系，但是任务复制必须寻找最短的路径进行复制，而且必须从任务的入口节点到起始节点全部复制到另一个处理器上，而在处理器R0上，与T4处理器节点有关的起始节点有两个，分别为T0和T1,而进行复制有3条选择，分别为：T0→T2→T4,T1→T2→T4,T1→T3→T4，而这三条路径的任务执行开销分别为：5+4+1=10，2+4+1=7，2+1+1=4，所以选择复制的路径为T1→T3→T4。

因此将上述任务分配的方案总结为：首先，为了减少任务之间所需的通信时间，将频繁通信的任务分配到同一处理节点上；其次，所有属于同一个进程的任务必须分配到同一个节点上，这是同一个进程共享同一个存储单元，并且各个处理节点都是相互独立的；最后要保证处理节点和负载是相互平衡的。其任务复制的思想就是在任务被分配完之后，对于两个任务之间存在通信但不在同一处理器上，将从任务的入口节点到起始节点的最短路径复制到另一个处理器上。

2 任务的调度

目前任务调度问题已经被证明为NP-hard问题，经过上诉的任务分配方案，将任务合理地分配到相应异构多核处理器中，本文提出的调度算法是在上述任务分配完成后，针对每一个相互独立的异构多核处理器中的任务调度。由于现在处理器处理的任务有时在上百个以上，而目前王嘉平提出的多核系统中实时任务调度算法的研究，杨辉华、张晓凤[5]提出了基于布谷鸟搜索的多处理器任务调度算法，刘朝华、张英杰、吴建辉[9]提出了一种求解TSP问题的改进克隆选择算法，用来求解处理器中的多任务优化组合问题，当处理器任务量过大时，运用他们提出的算法不能迅速而准确地求出处理结果。因此本文采用了任务间的旅行商组合优化方案，并提出通过混合粒子群算法来解决当处理器被分配的任务量过大时的问题。本文提出的混合粒子群算法借鉴了前人研究的成果并加以改进。以下算法的调度是针对独立的异构多核处理器中的任务调度，并且为了方便理解，本文认为每个独立的处理器被分配的任务为12个。

算法的实现过程如下：

(1) 任务个体的编码

图4 GA和HPSO在任务数N=14时优化过程对比图

编码采用整数编码的方法，每个数字表示一个被执行完的任务，如上述算法中本文假设执行的12个任务，每个任务的编码为[4,6,7,10,3,5,11,8,2,9,1,12],表示执行任务从任务4开始，经过4,6,7，.....最终返回任务4，从而完成全部任务的执行。

(2) 适应度值

任务适应度值为执行完全部任务时间的长短，表示为：

其中n为任务数量；Di,j表示执行i任务到j任务所需时间。

(3) 交叉操作

将全部任务中的随机个体分别和执行所需时间最长的任务和全部任务中所需执行时间最短的任务进行交叉来获得更新，交叉方法同样采用整数交叉法。首先选择两个交叉位置，其次把随机任务和执行所需最少任务进行交叉，假定选取的交叉任务为10和12，其交叉操作为：

个体[4,6,7,10,3,5,11,8,2,9,1,12]和极值 [4,2,8,10,3,5,11,7,6,9,1,12] 进行交叉操作过程得到的新个体为新任务，其新任务序列为:[4,6,8,10,3,5,11,8,2,9,1,12]，同时对与产生的任务中重复的编码进行调整，调整为[4,6,8,10,3,5,11,7,2,9,1,12]，然后采用保留优秀任务序列策略，只有当新执行路径比旧执行路径短时才选择更新。

(4) 变异操作

采用任务内部两两位置互换原则，首先随机确定两个任务位置，例如位置8和2进行互换，变异过程为：[4,6,7,10,3,5,11,8,2,9,1,12]→[4,6,7,10,3,5,11,2,8,9,1,12]，然后仍然保留优秀个体策略，只有当新执行路径比旧执行路径短才选择更新。

3 任务调度性能测试以及对比分析

3.1.1 任务调度算法在VisualStudio2010平台上的测试实验

模拟调度问题模型基础设置如下：考虑到任务的随机性和多样性，为了表示任务的不一样性和准确性，本文将任务用算法随机给得坐标来表示它的不一样性。同时此次测试实验分为三个部分，当任务数N=14、N=50、N=130时，混合粒子群算法利用Visual studio 2010中的可变处理器个数和自带OpenMP多线程并行计算来对多处理器上的调度结果。测试实验平台处理器个数设置为3，混合粒子群算法(HPSO)中的参数分别取为: 学习因子c1、c2分别取2，最大权重w取0.9，最小权重w取0.4；遗传算法(GA)中的参数分别取为：pc(交叉概率)取0.9;pm(变异概率)取0.05；GGAP(个体间的代沟)取0.9，为了使数据准确，本测试每组实验反复测试30次，最后取各个任务调度算法的最好处理结果。

① 当任务数取N=14时，种群数目为100，迭代数为200，测试结果如图4所示。

② 当任务数取N=50时，种群数目为100，迭代数为1000，测试结果如图5所示。

图5 GA和HPSO在任务数N=50时优化过程对比图

③ 当任务数取N=130时，种群数目为100，迭代数为3000，测试结果如图6所示。

图6 GA和HPSO在任务数N=130时优化过程对比图

3.1.2 实验总结

在使用混合粒子群算法进行任务调度时，当任务数N=14时，处理完任务所走的路程为608；当任务数N=50时，处理完这些任务所走的路程为1688；当任务数N=130时，处理完任务所走的路程为5 605。

在使用遗传算法进行任务调度时，当任务数N=14时，处理完任务所走的路程为最小为428，最大为561，其最后结果不稳定。当任务数N=50时，处理完这些任务所走的路程为1784。当任务数N=130时，处理完任务所走的路程为5 605。

当任务数N=14时，遗传算法所走的路程比混合粒子群算法少，但是遗传算法没有混合粒子群算法最后处理的结果稳定。

当任务数N=50时，遗传算法所走的路程比混合粒子群算法多。

当任务数N=130时，遗传算法所走的路程和混合粒子群算法所走的路程一样。

测试表明，遗传算法和混合粒子群算法都能在多处理器上并行计算，但是混合粒子群算法不论在多少个任务下执行时，都优于遗传算法而且稳定，但是当N=130时，遗传算法和混合粒子群算法表现的性能一样，而且稳定。

3.2 任务调度算法在Matlab上仿真实验

为了验证HPSO算法的优点，本文将遗传算法和混合粒子群算法在Matlab上进行了三次仿真实验。本文挑选在进行了多次试验后的两种算法的最好的结果仿真图进行对比，并采用国际上通用的 TSPLIB[1]库中的标准测试集burma14、st70、ch130分别进行三组实验，对任务N分别取14、50、130时的两个算法的比较，为了保证数据的准确性，每组实验分别进行30次，然后取平均值。采用本文提出的HPSO调度算法与本文对比的调度算法GA算法对任务进行调度，对调度的结果进行对比分析。

本实验中混合粒子群算法(HPSO)中的参数分别取为: 学习因子c1、c2分别取2，最大权重w取0.9，最小权重w取0.4；遗传算法(GA)中的参数分别取为：pc(交叉概率)取0.9;pm(变异概率)取0.05；GGAP(个体间的代沟)取0.9。

3.2.1 实验仿真

① 当线程数取N=14时，种群数目为100，迭代数为200，其任务的标准burma14位置坐标为以下坐标，如图7所示。

图7 当任务N=14时的任务分布图

其两种算法的仿真结果如表1所列。

表1 GA和HPSO算法在N=14时的数据结果

当任务N=14时,HPSO和GA算法的仿真对比图如图8所示。

图8 GA和HPSO在任务数N=14时优化过程对比图

② 当任务数取N=50时，种群数目为100，迭代数为1000，由于任务量过大就不列举位置坐标。

其根据任务坐标仿真结果如图9所示。

图9 当任务N=50时的任务分布图

其两种算法的处理结果如表2所列。

表2 GA和HPSO算法在N=50时的数据结果

当任务N=50时,HPSO和GA算法的仿真对比图如图10所示。

图10 GA和HPSO在任务数N=50时优化过程对比图

③ 当任务数取N=130时，种群数目为100，迭代数为3 000，其两种算法的处理结果如表3所列。

表3 GA和HPSO算法在N=130时的数据结果

N=130时的任务分布图如图11所示。

图11 当任务N=130时的任务分布图

当任务N=130时仿真对比图如图12所示。

图12 GA和HPSO在任务数N=130时优化过程对比图

3.2.2 实验总结

① 当任务N=14时，从图9可以看出GA算法在当迭代到100代的时候稳定了，而HPSO当迭代到40代的时候已经稳定了，同时从表1可以看出，当任务N=14时，其GA算法和HPSO算法在最优解方面分别为30.878和30.881，在最差解方面为31.208和30.881，在平均值方面分别为31.013和30.881，在调度的时间上为9.87和2.43。通过以上数据可以得出，当任务N=14时，无论在最优解还是最差解、调度的时间方面，HPSO算法都要比GA算法优越，而且HPSO算法也很稳定。

② 当任务N=50时，从图10可以看出GA算法在当迭代到730代的时候才稳定下来，而HPSO当迭代到600代的时候已经开始稳定了，同时从表2可以看出，当任务N=50时，其GA算法和HPSO算法在最优解方面分别为568.412和553.596，在最差解方面为644.112和604.837，在平均值方面分别为606.262和579.217，在调度的时间上为31.52和12.05。通过以上数据可以得出，当任务N=50时，无论在最优解还是最差解、调度的时间方面，HPSO算法都要比GA算法优越，而且HPSO算法也很稳定。

③ 当任务N=130时，从图13可以看出，GA算法在当迭代到3000代的时候也没有开始稳定下来，而HPSO当迭代到1700的时候已经开始稳定了，同时从表3可以看出，当任务N=50时，其GA算法在最优解和最差解方面不能求出准确值，而HPSO算法的最优解为6467.69、最差解位7000.198、平均值为6733.944，在调度的时间上为240.52。通过以上数据可以得出，当任务N=130时，GA算法已经不能调度并处理任务了，而HPSO算法可以求出准确值，所以当任务量大的时候，HPSO算法能够合理地对大任务量进行调度。

所以通过上述三组实验比较，可以得出HPSO算法无论在算法的时间复杂度、调度的成功率和任务执行的加速比率上都要比GA算法优越。

结 语

为优化异构多核处理器环境下任务调度性能，本文提出一种基于将有关联的且不在同一处理器上的任务进行复制思想，从而使每个异构多核的处理器能独立地执行任务，来减少不同处理器之间的通信开销，并且通过混合粒子群算法(HPSO)来调度异构多核处理器中的任务，避免由于当任意一个异构多核处理器由于任务分配过多而导致处理器不能及时且准确地处理出结果。

[1] Gupta S，Agarwal G，Kumar V.Task scheduling in multi-processor system using genetic algorithm[C]//Proc of the 2nd International Conference on Machine Learning and Computing,2012:267-271．

[2] 李静梅,张博.基于粒子群优化算法的异构多处理器任务调度[J].计算机工程与设计,2013,34(2) : 627-631.

[3] Kaur R,Singh G.Genetic algorithm solution for scheduling jobs inmultiprocessor environment[C]//Proc of Annual IEEE India Confe-rence,2012:968-973.

[4] 徐成,王培磊,杨志邦.基于改进蚁群算法的周期多帧任务分配[J].计算机应用研究,2012,29(9):3251-3254．

[5] 杨辉华,张晓凤.基于布谷鸟搜索的多处理器任务调度算法[J].计算机科学,2015(1).

[6] Ebrahimi J,Hosseinian S H,Gharehpetian G B.Unit commitment problem solution using shuffled frog leaping algorithm[J].IEEE Trans on Power Systems,2011,26(2):573-581．

[7] 徐雨明,朱宁波,欧阳艾嘉,等．异构系统中 DAG 任务调度的双螺旋结构遗传算法[J].计算机研究与发展,2014,51(6):1240-1252．

[8] Chen Minrong,Li Xia,Wang Na,et al．An improved shuffled frog-leaping algorithm for job-shop scheduling problem[C]//Proc of the 2nd International Conference on Innovations in Bio-inspired Compu-ting and Applications,2011:203-206．

[9] 刘朝华,张英杰,吴建辉.一种求解TSP问题的改进克隆选择算法[J].系统仿真学报,2010,22(7):1627-1631．

[10] 周辉仁,唐万生,牛犇.基于递阶遗传算法的多旅行商问题优化[J].计算机应用研究,2012,26(10):3754 -3757．

[11] 马永杰,云文霞.遗传算法研究进展[J].计算机应用研究,2012,29(4):1201-1206.

[12] 陈芳园,张东松,王志英.异构多核处理器体系架构设计研究[J].计算机工程与科学,2011(12):27-36.

[13] 彭晓明,郭浩然,庞建民.多核处理器-技术趋势和挑战[J].计算机科学,2012(S3):320-326.

[14] 余伶俐,蔡自兴.改进混合离散粒子群的多种优化策略算法[J].中南大学学报:自然科学版,2011,40(4):1047-1053.

Task Scheduling for Heterogeneous Multi-core Processors Based on HPSO

Tian Hui

(College of Information Science&Engineering,Guilin University of Technology,Guilin 541006,China)

In order to solve the problem of task scheduling among heterogeneous multi-core processors and better play to the advantage of heterogeneous multi-core processor platform,a replicating idea based on connected and not on the same processor task is proposed,so that each heterogeneous multi-core processor can independently perform the task to reduce the communication overhead among different processors.The hybrid particle swarm optimization algorithm (HPSO) is used to schedule tasks in heterogeneous multi-core processor,avoids the results can not be timely and accurately shown when an arbitrary heterogeneous multi-core processor has too many tasks.The experiment results show that compared with the traditional heuristic allocation scheme and the common genetic algorithm,the solution has better solving ability,and can provide the implementation scheme of less time scheduling and allocation,and has good application value.

multiprocessor;task scheduling;HPSO

TP301.6

A

士然

2017-01-03)