Research On The Thread-level Speculation Execution Model For LLVM Compiler

Thread-Level Speculation allows programs with a large amount of data dependencies to aggressively execute programs in parallel by predicting the dependency values in advance to obtain parallel benefits.As the core part of speculative execution,the efficient design of the execution model is crucial to the improvement of program speedup performance.However,the existing TLS execution model has a high misspeculation rate and low parallelism.At the same time,excessive overhead will be introduced in the execution process,which offsets the parallel performance.In order to solve the above-mentioned problems,this thesis starts research from three aspects: program feature analysis and extraction,sequential program automatic speculation and parallel conversion,and speculative execution model design.The main work of this thesis is summarized as follows:(1)A program feature analysis method that combines static and dynamic technologies is proposed.Due to the internal dependencies of the program,speculative parallelization becomes particularly difficult.Accurately analyzing and extracting program features plays a vital role in guiding thread division,thread scheduling and even speculative parallel version code generation.To this end,based on the LLVM compiler,this article proposes a mixed program profiling method.Using static analysis technology to analyze the behavior characteristics of the basic blocks.Analyze the control relationship and call relationship between the basic blocks.Constructing the control flow graph and the call relationship graph,thereby calculate the basic block frequency and branch probability.The dynamic analysis technology of instrumentation operation obtains the average number of iterations,calls and running instructions when the program is running.Meanwhile,the dynamic information when the program is running is obtained,which provides an analysis basis for the program's automatic speculation and parallelism.(2)A sequential program automatic speculation parallel conversion method based on LLVM compiler is proposed.The traditional method requires the programmer to manually insert the speculative statement into the sequential program when the program automatically speculates in parallel,which requires a lot of programmers and will spend a lot of time and energy.In order to overcome this drawback,this thesis expands the instruction library and function library of LLVM on the basis of program feature analysis and extraction to support speculative parallelism.The method uses the front-end tool Clang of the LLVM compiler to complete the conversion task of sequential programs to sequential intermediate language.At the meanwhile it uses the custom speculative parallel conversion pass to realize the conversion of sequential version IR to speculative parallel version IR,which provides a theoretical basis for speculative execution of sequential programs.(3)A pure software speculative execution model based on LLVM compiler is designed.The current speculation execution model has a high false speculation rate and high overhead.Combining the two prediction methods of last used value and step size prediction,this thesis uses a mixed value prediction method to further improve the accuracy of value prediction and reduce the rollback rate of speculation parallel.An adaptive Fork model is designed,properly dividing thread tasks according to program characteristics and using cost benefit evaluation strategy,fully extracting procedural nature,and stimulating parallel potential.An efficient memory management strategy is adopted to store the speculative thread state and the nonspeculative thread state separately to accelerate the communication process between the speculative thread and the main thread,reduce space overhead and accelerate the verification process.This model provides an effective execution mechanism for TLS.This thesis implements a speculative multi-threaded execution model based on the LLVM compilation framework and an ubuntu system with an 8-core processor.The experiment uses a total of 6 computationally intensive and memory-intensive programs for testing.The experimental results show that the execution model can achieve a maximum speedup of 3.76 times and an average speedup of 2.59 times.Compared with the existing TLS execution model,it has achieved the average speedup rate is 9%,and the average execution efficiency of nonspeculative threads is 94.63%.Compared with the traditional Fork model,the adaptive Fork model can bring an average 4% performance improvement.The experimental results show that the speculative execution model based on LLVM can fully tap the parallelism of the program and effectively improve the speedup performance of the program.