Research On Loop Optimization Based On Polyhedral Model

In many communication applications,such as signal and image processing,most of the running time is spent in the calculation intensive loop.Polyhedron model can make full use of the advantages of modern multi-core architecture to explore the parallelism and locality of the loop-nest,which becomes a new choice for loop optimization.However,due to the strict modeling constraints of the polyhedron model and the complexity of the programs in different fields,not all loop nests can be represented as polyhedrons.It is necessary to expand the modeling of the polyhedron model to fully utilize the optimization effect of the polyhedral model.In addition,as an important loop transformation to improve the locality of data,traditional loop tiling technologies can only perform regular parallelogram tiles,which seriously affects the selection of the optimal tile size.Moreover,the increasingly complex hardware storage architecture also makes it difficult to optimize the optimal tiling algorithm aimed at improving data locality.Therefore,the polygon tiling technology proposed in this paper has great significance to discuss how to further optimize data locality by choosing a reasonable tile shape and size.Based on the polyhedron model,this thesis mainly makes the following optimization and Innovation:1.A pre-optimization method for polyhedron model identification is proposed: many loop-nests cannot be identified and expressed as polyhedron due to the strict limitation of polyhedron model modeling,which makes many loops lose the opportunity of using polyhedron model optimization.In order to solve this problem,based on the open source LLVM compilation framework,a new normalized processing pass(Pass)for polyhedrons is added and implemented.And tries to solve the non-affine factors that have the greatest impact on polyhedron modeling through a fixed-value substitution method.In addition,in order to make the recognition algorithm converge to the hot spot loop faster,the static control parts recognition algorithm is further optimized based on the traversal of the natural loop tree.2.A method of polygon tiling based on reuse mode is proposed: the traditional loop tiling methods can only form regular parallelogram tiles.Although regular tiles can also improve the data locality,but this simple tiling method often hides more complex dependency,which will seriously affect the data localization effect of loop tiling optimization.In addition,this method will also lead to an excessive number of tiles,which will increase management overhead and reduce the performance improvement caused by tiles.In order to solve this problem,based on the powerful linear representation ability of the polyhedron model,this paper proposed a polygon tiling method based on the reuse patterns,and gives an optimized solution to the block shape and block size.The related loop optimization methods proposed in this paper are based on the open source LLVM compilation framework.The test results show the correctness of the optimization method and the effectiveness of the algorithm.