P. Balaprakash, S. M. Wild, and B. Norris, "SPAPT: Search Problems in Automatic Performance Tuning," Preprint ANL/MCS-P1872-0411, April 2011. [pdf]
Automatic performance tuning of computationally intensive kernels in scientific applications is a promising approach to achieving good performance on different computing architectures while preserving the kernel implementations readability and portability. A major bottleneck in automatic performance tuning is the computation time required to test the large number of possible code variants, which grows exponentially with the number of tuning parameters. Consequently, the design, development, and analysis of effective search techniques capable of finding high-performing parameter configurations quickly have gained significant attention in recent years. An important element needed for this research is a collection of test problems that allow performance engineering and mathematical optimization researchers to conduct rigorous algorithmic developments and experimental studies. In this paper, we describe a set of extensible and portable search problems in automatic performance tuning (SPAPT) whose goal is to aid in the development and improvement of search strategies and performance-improving transformations. SPAPT contains representative implementations from a number of lower-level, serial performance tuning tasks in scientific applications. We present an illustrative experimental study on a number of problems from the test suite. We discuss some important issues such as modeling, search space characteristics, and performance objectives.