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

doi:10.19678/j.issn.1000-3428.0068440

Abstract

Abstract:

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.

Key words: heterogeneous multi-core, task scheduling, Bat Algorithm (BA), evolutionary adaptive, Directed Acyclic Graph (DAG)

摘要：

异构多核处理器的任务调度问题已经被证明是一个NP完全问题。为满足复杂应用的计算需求, 提高异构多核处理器的任务调度效率, 提出一种基于进化自适应蝙蝠算法(EABA)的异构多核处理器任务调度算法。首先, 对任务调度问题进行描述, 并建立相应的数学模型; 接着, 设计任务分配编码方案和适应度函数, 将所提算法映射到离散空间, 使其能够适用于离散的异构多核处理器任务调度问题的研究; 然后, 为避免算法过早陷入局部最优, 引入衰减脉冲策略和进化自适应变换策略; 最后, 设计仿真实验, 将所提算法与蝙蝠算法(BA)、改进粒子群算法(IPSO)、人工鱼群算法(AFSA)、改进鲸鱼优化算法(IWOA)进行比较。实验结果表明, 在中等规模任务(40~70个)和大规模任务(80~100个)下, EABA算法的最优调度长度与次优算法相比分别缩短了12.86%和13.67%, 算法平均执行时间分别减少了14.51%和13.50%。

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

FENG Shuang, JIANG Bo, XU Hong. Task Scheduling for Heterogeneous Multi-Core Processors Based on Evolutionary Adaptive Bat Algorithm[J]. Computer Engineering, 2025, 51(5): 249-256.

冯爽, 江波, 徐宏. 基于进化自适应蝙蝠算法的异构多核处理器任务调度[J]. 计算机工程, 2025, 51(5): 249-256.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0068440

https://www.ecice06.com/EN/Y2025/V51/I5/249

Figures/Tables 9

Fig.1 Heterogeneous multi-core system model

Fig.2 Schematic diagram of task DAG

Fig.3 Procedure of the EABA algorithm

Fig.4 Iterative evolution curves of different algorithms when the number of tasks is 10

Fig.5 Comparison of optimal scheduling length under different task sizes

Fig.6 Comparison of average execution time of algorithms under different task sizes

References 25

1	ULLMAN J D . NP-complete scheduling problems. Journal of Computer and System Sciences, 1975, 10 (3): 384- 393. doi: 10.1016/S0022-0000(75)80008-0
2	SAHOO R M , KUMARI PADHY S . A novel algorithm for priority-based task scheduling on a multiprocessor heterogeneous system. Microprocessors and Microsystems, 2022, 95, 104685. doi: 10.1016/j.micpro.2022.104685
3	HAMED A Y , ALKINANI M H . Task scheduling optimization in cloud computing based on genetic algorithms. Computers, Materials & Continua, 2021, 69 (3): 3289- 3301. URL
4	ABUALIGAH L , ALKHRABSHEH M . Amended hybrid multi-verse optimizer with genetic algorithm for solving task scheduling problem in cloud computing. The Journal of Supercomputing, 2022, 78 (1): 740- 765. doi: 10.1007/s11227-021-03915-0
5	SIDDESHA K, JAYARAMAIAH G V. Energy-aware task scheduling approach using DVFS and particle swarm optimization for heterogeneous multicore processors[EB/OL]. [2023-09-10]. https://link.springer.com/chapter/10.1007/978-981-16-1342-5_75.
6	KHAN M S A , SANTHOSH R . Task scheduling in cloud computing using hybrid optimization algorithm. Soft Computing, 2022, 26 (23): 13069- 13079. doi: 10.1007/s00500-021-06488-5
7	杨辉华, 张晓凤, 谢谱模, 等. 基于布谷鸟搜索的多处理器任务调度算法. 计算机科学, 2015, 42 (1): 86- 89. doi: 10.11896/j.issn.1002-137X.2015.1.020
	YANG H H , ZHANG X F , XIE P M , et al. Multiprocessor task scheduling method based on cuckoo search algorithm. Computer Science, 2015, 42 (1): 86- 89. doi: 10.11896/j.issn.1002-137X.2015.1.020
8	PIROZMAND P , JALALINEJAD H , HOSSEINABADI A A R , et al. An improved particle swarm optimization algorithm for task scheduling in cloud computing. Journal of Ambient Intelligence and Humanized Computing, 2023, 14 (4): 4313- 4327. doi: 10.1007/s12652-023-04541-9
9	李静梅, 张大虎, 吴艳霞, 等. 基于蚁群优化算法的异构多核线程调度方法. 计算机工程与设计, 2014, 35 (6): 1946- 1950. doi: 10.3969/j.issn.1000-7024.2014.06.014
	LI J M , ZHANG D H , WU Y X , et al. Heterogeneous multi-core thread scheduling method based on ant colony optimization algorithm. Computer Engineering and Design, 2014, 35 (6): 1946- 1950. doi: 10.3969/j.issn.1000-7024.2014.06.014
10	张金泉, 徐寿伟, 李信诚, 等. 基于正交自适应鲸鱼优化的云计算任务调度. 计算机应用, 2022, 42 (5): 1516- 1523. doi: 10.11772/j.issn.1001-9081.2021050806
	ZHANG J Q , XU S W , LI X C , et al. Cloud computing task scheduling based on orthogonal adaptive whale optimization. Journal of Computer Applications, 2022, 42 (5): 1516- 1523. doi: 10.11772/j.issn.1001-9081.2021050806
11	程小辉, 童辉辉, 康燕萍. 基于麻雀搜索算法的异构多核处理器任务调度. 计算机应用与软件, 2023, 40 (4): 211- 216. doi: 10.3969/j.issn.1000-386x.2023.04.034
	CHENG X H , TONG H H , KANG Y P . Heterogeneous multiprocessor task scheduling based on sparrow search algorithm. Computer Applications and Software, 2023, 40 (4): 211- 216. doi: 10.3969/j.issn.1000-386x.2023.04.034
12	CLERC M , KENNEDY J . The particle swarm -explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 2002, 6 (1): 58- 73. doi: 10.1109/4235.985692
13	蒋清源. FPGA计算资源约束下的异构多核系统任务调度算法设计与实现[D]. 上海: 华东师范大学, 2022.
	JIANG Q Y. Design and implementation of task scheduling algorithm for heterogeneous multi-core system under the constraint of FPGA computing resources[D]. Shanghai: East China Normal University, 2022. (in Chinese)
14	梁秋玲, 张向利, 张红梅, 等. 基于多核处理器的关联任务并行感知调度算法. 计算机工程, 2021, 47 (7): 212- 217. doi: 10.19678/j.issn.1000-3428.0057225
	LIANG Q L , ZHANG X L , ZHANG H M , et al. Parallel perceptual scheduling algorithm for related tasks based on multi-core processors. Computer Engineering, 2021, 47 (7): 212- 217. doi: 10.19678/j.issn.1000-3428.0057225
15	KIM S I , KIM J K . A method to construct task scheduling algorithms for heterogeneous multi-core systems. IEEE Access, 2019, 7, 142640- 142651. doi: 10.1109/ACCESS.2019.2944238
16	PRADHAN R , SATAPATHY S C . Energy-aware cloud task scheduling algorithm in heterogeneous multi-cloud environment. Intelligent Decision Technologies, 2022, 16 (2): 279- 284. doi: 10.3233/IDT-210048
17	XIE G Q , ZENG G , LIU L J , et al. Mixed real-time scheduling of multiple DAGs-based applications on heterogeneous multi-core processors. Microprocessors and Microsystems, 2016, 47, 93- 103. doi: 10.1016/j.micpro.2016.04.007
18	YANG X S. A new metaheuristic bat-inspired algorithm[EB/OL]. [2023-09-10]. https://link.springer.com/chapter/10.1007/978-3-642-12538-6_6.
19	GANDOMI A H , YANG X S . Chaotic bat algorithm. Journal of Computational Science, 2014, 5 (2): 224- 232. doi: 10.1016/j.jocs.2013.10.002
20	CAI X J , WANG L , KANG Q , et al. Bat algorithm with Gaussian walk. International Journal of Bio-Inspired Computation, 2014, 6 (3): 166- 174. doi: 10.1504/IJBIC.2014.062637
21	DENG Z , SHEN H , CAO D , et al. Task scheduling on heterogeneous multiprocessor systems through coherent data allocation. Concurrency and Computation: Practice and Experience, 2021, 33 (10): e6183. doi: 10.1002/cpe.6183
22	CHEN J C , HE Y , ZHANG Y , et al. Energy-aware scheduling for dependent tasks in heterogeneous multiprocessor systems. Journal of Systems Architecture, 2022, 129, 102598. doi: 10.1016/j.sysarc.2022.102598
23	ELCOCK J , EDWARD N . An efficient ACO-based algorithm for task scheduling in heterogeneous multiprocessing environments. Array, 2023, 17, 100280. doi: 10.1016/j.array.2023.100280
24	HASAN R A , ALHAYALI R A I , MOHAMMED M A , et al. An improved fish swarm algorithm to assign tasks and cut down on latency in cloud computing. TELKOMNIKA (Telecommunication Computing Electronics and Control), 2022, 20 (5): 1103. doi: 10.12928/telkomnika.v20i5.22645
25	CHAKRABORTY S , SAHA A K , CHHABRA A . Improving whale optimization algorithm with elite strategy and its application to engineering-design and cloud task scheduling problems. Cognitive Computation, 2023, 15 (5): 1497- 1525. doi: 10.1007/s12559-022-10099-z

[1]	WANG Kewen, ZHANG Weiting, SUN Tong. Resource Scheduling Mechanism for Space-Air-Ground Integrated Computing Power Networks [J]. Computer Engineering, 2025, 51(5): 52-61.
[2]	Yitao ZHOU, Yang LI, Chao HAN, Yulai ZHAO, Ling WANG, Jianhua LI. Task Scheduling and Thermal Management System for S-NUCA Heterogeneous Processor [J]. Computer Engineering, 2024, 50(2): 196-205.
[3]	YAN Changyu, ZHANG Lei. Hybrid List-Scheduling Algorithm Based on Task Duplication and Pre-Scheduling [J]. Computer Engineering, 2024, 50(12): 124-132.
[4]	LIANG Qiuling, ZHANG Xiangli, ZHANG Hongmei, YAN Kun. Parallel Perceptual Scheduling Algorithm for Related Tasks Based on Multi-Core Processors [J]. Computer Engineering, 2021, 47(7): 212-217.
[5]	XIONG Wen, YU Quanxi, WU Renbo, LUN Huiqin, KONG Haibin, TAN Junguang. Research on Task Scheduling of Flexible Regulation and Control Platform Based on Evolutionary Game [J]. Computer Engineering, 2019, 45(7): 86-94.
[6]	NI Hong, LIU Xin. Multi-Core optimization technology of unstructured grid based on Sunway TaihuLight [J]. Computer Engineering, 2019, 45(6): 45-51.
[7]	REN Liangyu,ZHAO Chengping,YAN Hua. Multi-core scheduling algorithm based on task duplication and redundancy elimination [J]. Computer Engineering, 2019, 45(5): 59-65.
[8]	ZHENG Chuhong, PENG Yong, XU Yiming, LIAO Yi. Task Scheduling Algorithm Based on Improved NSBBO in Cloud Manufacturing Environment [J]. Computer Engineering, 2019, 45(10): 26-32.
[9]	YANG Pingping,YUE Chunsheng,HU Zeming. Multi-level Pipeline Scheduling Algorithm in Heterogeneous Signal Processing Platform [J]. Computer Engineering, 2018, 44(11): 83-89.
[10]	GAO Feng,DENG Fei,CHEN Quangen. Design of Semi-physical Simulation Test Platform Based on Hierarchical Model [J]. Computer Engineering, 2018, 44(1): 104-109,115.
[11]	ZHANG Jing,SUN Shaojie,FAN Hongbo. A Task Scheduling Algorithm with High Stability Based on Cost Optimization [J]. Computer Engineering, 2017, 43(7): 60-63,69.
[12]	PENG Ziran,WANG Guojun. An Optimal Energy Saving Real-time Task Scheduling Algorithm for Mobile Terminal [J]. Computer Engineering, 2017, 43(5): 67-74.
[13]	ZHANG Jing,SUN Shaojie,FAN Hongbo,FU Xin,ZHANG Guo. Task Scheduling Algorithm in Heterogeneous Multi-core Processor with High Real-time Performance [J]. Computer Engineering, 2017, 43(5): 55-59.
[14]	HUANG Tinghui,WANG Yuliang,WANG Zhen,CUI Gengshen. Spark I/O Performance Optimization Based on Memory and File Sharing Mechanism [J]. Computer Engineering, 2017, 43(3): 1-6.
[15]	YANG Zhiwei,ZHENG Quan,WANG Song,YANG Jian,ZHOU Lele. Adaptive Task Scheduling Strategy for Heterogeneous Spark Cluster [J]. Computer Engineering, 2016, 42(1): 31-35,40.

Please choose a citation manager

Content to export