key step in program performance optimization is to determine optimal values for certain parameters. Static approaches determine these values based on analytical models. However, complex computer architectures and complex code structures limit the strength of them. Execution-driven approaches like iterative compilation determine these parameter values by executing the program with different parameter values and select the one with the shortest runtime. These approaches can find excellent results for they accurately account for all machine and program components. But the expensive compilation cost has limited their application scope to embedded applications and a small group of math kernels.

We propose a low cost iterative compilation approach Lega(Limited Execution and Genetic Algorithm) for scientific program optimization parameter selection. It consists of three components: (1)parameterizations to make use of the native compiler; (2) program reduction transformations to reduce the time spent on evaluating each parameter value; (3)genetic algorithm to accelerate the parameter search process. We apply Lega to three math kernels and three SPEC95 benchmarks on two platforms. Results show that Lega can find excellent parameters comparable to previous iterative methods in much shorter time. Its cost is 5.4% of the original iterative compilation for the three math kernels on average. And its cost is 47.22% of the original iterative compilation for the three SPEC95 benchmarks on average, although the latter uses training input set instead of reference input set for the search procedure.