Research On Static Task Scheduling Algorithm For Multicore Systems

Multi-core processor has become the mainstream architecture of microprocessor,greatly improving the performance of microprocessor.Therefore,task scheduling,as a key factor affecting the performance of multi-core systems,has gradually attracted people's attention.For the static task scheduling problem of multi-core system,the list-based task scheduling algorithm has attracted attention because of its simple implementation and good effect.As a typical representative,SLS algorithm has its inherent defects:only consider the priority scheduling list based on BL weights,however,other scheduling lists of the task graph scheduling solution space are ignored,so the exploration of the task graph scheduling solution space is extremely insufficient.Aiming at the inherent defect of SLS algorithm,this dissertation combines biological algorithm to initialize multiple problem feasible solutions for synchronous optimization and iterative strategy,selects the priority scheduling list formed by four kinds of weight calculation strategies as the initial scheduling list combination,and proposes the task turmoil iterative strategy at the same time.The turmoil iterative strategy performs synchronous iteration on the list in the initial scheduling list combination to generate an optimal scheduling list.The algorithm is simple to implement and can explore the task graph scheduling solution space more widely,so as to obtain better task scheduling results.Due to the complex topology of the task map,multiple tasks often have the same task weight,which makes the task into a weight consistent sorting dilemma.In order to solve this problem,this dissertation proposes a list scheduling algorithm based on special macroblock with reference to the concept of SC algorithm macroblocks and macroblock topological sequences.The tasks with uniform weights are concentrated into special macroblocks,and then the macroblock topological sequence is traversed to generate a better task scheduling list,thereby optimizing task scheduling results.In this dissertation,by combining the basic parameters of the task map and the system model to generate task maps with different characteristics,a more comprehensive test task graph set is formed,and the performance of the two algorithms proposed in this dissertation is tested.The test results show that the average iteration ratio of the combined iterative list scheduling algorithm based on task turmoil up to 18.7%and the lowest is 7.9%.The average enhancement ratio of the list scheduling algorithm based on special macroblocks is up to 15.3%and the lowest is 6.8%.The adaptability of the algorithm is strong,when the scale of the task graph is expanded,the performance of the algorithm is not significantly attenuated.At the same time,the algorithm scheduling performance is better for the task graph with higher communication and higher correlation between tasks.