Title: Can search algorithms save large-scale automatic performance tuning?
Authors: Prasanna Balaprakash, Stefan Wild, Paul Hovland
Abstract: Empirical performance optimization of computer codes using autotuners has received significant attention in recent years. Given the increased complexity of computer architectures and scientific 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 finds 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 find 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.
Keywords: autotuning; empirical tuning; optimization; performance-tuning
Thanks: This work was supported by the U.S. Department of Energy under Contract No. DE-AC02-06CH11357. Computational resources were provided by the Laboratory Computing Resource Center at Argonne National Laboratory.
Status: Appears in Proceedings of the International Conference on Computational Science, ICCS 2011, Procedia Computer Science, Vol. 4, pp. 2136-2145, 2011. Presented at the Sixth international Workshop on Automatic Performance Tuning (iWAPT2011).
Link: [PDF from ICCS] [earlier PDF available from ANL tech reports]
title = "Can search algorithms save large-scale automatic performance tuning?",
author = "Prasanna Balaprakash and Stefan M. Wild and Paul D. Hovland",
journal = "Procedia Computer Science",
volume = "4",
pages = "2136 - 2145",
year = "2011",
note = "Proceedings of the International Conference on Computational Science, ICCS 2011",
issn = "1877-0509",
doi = "10.1016/j.procs.2011.04.234"
Back to Stefan Wild's homepage