(182h) Autotuning with Derivative-Free Optimization

As the landscape of high performance computing evolves, there is a growing need to design software that is optimal on a variety of system architectures. To address this need, algorithms are designed with tunable parameters to allow for performance portability. However, identifying optimal tuning parameters requires solving a large global optimization problem without an explicit algebraic function. Past research has been conducted to automatically determine good tuning parameters through the use of hill climbing algorithms [1], Nelder-mead simplex algorithms [5], genetic algorithms [2], and simulated annealing [4].

In this work we investigate the benefits of autotuning with derivative-free optimization (DFO). While most of the search techniques implemented in autotuners utilize local DFO solvers or heuristic based methods, by employing model-based and global DFO solvers [6], we are able to quickly find high quality tuning parameters. We compare our proposed methodology against state-of-the-art autotuning techniques such as OpenTuner [1], Active Harmony [7], and Starchart [3]. We carry out experiments on dense linear algebra kernels that are essential to the performance of numerous algorithms. In this work, we tune GPU algorithms which have a more complex parameter space than traditional CPU algorithms. We demonstrate the ability of our approach to tune any system by tuning a collection of algorithms on different GPU architectures.

References

[1] J. Ansel, S. Kamil, K. Veeramachaneni, J. Ragan-Kelley, J. Bosboom, U. O’Reilly, and S. Amarasinghe. Opentuner: An extensible framework for program autotuning. In Parallel Architecture and Compilation Techniques (PACT), 2014 23rd International Conference on, pages 303–315, 2014.

[2] D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.

[3] W. Jia, E. Garza, K. Shaw, and M. Martonosi. GPU performance and power tuning using regression trees. ACM Transactions on Architecture and Code Optimization (TACO), 12:13, 2015.

[4] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220:671-680, 1983.

[5] J. A. Nelder and R. Mead. A simplex method for function minimization. Computer Journal, 7:308–313, 1965.

[6] L. M. Rios and N. V. Sahinidis. Derivative-free optimization: A review of algorithms and comparison of software implementations. Journal of Global Optimization, 56:1247-1293, 2013.

[7] C. Ţăpuş, I. Chung, and J. Hollingsworth. Active harmony: Towards automated performance tuning. In Proceedings of the 2002 ACM/IEEE conference on Supercomputing, pages 1–11, 2002.