基于粒子群优化算法的异构多处理器任务调度

李静梅，张 博

(哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001)

0 引言

多处理器系统由多个具有不同计算性能的处理器构成。如何将不同的任务分配到不同计算能力的处理器上进行处理便成为能否充分发挥多处理器性能的首要问题，这也是任务调度策略的研究成为多处理器技术研究热点问题的原因。但是，目前比较成熟的任务调度算法研究大多基于同构环境［1-2］，任务在同构多处理器中每个处理器上的执行时间相同，在任务调度时只需要将任务调度到上一任务完成时间最早的处理器上即可，而异构多处理器上各处理器的处理能力各不相同，在分配任务时还要考虑任务在不同处理器上的执行效率和处理器整体的执行时间。因此，异构多处理器上的任务调度问题相对更加复杂，采用同构多处理器任务调度算法不能充分发挥每一个处理器的性能和整体的并行性。

任务调度已被证明是NP完全问题［3］，不能在多项式时间复杂度内找到最优解。为求解此类NP完全问题，一些启发式算法如遗传算法 (genetic algorithm，GA)等，开始被应用到任务调度研究［4-7］。

基于上述背景，本文提出了一种基于粒子群优化 (particle swarm optimization，PSO)的任务调度算法——PSOASA算法，并在matlab仿真平台上与异构多处理器任务调度研究较多的遗传算法进行了性能比较测试，证明其收敛速度和求解精度均优于现有算法。

1 任务调度问题描述

为了方便描述问题，定义多处理器系统包含m个不同的处理器，一个应用程序被划分成n个子任务并且子任务之间相互独立，定义 T={T1，T2，…，Tn} (i=1，2，3，…，n)为n个独立任务序列;P={P1，P2，…，Pm}(j=1，2，3，…，m)为m个处理器序列。当n m时，即待执行任务数小于处理器的数目，可以根据先到先服务规则分配任务到指定处理器上执行。如果n＞m，则可以通过一些调度方案分配任务到相应处理器执行。本文仅考虑后一种情况。

任务i的计算量为Ti，任务i在处理器j上的执行时间cptij已知，s代表一个调度方案，SL是任务序列T在处理器集合P上执行的完成时间，SL(s)表示任意一个调度方案s下全部任务的完成时间，则任务调度问题就是求得一个最优调度方案f，使SL(f)最小。任务调度问题数学描述为

2 粒子群优化算法

PSO算法是一种基于群体智能理论的全局优化方法，种群 (Swarm)中粒子通过相互间的合作与竞争进行优化搜索，种群是粒子的集合，种群大小或规模是集合中粒子的数目。种群中的粒子都有位置和速度两个属性，粒子的维数同问题解空间的维数相对应。PSO算法从随机解开始进行迭代寻找最优解，通过适应度来评价解的质量，粒子追随当前搜索到的最优值寻找全局最优。PSO算法实现容易、求解精度高、收敛速度快，在解决TSP、流水车间调度和路径规划等问题中展示了其良好的优越性［8-9］。

假设PSO算法的搜索空间是d维，使用式 (2)表示第i个粒子的位置和速度矢量

PSO算法运行时初始化为一群随机粒子 (随机解)，每个粒子在搜索空间内不断更新速度和位置，然后进行迭代直到找到最优解或达到最大迭代次数。每一次迭代过程中，粒子通过两个极值的信息不断更新自己的位置和速度。第一个是个体最优解，是粒子上一次迭代本身所找到的最优解，第i个粒子的个体最优解记为pbesti=［pbesti1，pbesti2，…，pbestid］，另一个是整个种群找目前找到的最优解，称为全局最优解，记为gbest= ［gbest1，gbest2，…，gbestd］。另外，粒子的所有邻居中的最优解是局部最优解。

在找到个体最优解和全局最优解时，粒子根据状态更新公式更新自己的速度和位置，PSO算法速度和位置更新公式［10］如下

式中:n——种群大小，t——迭代次数，c1和 c2——加速常数，一般取值为2;r1和 r2——0到1之间的随机数;ω——惯性权重，用于平衡收敛的全局性和收敛速度，计算方法见式 (4)

式中:N——最大迭代次数，ωmax和 ωmin——ω的最大值和最小值，通常取值为0.9和0.4，t——迭代次数。

PSO算法实际运行过程中，由于粒子更新过程中总会考虑周围粒子的信息，随着迭代次数的增加就会产生“聚堆”现象，粒子会在问题过程中逐渐丧失多样性，致使过早的收敛，容易陷入局部最优。为了解决此问题，PSO算法多使用一些元启发式算法进行局部搜索，以加强PSO算法的收敛性能。

3 基于粒子群优化的调度算法

3.1 粒子编码方案

异构多处理器环境中，任务调度算法需要解决的是在提高资源利用率和系统效率的同时，如何最大限度地减少完成时间。PSO算法是一种连续算法，算法的更新公式和过程是面向连续空间并为其设计的，而调度问题属于离散问题。本文根据异构多处理器调度问题特点，重新构建粒子表达方式，对粒子的位置和速度进行编码，将PSO算法映射到离散空间，使其适用于解决任务调度问题。

PSO算法中每一个粒子都代表一个任务调度问题的潜在解。粒子位置矢量定义为一个n(m矩阵X，每一列代表一个任务分配情况，每一行代表一个处理器执行情况。式(5)为粒子位置编码方案，约束条件为式 (6)

根据约束条件 (6):位置矩阵X的元素xi，j取值为0或1;每一行可以有多个1出现;每一列任意一个元素都可以为1;每一列只允许仅有一个元素值为1。即:

(1)其中xi，j=1表示任务Ti分配到处理器Pj上执行，否则 xi，j=0;

(2)每一个处理器都可以执行多个任务;

(3)任务可以分配到任意一个处理器上执行且任务必须被分配到一个处理器上执行;

(4)一个任务不允许同时分配到多个处理器上，即任务执行不能被中断。

速度定义为粒子达到目标状态所需要对其当前位置执行的基本交换次序。速度V为n(n矩阵，如式 (7)所示，速度矩阵V中的元素vij只取值为0或1

此时，粒子的位置和速度状态不再是同维连续失量。粒子的速度和位置不能再参照式 (3)进行更新，为了利用此编码方式，本文重新定义粒子速度和状态更新公式中的加减法、乘法运算规则:

(1)定义PSO算法中的加减法操作为交换操作，即vij=1表示交换位置矩阵X里第i列和第j列值为1的元素的位置，即相互任务i和任务j所分配的处理器，根据速度约束条件 (8)，速度矩阵以对角线为对称轴，不能为对称矩阵，避免了一次更新过程中无效的重复交换现象。

(2)定义速度与随机数的数乘为依随机数对应概率值决定是否按照速度矩阵进行交换操作。

重新定义的运算规则使用符号“⊕”表示，则重新定义后的粒子状态更新公式为式 (9)，各变量含义同式 (3)

式 (10)所示的位置和速度状态进行位置更新的结果见式(11)

由此可见，粒子的这种编码方案和约束简单明了，符合异构多处理器任务调度规则，能够表示出所有可能的任务调度方案，并且将粒子搜索空间和任务调度方案一一映射起来，同时避免了冗余搜索。

3.2 适应度

粒子位置好坏的评价标准根据粒子的适应度进行评价。粒子适应度通过适应度函数计算得到，本文使用粒子的makespan作为其适应度评价标准，粒子的makespan是指粒子中全部任务的最晚完成的时间，makespan越小粒子位置越接近最优粒子，其所代表的潜在调度方案越好。第y个粒子适应度值计算方法如下

其中，j为处理器编号makespan(pj)表示第j个处理器上所有任务的完成时间。makespan(pj)通过式 (13)计算得到

由式 (12)、(13)得到适应度函数为

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

针对PSO算法容易陷入局部最优解的问题，本文融入了模拟退火 (simulated annealing，SA)算法进行局部搜索，以保证PSO算法的收敛性能，提出PSOASA算法。

PSOASA算法在PSO算法每次迭代后使用SA算法重复局部迭代以选择更好的解，同时也允许算法通过一定的概率接受比较差的解使PSO算法避免局部最优。当初始温度、温度下降速度、终止温度达到一定条件时，SA算法已经被证明一定收敛于全局最优［11］。

初温T0的设置对PSOASA算法的性能具有一定的影响，初温公式如式 (15)，f(gbestini)表示初始种群的全局最优粒子的适应度值

退温函数采用线性退温，即

λ为退温速率，其中Tt为第 t次迭代时 SA算法的温度。

SA算法随机选择gbest的一个邻居gbest＇，为避免陷入局部最优，SA算法以一定的概率接受差的解，用粒子中选择出来的gbest＇来以一定的概率取代全局最优解gbest，让算法跳出局部最优。因此通过使用PSO算法的目标函数(14)计算 Δ =f(gbest＇)－f(gbest)判 断 gbest＇是 否 取代gbest，如果Δ≤0，则从 gbest移动到 gbest＇，否则以概率 η移动到gbest＇，概率η计算方法为

PSOASA算法借助SA的突跳能力对部分较好的个体进行优化，利用PSO算法的收敛速度快、SA算法依概率突跳能力以及收敛到全局最优解等特点。通过这两种算法的协同搜索，增加了种群多样性，有效地克服PSO算法的“早熟”现象，既提高了收敛速度，又保证了全局最优解的质量。

PSOASA算法完整流程可以概括如下:

步骤1 初始化;设置有关PSOASA算法参数:随机初始化每个粒子的位置矢量和速度矢量;设定粒子群的规模;设定SA算法的初始温度和退温系数λ;结束条件温度;

步骤2 使用式 (14)计算粒子的适应值，初始化粒子的个体最优解和种群的全局最优解，设置粒子当前位置为pbest，种群最佳位置为全局最优值gbest;

步骤3 运用式 (9)更新粒子的位置和速度;

步骤4 使用适应度函数 (14)计算出每一个粒子的适应度值;

步骤5 找出个体最优粒子和全局最优粒子，并将求得的适应度分别与pBest和gBest的适应度比较，若较好，则更新pBest或gBest;

步骤6 判断gbest是否满足SA算法抽样准则，满足则接受gbest，否则以概率η执行下一步，否则由gbest产生新的状态，按抽样准则确定新状态并执行退温操作并在次判断;

步骤7 判断是否达到SA算法终止条件，是则执行步骤8，否则执行式 (16)，更新温度参数，并转到步骤6;

步骤8 判断是否满足结束条件 (达到最大迭代次数)，如果满足，执行步骤10;否则，继续下一步;

步骤9 更新迭代变量:t=t+1;

步骤10 输出gbest，算法运行结束。

4 仿真实验

本文在matlab仿真环境中，对PSOASA算法和目前多处理器任务调度研究较多的GA算法进行性能［12］对比验证。基准测试用例采用Watson等［13］提出基准测试套件进行调度算法的性能测试。表1给出了PSOASA和GA的实验参数设置。为了抵消数据随机性对测试结果的影响，更好的反应算法的性能，全部任务完成时间取10次测试中得到最优解的平均值。

本文实验中测试了100、200、300、400、500个任务在5个处理器上调度的结果。图1为使用PSOASA算法和GA算法在100个任务和5个处理器条件下进行任务调度的完成时间-迭代次数曲线。

图1可以看出，相对于GA算法，PSOASA算法的找到最优值的迭代次数更少，解的质量更高，即适应度更低，全部任务执行完成的时间更少。这是因为遗传算法复杂的交叉和变异操作增加了算法的时间复杂度，算法后期容易错过最优解;PSOASA算法具有PSO算法的收敛速度快的特点，同时SA算法对质量较好解进行扰动，增加了种群多样性，提高算法的求解质量。

图2为不同任务数情况下，算法的平均执行时间变化曲线。通过图2可以看出，任务数较少时，PSOASA算法的执行时间稍优于GA算法，但随着任务数目的增加，二者差距越来越明显。在任务数较多时，PSOASA算法具有更短的执行时间，性能明显优于GA算法，这是因为GA算法在任务数较多时，交叉和变异操作的多样性会受到限制，效率低下;而PSO算法受问题维数的影响更小，并且具有更好的并行搜索性能。因此，PSOASA算法更适合于大规模并行任务调度。

5 结束语

为提升异构多处理器系统中的任务调度效率，本文提出了基于PSO算法的PSOASA算法求得全部任务最短完成时间。PSOASA算法充分利用了PSO算法收敛速度快和并行性的特点，通过建立粒子编码方式和重新定义粒子更新公式，使连续的PSO算法适用于异构多处理器任务调度，并融入了SA算法克服了PSO算法容易陷入局部最优的缺点。通过与多处理器任务调度研究中较多采用的遗传算法进行性能测试比较，本文的算法能在更少的迭代次数内搜索到最优解，并且最优解的质量更高，算法的执行速度也优于遗传算法，很好的解决了异构多处理器系统中的任务调度问题，在大规模运算环境中有很好的研究价值和应用前景。

［1］ZHAO Peng，YAN Ming，LI Sikun.Performance optimization of application algorithms for heterogeneous multi-processor system-onchips［J］.Journal of Software，2011，22(7):1475-1487(in Chinese).［赵鹏;严明;李思昆.异构多处理器SoC的应用算法性能优化方法 ［J］.软件学报，2011，22(7):1475-1487.］

［2］Fatih Tasgetirena M，LIANG Yunchia，Sevkli Mehmet.Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem ［J］.International Journal of Production Research，2006，44(22):4737-4754.

［3］Thanushkodi K，Deeba K.On performance analysis of hybrid algorithm(improved PSO with simulated annealing)with GA，PSO for multiprocessor job scheduling［J］.WSEAS Transactions on Computers，2011，10(9):287-300.

［4］WENYun，XUHua，YANGJiadong.A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous processor networks ［J］.Journal of Parallel and Distributed Computing，2011，71(11):1518-1531.

［5］Ebrahimi Moghaddam，Mohsen Bonyadi，Mohammad Reza.An immune-based genetic algorithm with reduced search space co-ding for multiprocessor task scheduling problem ［J］.International Journal of Parallel Programming，2011，40(2):225-257.

［6］YAO Lili，SHI Haibo，LIU Chang.Solving multi-objective hybrid flow-shop scheduling problem based on genetic algorithm ［J］.Application Research of Computers，2011，28(9):3264-3271(in Chinese).［姚丽丽，史海波，刘昶.基于遗传算法的混合流水线车间调度多目标求解 ［J］.计算机应用研究，2011，28(9):3264-3271.］

［7］Abdel-Kader，Rehab F.An improved discrete PSOwith GA operators for efficient QoS-multicast routing［J］.International Journal of Hybrid Information Technology，2011，4(2):23-38.

［8］SONG Jiguang，QIN Yong，SHI Jianfang.Study of PSO algorithm and its application for routing optimization［J］.Computer Engineering and Design，2011，31(9):1905-1919(in Chinese).［宋继光，秦勇，史健芳.粒子群算法及其在路由优化中的研究［J］.计算机工程与设计，2011，31(9):1905-1919.］

［9］LI Shuhong，ZHANG Qiaorong.Application of binary particle swarm optimization algorithm in path planning［J］.Computer Engineering and Design，2009，30(21):4953-5009(in Chinese).［李淑红，张巧荣.二进制粒子群算法在路径规划中的应用［J］.计算机工程与设计，2009，30(21):4953-5009.］

［10］YANG Fan，HU Chunping，YAN Xuefeng.Particle swarm optimization algorithm of self-adaptive parameter based on ant system and its application［J］.Control Theory ＆ Applications，2010，27(11):1479-1488.

［11］LI Pengchao.Grid resource prediction based on support vector regression and simulated annealing algorithms ［D］.Jilin:Master＇s graduation thesis of University of Jilin，2010(in Chinese).［李鹏超.基于模拟退火算法和支持向量回归的网格资源预测［D］.吉林:吉林大学硕士学位论文，2010.］

［12］LI Zhiqiang.Optimization for the parallel test task scheduling based on GA ［C］//2nd International Conference on Information Science and Engineering.Hangzhou，China:2011:5223-5226.

［13］Jean-Paul Watson，Christopher Beck J.A hybrid constraint programming/local search approach to the job-shop scheduling problem ［J］.Lecture Notes in Computer Science，2008，50(15):263-277.