Research On Code Optimization Combining Empirical Search And The Analytical Model

With the development of High Performance Computing (HPC), the computers' peak performances increase in a continuous and rapid way, however, the sustained performances achieved by real applications do not increase in the same scale as the machine's peak performances do. The gaps between them are widening. Program performance optimization is one of the effective ways to solve this problem, and many transformations of program performance optimization need to choose the optimization parameters carefully to abtain optimal performance. Therefore, the selection of optimization parameters is the crucial problem program performance optimization must solve.There are mainly two kinds of optimization methods to compute optimal optimization parameters—model-driven optimization and empirical optimization. A model-driven method uses a simple model of the program and the machine to select parameters. By contrast, an empirical method generates multiple versions of the program, runs all of them on the actual machine, and selects the one that results in the best performance. But it is maybe not precise to predict the parameters using a simple architectural model, and a purely empirical approach is not practical in general because of its huge costs. Therefore, we consider using an analytical model to confine the search space, and validating the effect of optimization through empirical results, and ultimately realizing model-driven empirical optimization.Aimming at reducing the cost of optimization, and improving its quality, we research on performance modeling, optimization parameter selection for model-driven empirical optimization. Our work includes:(1) We propose a framework for model-guided empirical optimization, which combines the model information and empirical optimization. The test results on the platform of PENTIUM III and PENTIUM 4 verify that model-guided empirical optimization can gain better optimization resolution with lower cost against a purely empirical approach.(2) Research on performance model. Using existing program analyzing techniques in the field of general compiler optimizations for reference, we make a deep research on optimization parameters which impact the performance farmost, and build an analytical performance model considering multiple memory hierarchy levels, which will define the range of optimization parameters where program can gain high performance.(3) Research on genetic algorithms based empirical search. We use genetic algorithms to empirically search the optimization space in our optimization framework. In the design of genetic algorithms we combine the constraint information of the parameters explored in the anylytical model which can constrain the search space, and evaluate the individual's quality based on the performance data aquired by hardware performance counters. We optimize programs based on memory access time considering multiple memory hierarchy levels with this method. Through optimization, the program of matrix multiply (MxM) and Successive Overrelaxation (SOR) gain speedup up to 3.88, and the factor of memory access cost in total running time decreases sharply as well: MxM's decreses from about 53% to 7.5% around, and SOR's decreses from about 30% to 10% around.