Argonne National Laboratory

Can Search Algorithms Save Large-Scale Automatic Performance Tuning?

TitleCan Search Algorithms Save Large-Scale Automatic Performance Tuning?
Publication TypeConference Paper
Year of Publication2010
AuthorsBalaprakash, P, Wild, SM, Hovland, PD
Conference NameProceedings ICCS 2011 in Procedia Computer Science
Date Published11/2010
Conference LocationTsukuba, Japan
Other NumbersANL/MCS-P1823-0111

Empirical performance optimization of computer codes using autotuners has received signifi cant attention in recent years. Given the increased complexity of computer architectures and scientifi c codes, evaluating all possible code variants is prohibitively expensive for all but the simplest kernels. One way for autotuners to overcome this hurdle is through use of a search algorithm that fi nds high-performing code variants while examining relatively few variants. In this paper we examine the search problem in autotuning from a mathematical optimization perspective. As an illustration of the power and limitations of this optimization, we conduct an experimental study of several optimization algorithms on a number of linear algebra kernel codes. We fi nd that the algorithms considered obtain performance gains similar to the optimal ones found by complete enumeration or by large random searches but in a tiny fraction of the computation time.