基于改进遗传算法的异构多核节能任务调度方法

摘要

一种基于改进遗传算法的异构多核节能任务调度方法，它由用来确定任务优先级的改进遗传算法以及基于缩放优先级的节能调度算法组成，其流程为：(1)进行种群信息初始化；(2)进入循环体通过遗传算法确定任务优先级；(3)根据任务DAG图和划分策略，确定任务在处理器上的调度顺序；(4)根据任务节省能量与延长时间之间的关系，在可行的任务调度基础上进行动态电压缩放；(5)计算当前群体适应度并排序；(6)采用改进的遗传算法对种群进行更新，确定新的任务优先级，如果满足终止条件则退出，否则继续迭代。

主权项

1.一种基于改进遗传算法的异构多核节能任务调度方法，其特征在于，由用来确定任务优先级的改进遗传算法以及基于缩放优先级的节能调度算法组成，其流程为：（1）进行种群信息初始化；（2）进入循环体通过改进遗传算法确定任务优先级；（3）根据任务DAG图和划分策略，确定任务在处理器上的调度顺序；（4）根据任务节省能量与延长时间之间的关系，在可行的任务调度基础上进行动态电压缩放；（5）计算当前群体适应度并排序；（6）采用改进的遗传算法对群体进行更新，确定新的任务优先级，如果满足终止条件则退出，否则继续迭代；所述步骤（1）中，将任务优先级转换为按一定顺序组织的染色体，其中染色体的编码采用一维位串形式，编码长度为任务图中任务节点数n，每个基因表示对应任务的调度优先级，取值范围为[0,n-1]，数值越低对应优先级越高，对于优先级相同的任务，则根据任务编号进行排序；所述步骤（6）的流程为：（6.1）对群体进行选择操作，从当前群体中选出个体，作为父辈进行交叉和变异操作；选择算子执行步骤如下：（6.1.1）根据遗传算法中群体数目参数计算需要选择的个体数目Nsel；（6.1.2）根据前面排序的排序结果，选择位于队列前部的Nsel/2个个体；（6.1.3）采用随机算法，在队列中其余个体中均匀产生Nsel/2个个体；（6.1.4）将上述（6.1.2）和（6.1.3）产生的共Nsel个个体作为选择结果进行交叉和变异，选择过程结束；（6.2）进行交叉操作：采用两点交叉算子；（6.3）变异操作：变异算子是对个体中某个基因在有效值范围内进行随机变换，也即随机改变某个任务的执行优先级；（6.4）群体更新，执行步骤如下：（6.4.1）计算新生成个体的调度能耗Echild；（6.4.2）比较新生成个体的调度能耗Echild和父辈的调度能耗Eparent，分两种情况考虑：如果新生成个体的调度能耗Echild小于父辈的调度能耗Eparent，则选择新产生的染色体；如果新生成个体的调度能耗Echild大于等于父辈的调度能耗Eparent，则以概率Preceive接受新的染色体，Preceive的计算方法下式：$\left\{\begin{array}{c}{P}_{\mathrm{receive}}=e^{-(E_{\mathrm{child}}-E_{\mathrm{parent}})/T}\\ T=\frac{1}{P}\underset{i=1}{\overset{P}{\Sigma }}{(E_i-\bar{E})}^2\end{array}\right.$其中，e为自然常数，Ei为个体i所对应的能耗，为群体平均执行能耗，P为群体规模；（6.4.3）用新选择的染色体去更新群体；（6.4.4）如果还有新的染色体未处理，则转到（6.4.1），否则结束群体更新；所述步骤（4）采用基于缩放优先级的节能调度算法，其流程为：（4.1）进行算法初始化；（4.2）将所有任务赋以最高电压；（4.3）采用优先级链表调度算法进行任务调度，算法根据任务映射、电压级别和任务优先级输入信息，确定性地输出任务调度策略、执行时间和能耗，不能调度则返回一个无效值；（4.4）对最高电压级别的调度结果进行判断，如果执行时间大于等于截止时间，说明该调度不存在缩放空间，返回调度能量；（4.5）进行电压反复缩放过程，其中对每个可以缩放的任务进行如下操作：降低一个电压级别后进行优先级链表调度，如果满足截止时间，则计算任务Ti在当前电压下的缩放优先级，优先级为下式：$\mathrm{ZoomPriority}(i,k)=K_{\mathrm{coe}}·\frac{E(T_i,P_j,V_k)-E(T_i,P_j,V_{k-1})}{t(T_i,P_j,V_{k-1})-t(T_i,P_j,V_k)}$式中，ZoomPriority(i,k)：任务T_i在当前电压下的缩放优先级；K_coe为比例系数，E(T_i,P_j,V_k)：任务T_i在处理器P_j中以电压等级V_k运行的能耗；E(T_i,P_j,V_k-1)：任务T_i在处理器P_j中以电压等级V_k-1运行的能耗；t(T_i,P_j,V_k)：任务T_i在处理器P_j中以电压等级V_k运行的时间；t(T_i,P_j,V_k-1)：任务T_i在处理器P_j中以电压等级V_k-1运行的时间；（4.6）记录目前为止最大可缩放优先级及其对应的调度结果；（4.7）对可行的最优缩放任务降低一个电压级别，并更新当前最优能耗，如果没找到可缩放任务则返回当前最优能耗值，算法退出。