Research On Static Task Scheduling Algorithm For Multi-Core Systems Under Communication Constraints

With the development of information technology,the era of single core processor is gradually withdrawn from the historical stage.The appearance of multi-core processors greatly improves the performance of the computer.Among them,an efficient task scheduling strategy is the key to improve the performance of multi-core processors.For the static task scheduling problem of multi-core processors,Simple List Scheduling(SLS)algorithm has many defects,so it is difficult to get better scheduling results.Thesis analyzes the shortcomings of the simple list scheduling algorithm through theoretical analysis and example,and points out two defects of the simple list scheduling algorithm: In the task scheduling process,the simple list scheduling algorithm only considers the priority list of tasks,but ignores other task topology sequences that may lead to shorter scheduling lengths;The greedy strategy used in the simple list scheduling algorithm can only obtain the local optimal solution and can not get the overall optimal solution.Aiming at the first defect,thesis improves the traditional genetic algorithm and applies it to list scheduling,and proposes a list scheduling algorithm based on genetic algorithm(LSGA).Through many times of inheritance and mutation,a lot of task graph topological sequences are taken into consideration.For the second defects,thesis applies ant colony algorithm to list scheduling,and proposes a list scheduling scheme based on ant colony algorithm(LSACO).When the LSACO algorithm assigns the processor kernel to the task,through a large number of iterations,the algorithm gradually tends to the most reasonable processor allocation scheme.Aim at the communication path congestion on the network communication environment,thesis from two aspects that reduce the number of congestion and reduce the time of congestion to improve the LSACO algorithm,proposed multi-objective list scheduling scheme based on ant colony algorithm(MLSACO).MLSACO algorithm not only takes account of the length of task scheduling,but also alleviating the congestion of communication path in network environment.Thesis selects the length of task scheduling as the evaluation index of the algorithm,and selects four common types of task graph and random task graph to generate a large number of task map samples.And four groups of performance statistics are carried out respectively.The experimental statistics show that the scheduling results of LSGA and LSACO algorithms are obviously better than those of the simple list scheduling algorithms in all interconnected communication environments.At the same time,the performance of the LSGA algorithm is also better than the ILS-Mb(Iterative List Scheduling with Macroblock)algorithm.Especially when the communication weight is relatively large,the average speedup of the LSACO can reach 119.9%.In the communication environment of the network on chip,the scheduling performance of the MLSACO algorithm is also higher than that of the simple list scheduling algorithm,and it can effectively alleviate the path congestion problem under network on chip communication.The experimental data shows that compared with the simple list scheduling algorithm,the probability of the MLSACO algorithm to alleviate the path congestion is generally higher than 85%.