Reduction transformations for optimization parameter selection

Program performance optimization often involves choosing right parameters to minimize the program´s runtime. Selecting optimization parameters by means of execution-driven search is guaranteed to find excellent results, for it accurately accounts for all performance components of the target platform. But the major drawback of execution-driven approach is the excessive compilation time due to thousands of runs of the original program. In this article, we propose a novel technique called program reduction transformations to reduce the cost of execution-driven optimization parameter selection. It is based on our observation to the characteristics of the scientific applications and the optimization parameter selection task. The ideal is to transform the program before it is used in execution-driven parameter selection procedure. The transformed program runs in much shorter time but preserves the parameter selection quality. This technique greatly reduces the time spent on evaluating each candidate parameter and makes execution-driven optimization parameter selection affordable. We formulate the theoretic foundation of program reduction transformation. And we find several situations where reduction transformations can be legally applied. These situations are common in scientific applications. Experiments done for two math kernels and three SPEC benchmarks show that our approach is both feasible and effective