Research on Task Scheduling of Heterogeneous Multi-core Processor based on Replication Genetic algorithm
Xiaohui Cheng, Rui Xu · 2019
The task scheduling problem of heterogeneous multicore processors has been proved to be a NPC problem. The classical genetic algorithm has some shortcomings, that is, the convergence time is long and the efficiency is often low. Therefore, in order to give full play to the platform advantages of heterogeneous multi-core processors, this paper improves the classical genetic algorithm and proposes a based replication genetic algorithm (RGA). The main work of this paper is as follows: firstly, the DAG task scheduling model of heterogeneous multi-core processor is analyzed, which improves the ability of new individuals' reproduction by dynamically setting the crossover rate and mutation rate;and based on the replication operator, a part of individuals with higher adaptability are retained in each generation to achieve better convergence speed; at the same time, in the stage of processor selection, both direct predecessor tasks and direct tasks are considered. The influence of subsequent tasks on the completion time to ensure the load balance of the processor. Finally, the simulation results show that, compared with the classical GA and ACO, RGA not only keeps the possibility of generating new population, but also has faster convergence speed and better solving ability, improves the efficiency of task scheduling and has good scheduling fairness.