Research On Key Techniques In Low-cost Iterative Compilation Optimization

In recent years, iterative compilation has become a hotspot in the area of program optimizations for high performance computing architectures. It investigates sequences of parameters for various transformations, generates many versions of a program and selects the one with the highest speedup by actually executing the program on the target machine, outperforming static compilation approaches significantly. However, transformation parameters, the order in which transformations are applied, and even which transformations must be applied and how many times, all form a huge optimization space. Therefore, iterative compilation method is quite time-consuming, due to multiple, costly "runs" of candidate implementations and the combinatorics of optimization space, which make it impractical for the optimization of general applications.Aiming at reducing the optimization cost of iterative compilation, we research on the reduction of the optimization space, the search strategies, the partition of the optimization space, the representation of program transformations, and the optimization framework. Experimental results validate the effectiveness of the optimization methods presented in this paper. Main contributions are listed as follows:1. Research on iterative compilation is overviewed, and the drawbacks of current iterative compilation research are pointed out.2. An optimization space reduction technique is presented based on the architecture and empirical knowledge about applications, to limit the optimization space. Experimental results indicate our approach can produce parameter values with better performance and lower cost.3. Nelder-Mead simplex based iterative compilation optimization parameter search algorithm is presented. Experimental results prove that for iterative compilation optimization parameters selection problem, the Nelder-Mead simplex search strategy can produce parameter values with better performance than that of GA and random search while its search cost is lower than GA in most cases.4. A hybrid algorithm–UMDA/S: Univariate Marginal Distribution Algorithm with Nelder-Mead Simplex Search is introduced, which utilizes the optimization space structure and parameter dependence to find the optimal parameter. Elitist reservation, weighted estimation and mutation are proposed to improve UMDA/S'performance. Comparisons with three algorithms show the ability of UMDA/S to locate more excellent parameters and to achieve more performance improvement.5. A program optimization transformation model POTraM based on hardware performance counters is presented, to decide how and when to apply transformations and to partition the optimization space. Experimental results show that POTraM can effectively improve programs'floating-point performance, reducing programs'runtime, therefore, lessening the performance gap for high-performance applications.6. Aiming at investigating the best phase order and the best transformation parameters simultaneously, this paper presents a novel iterative compilation method, which integrates the advantages of polyhedral model and model-guided iterative compilation to create a unique and powerful framework that is capable of fully automated non-parameterized code transformation and model-guided parameterized code transformation as well as automatic parameter search. The framework is demonstrated on three typical computational kernels for code transformations to achieve performance that greatly exceeds the native compiler, and is significantly better than the performance of state-of-the-art polyhedral model based loop transformations and that of iterative compilation, generating efficient code on complex loop nests.