Research On Hybrid Task Scheduling Algorithm For Heterogeneous Multi-core Processors

With the rapid development of computer systems,people's demand for high-performance computers is increasing,heterogeneous multi-core processor rises quickly.Heterogeneous multi-core processor is an asymmetric multi-core processor that is composed of processing cores of various types and different computing capabilities.How to coordinate the work between these processing cores,reasonably divide tasks and allocate them to the processors for execution,is very important for the heterogeneous multi-core research.The quality of task scheduling technology determines the execution efficiency of the system.In order to further improve the parallel processing capability of heterogeneous multi-core processor,an efficient hybrid task scheduling algorithm is proposed.After summarizing,the main work of this article is as follows.(1)Aiming at the problems of lack of comprehensive calculation of communication overhead and low utilization of processor core in the existing HEFT algorithm for table scheduling,an improved table scheduling algorithm—IHEFT is proposed.In the task sorting stage,when calculating the priority value of the task,it is necessary to consider the data transmission sales volume of the current task to the export task.Then the sales volume of the calculation performed by the current task on the processor,and the task's dependence on the processor core.The dependence is judged by the variance of the execution time on each processor.Finally,a scheduling list is constructed according to the maximum cost sum of the three tasks.This scheduling strategy is mainly based on the overall consideration.The purpose is to maintain the fairness of task scheduling.In the task allocation stage,the tasks are layered and optimized according to the criterion of the earliest completion time.The task allocation plan adopting interval insertion and task replication strategy is designed.It can effectively shorten the scheduling length of the overall task and reduce the resource consumption of the processor.(2)Aiming at the problems of task division and unreasonable allocation in the task scheduling process,based on the Sparrow Search Algorithm(SSA),an improved task scheduling algorithm based on hybrid optimization strategy—IHSSA is proposed.The initialization of the population consists of two parts,one is a sparrow individual formed by encoding the task scheduling sequence generated by the IHEFT algorithm,and the other is hierarchical constraints on the individuals generated by random generation to enhance the diversity of the population.Those sparrows together form an excellent initial population.In addition,chaos perturbation strategy is introduced to avoid the phenomenon of local optimal solutions in the algorithm.The algorithm's overall search ability and solution accuracy are improved.Thereby,it will enhance the ability to execute tasks in parallel,is effective for improving the task scheduling efficiency of the system.Finally,through experimental simulation,different DAG test cases are generated through the random task graph generator,which shows that the improved IHEFT algorithm and IHSSA algorithm have a certain improvement in scheduling makespan,speed-up ratio,etc.Experiments verify the effectiveness of the algorithm.