Based On Intelligent Search Algorithm For Multi-core Processor Task Scheduling

With the continuous demand growth for the processor, performance and power consumption make the development of the single-core processor have encountered the bottleneck. So the multi-core processor begins to get attention. Task scheduling on multi-core processor is from two aspects of time and space to assign every task to the corresponding processor. Reasonable task scheduling can improve the performance of the processor, and also can reduce the loss of the system. Task scheduling on multi-core processor includes allocation and scheduling. Allocation is mainly to allocate tasks to cores, that is to say, match the task to the reasonable core; Scheduling is mainly to solve when to perform tasks, that is, get the start time and end time on corresponding cores. The factors for task scheduling are the execution time of every task, the communication overhead between two tasks and the dependencies among tasks. The domestic and foreign scholars have conducted in-depth research on this problem, and they have proved that task scheduling on multi-core processor is a combinatorial optimization problem.It cannot find the optimal solution in polynomial time complexity, and is NP-hard problem.In this thesis, the tasks of research have dependencies, and they are allocated on homogeneous multi-processor system. In view of the parallelism and global search of the intelligent search algorithm, this article uses several kinds of common intelligent search algorithm to solve the problem of task scheduling. The main work is as follows:(1) This thesis puts forward the improve population of genetic algorithm (IPGA) and adopts the following methods to improve:First, use hierarchical scheduling based on heuristic method to initialize the population so as to improve the quality of initial population; Second, develop the new crossover method and dynamic mutation to improve its local search ability; Third, employ perturbation strategy to improve its global search ability. Finally, put the best individual into the next generation to ensure that the global optimal individual can participate in the roulette wheel selection.Experimental results show IPGA can get smaller task makespan and faster ability of searching optimal solution.(2) This thesis proposes the modified hybrid genetic algorithm (MHGA), in which the heuristic algorithm, tabu search algorithm (TS) and simulated annealing algorithm (SA) are integrated. The improvement of MHGA include:First, employ tabu search algorithm based on random number crossover to enhance the diversity of the population; Second, adopt simulated annealing algorithm based on mutation to improve the quality of the individual; Finally, compare MHGA with IPGA in some aspects.Experimental results show that MHGA can obtain smaller task scheduling time and have ability to search better solution quickly in comparison with other GAs.(3) This thesis proposes the modified hybrid particle swarm optimization (MHPSO), in which the heuristic algorithm and simulated annealing algorithm are integrated. It uses the following ideas to optimize:First, heuristic method is used to initialize the particle swarm, and it improves the quality of the original particle swarm; Second, put forward a kind of discrete particle encoding rule; Finally, use the simulated annealing algorithm to update the particle position and velocity. The simulation results show that comparing with HGA?PGA and IPGA, this algorithm has shorter total task completion time. Comparing with MHGA, this algorithm has a little longer total task completion time, but its simulation time is shorter.