一种嵌入式异构多处理器系统的任务调度方法

摘要

本发明涉及一种嵌入式异构多处理器系统的任务调度方法。现有的算法需要花费大量的时间用于寻优，解决实际问题能力欠缺。本发明方法首先动态调整粒子速度V，得到一个速度的最优值；然后根据粒子速度的最优值调整惯性权重w；最后模拟任务调度方法。本发明针对具有复杂功能的嵌入式多处理器系的全局搜索能力和局部搜索能力的平衡性，粒子群优化算法在迭代后期搜寻能力下降的问题，通过调整调整飞行时间和惯性权重，提出了优化其平衡性提升其迭代后期搜寻能力的任务调度方法。

主权项

一种嵌入式异构多处理器系统的任务调度方法，其特征在于该方法的具体步骤是：步骤(1).动态调整粒子速度V调整粒子的飞行速度，在进化初期，粒子距离最优位置较远，粒子的飞行速度应快一些，这样有利于尽快的移向最优位置；当粒子距离最优位置较近时，粒子的飞行速度应慢一些，这样可以避免因飞行速度过快而导致的粒子“飞过”最优位置从而产生的来回运动现象；粒子飞行速度的计算方程式如下所示： X ij ( t + 1 ) = X ij ( t ) + V ij ( t + 1 ) × ( 1 + k × sin [ ( iter I max + 1 2 ) × π ] ) - - - ( 1 ) Xij(t+1)表示在时间点t+1的位移，Vij(t+1)表示在时间点t+1的速度，iter表示粒子当前的进化代数；Imax表示粒子的最大进化代数；K为比例系数，是常量；通过上述方程式对影响粒子飞行速度的因子进行动态调整，得到一个速度的最优值；步骤(2).调整惯性权重ww仍然随迭代次数线性递减，当迭代次数到达某个阈值时，这时w的值为wmin；然后w随迭代次数线性递增，这样w随迭代次数变化而变化，有助于算法摆脱局部极值，增强粒子群优化算法的全局搜索能力，找出最优解；由此提出惯性权重的调整策略；惯性权重的粒子群优化算法的惯性权重计算公式如下： w = w max - w max - w min iter T × iter iter ≤ iter T - - - ( 2 ) w = w min + iter - iter T iter max - iter T × w max iter ≥ iter T - - - ( 3 ) iter为迭代次数；itermax为设置的总的迭代次数；iterT为迭代次数的阈值；wmax是惯性权重的最大值；wmin是惯性权重最小值；步骤(3).模拟任务调度方法，具体步骤是：步骤a.初始化一群粒子，确定群体规模m，给定算法的最大、最小权重因子值，根据调度所需时间设定算法总的迭代次数itermax和迭代次数的阈值iterT；步骤b.根据所定义的适应度函数 S ij = ( T i _ execution _ time ) j Σ j = 1 m ( T i _ execution _ time ) j ∈ [ 0 , 1 ] 来计算每个微粒的适应值；步骤c.比较粒子的适应值和自身最优值pbest，如果当前粒子的适应值比pbest更优则置pbest为当前粒子的适应值；比较粒子适应值与种群最优值gbest；如果当前粒子的适应值比种群最优值gbest更优，则将种群最优值gbest修改为当前粒子的适应值；步骤d.判断是否达到了阈值迭代，若没有，则w值由公式(2)计算得出，若有，w值则由公式(3)计算得出；步骤e.根据以下式子对粒子速度进行更新；vij(t+1)＝w×vij(t)+c1r1(pbestij‑Xij(t))+c2r2(gbestj‑Xij(t))Xij(t+1)＝Xij(t)+vij(t+1)pbest为自身最优值，gbest种群最优值，c1和c2表示学习因子，r1和r2是0到1之间的随机数；步骤f.根据调整粒子飞行速度来更新粒子的位置；计算方程式如下：vij(t+1)＝w×vij(t)+c1r1(pbestij‑Xij(t))+c2r2(lbestj‑Xij(t))Xij(t+1)＝Xij(t)+vij(t+1)pbest为自身最优值，lbest为局部极值，c1和c2表示学习因子，r1和r2是0到1之间的随机数；步骤g.判断是否达到最终迭代次数，如果没有达到，执行步骤c；如果达到了，则从最后一代中获得个体最佳值。