Research On Heuristic Search And Optimization Oriented To Loop Auto-schedule

Loop code usually occupies most of the execution time in compute-intensive programs.The way the loop is iterated and scheduled often significantly affects the overall performance of the program.Therefore,finding a suitable schedule for loop code has always been the focus of program performance optimization.However,due to the high development cost of manually optimizing code and the low readability of optimized code,automatic scheduling technology has received more and more attention recently.Most existing automatic scheduling research is based on their own domain-specific languages or compilers and can achieve good optimization effects on some specific applications.However,they often lack support for general-purpose programming languages and general applications.Some automatic optimization framework for loop code in general-purpose programming languages requires developers to provide parameterized scheduling templates,which cannot be completely automatic.In response to this situation,this dissertation studies the automatic scheduling technology of loops in the general-purpose programming language C/C++,constructs a loop automatic scheduling framework starting from source code,and uses deep learning technology to construct a cost model to accelerate the loop scheduling search process.The main research results of this dissertation include:Analyze the loop structure in C/C++source code and apply different loop scheduling transformations to it to construct a scheduling search space.Use the adjusted Monte Carlo tree search algorithm and Bayesian optimization algorithm to efficiently search the search space and obtain the optimal schedule,thereby realizing the loop automatic scheduling process.The experimental results show that compared with Polly’s loop optimization compiler based on heuristic algorithms,the automatic scheduling framework proposed in this dissertation can obtain scheduling results with better performance on most benchmark programs.Since a large number of scheduling samples need to be evaluated for performance during the scheduling search process,this dissertation designs a cost model based on deep learning to predict the speedup ratio of scheduling,replacing time-consuming compilation and execution processes to improve the efficiency of the automatic scheduling framework.In order to train the cost model,this dissertation also designed a random code generator and used it to construct a dataset with 160,000 data points.The average absolute error of this dissertation’s proposed cost model in predicting scheduling speedup ratio is 0.18.This dissertation also applies the model to automatic scheduling framework and automatically schedules 10 benchmark programs.The experimental results show that when using this cost model,the automatic scheduling framework finds competitive scheduling results about 110 times faster.