基于进化自适应蝙蝠算法的异构多核处理器任务调度  

Task Scheduling for Heterogeneous Multi-Core Processors Based on Evolutionary Adaptive Bat Algorithm

作　　者：冯爽 江波 徐宏 FENG Shuang;JIANG Bo;XU Hong(The 32nd Research Institute of China Electronics Technology Group Corporation,Shanghai 201808,China)

机构地区：[1]中国电子科技集团公司第三十二研究所,上海201808

出　　处：《计算机工程》2025年第5期249-256,共8页Computer Engineering

摘　　要：异构多核处理器的任务调度问题已经被证明是一个NP完全问题。为满足复杂应用的计算需求,提高异构多核处理器的任务调度效率,提出一种基于进化自适应蝙蝠算法(EABA)的异构多核处理器任务调度算法。首先,对任务调度问题进行描述,并建立相应的数学模型;接着,设计任务分配编码方案和适应度函数,将所提算法映射到离散空间,使其能够适用于离散的异构多核处理器任务调度问题的研究;然后,为避免算法过早陷入局部最优,引入衰减脉冲策略和进化自适应变换策略;最后,设计仿真实验,将所提算法与蝙蝠算法(BA)、改进粒子群算法(IPSO)、人工鱼群算法(AFSA)、改进鲸鱼优化算法(IWOA)进行比较。实验结果表明,在中等规模任务(40~70个)和大规模任务(80~100个)下,EABA算法的最优调度长度与次优算法相比分别缩短了12.86%和13.67%,算法平均执行时间分别减少了14.51%和13.50%。The task scheduling problem for heterogeneous multi-core processors has been proven to be NP-complete.To meet the computational demands of complex applications and enhance the efficiency of task scheduling in heterogeneous multi-core processors,an Evolutionary Adaptive Bat Algorithm(EABA)-based task scheduling algorithm for heterogeneous multi-core processors is proposed.First,the task scheduling problem is described,and a corresponding mathematical model is established.Subsequently,a task allocation encoding scheme and a fitness function are designed to map the proposed algorithm into a discrete space,making it suitable for studying discrete task scheduling problems in heterogeneous multi-core processors.Subsequently,to prevent the algorithm from prematurely converging to the local optima,a decaying pulse strategy and an evolutionary adaptive transformation strategy are introduced.Finally,simulation experiments are designed to compare the proposed algorithm with the Bat Algorithm(BA),Improved Particle Swarm Optimization(IPSO)algorithm,Artificial Fish Swarm Algorithm(AFSA),and Improved Whale Optimization Algorithm(IWOA).The experimental results demonstrate that,under medium-scale tasks(40 to 70 tasks)and large-scale tasks(80 to 100 tasks),the optimal scheduling length of the EABA is shortened by 12.86%and 13.67%,respectively,compared with that of the suboptimal algorithm,with average execution time reductions of 14.51%and 13.50%,respectively.

关 键 词：异构多核 任务调度 蝙蝠算法 进化自适应 有向无环图 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]