Research And Design On Task Scheduling Algorithms For Cloud Computing Heterogeneous Multi-Core Systems

As technology advances and user demand for data and computing grows,achieving high performance resource scheduling plays a critical role in cloud computing environments.Efficient scheduling algorithms not only improve user service quality but also reduce cloud computing platform overhead.It’s well known that the task scheduling problem of cloud computing heterogeneous multi-core systems is the NP-Complete problem.Task scheduling algorithm research is mainly divided into dynamic task scheduling and static task scheduling,where static task scheduling algorithms are mainly divided into two categories: one category is based on heuristic task scheduling algorithms,which can be subdivided into list scheduling method,task repetition scheduling method and clustering method;the other category is based on random search meta-heuristic scheduling algorithms,which can be subdivided into genetic algorithm based,ant colony based,particle swarm based and other multi-class meta heuristic evolutionary algorithms.Many heuristic or meta-heuristic methods have been proposed in the research of static task scheduling for heterogeneous multicore systems in cloud computing.However,heuristic algorithms depend on specific problems,and meta-heuristic methods suffer from incomplete search space or inefficient search for optimal solutions,as well as low resource utilization.In this thesis,we propose two novel task scheduling algorithms,the heuristic parent task repetition algorithm(PTD algorithm)and the hybrid metaheuristic and parent task repetition scheduling algorithm(HMP algorithm),for task scheduling in cloud computing heterogeneous multicore systems.The main work and contributions of this thesis include.1.Design and develop PTD heuristic task duplication scheduling algorithm The PTD algorithm introduces the concept of pessimistic time cost and proposes a new task priority calculation formula and processor selection strategy.The PTD algorithm uses task duplication strategy to reduce inter-task communication overhead,minimizes application completion time,and improves processor resource utilization.By randomly generating application graphs with different structures and comparing the performance of the algorithm with real application experiments,the overall performance of PTD algorithm outperforms four classical comparison algorithms: HEFT,PEFT,HEFTGA and IACO algorithm.The average completion time in randomly generated graphs is saved by 11.6% and resource utilization is improved by 8.6%.2.Design and develop HMP task scheduling algorithm with hybrid metaheuristic and PTD algorithm The HMP algorithm mainly based on ant colony algorithm for optimization,proposes guided ants,dynamic volatile and secreted pheromone and introduces pheromone reward and punishment mechanism,and introduces after ant colony evaluation mutation variation and crossover operation modules in the genetic algorithm to expand the solution space of the algorithm,while using the PTD algorithm to evaluate the task priority queue search of ants.Experiments are conducted through extensive random generation and real applications,real applications include Gaussian elimination method,Fast Fourier Transform,Cyber Shake,Montage,Sipht and Inspiral applications.The implementation shows that the HMP algorithm outperforms the comparison algorithm in completion time performance for 90% of the examples,and has significantly better performance in several performance metrics.