Research On Auto-Vectorization Compiling Techniques Oriented To Irregular Applications On SIMD Extension

SIMD extension generally used in CPUs,is a vector accelerator,which is one of critical parts in computers and can efficiently improve the performance of applications.As a main method of generating vector programs,Auto-vectorization has been widely researched and realized in different mainstream compilers.However,the current auto-vectorization can only deal with regular memory access applications,and has limited capability to vectorize applications with complex and irregular memory access.After an analysis of challenges in auto-vectorization,this paper focuses on the research of auto-vectorization techniques oriented to irregular applications on SIMD extension,following the phases of vector exploitation,optimization and code generation.The paper makes an in-depth study on the vector exploitation and memory access optimization of irregular applications and vector instruction generation of the irregular memory access.Our main work and contributions are as follows:The first is the research on vector exploitation of irregular applications.The automatic vectorization of existing compilers can provide accurate data analysis for regular applications,thus guiding the program to generate vector instructions.Irregular applications also contain opportunities for vector parallel execution.However,the access is not continuous or dependent on input data,which cannot makes the compiler establish an accurate data reference relationship during the compilation phase.So the compiler gives up its vectorization opportunity.This paper proposes Inspector-based irregular data access pattern recognition based on the Inspector/Executor model.We pre-analyze the irregular application access patterns before calculation.Besides,a vector packaging strategy for irregular data is proposed considering the problem of vector writing conflicts for irregular reductions.The strategy packs different iterations into vectors to solve the problem of vector exploitation for irregular applications.The second is the research on the memory access optimization of irregular applications.In irregular applications,the discontinuity and randomness of memory access make the locality of the program data poor and the efficiency of memory access low.Therefore,in order to improve the access efficiency of irregular applications,a hierarchical tiling algorithm is first presented to improve the locality of data in this paper.Then a data prefetching algorithm based on memory access records is proposed to hide the latency of memory access.Finally,a vector register reuse method based on the maximum matching degree is given to reduce the number of memory access and improve the program execution efficiency.The last is the research on vector instruction generation of the irregular memory access.The SIMD extension instruction can load continuous data in memory into the vector register at one time.However,the number of isomorphic statements in a vector packet may be smaller than the vectorization factor because of the randomness of irregular data access.Besides,a vector load instruction cannot load irregular data into a vector register.So the research on vector instruction generation for partial use of vector registers and irregular data access is required.Therefore,this paper proposes implementation schemes for insufficient vectorization and irregular vector memory access.Then,the calculation of the cost model is proposed to select the optimal scheme for the vector transformation of the program.Auto-vectorization technique of irregular applications in this paper has been realized based on GCC 5.3.0.The correctness and effectiveness of the vectorization method proposed in this paper is verified by testing the selected programs.The research in this paper can improve the acceleration performance of SIMD extension components,which has a certain guiding significance for the development of the compilation system and the optimization of the application program.