A methodology for comparing optimization algorithms for auto-tuning

Future Generation Computer Systems, vol. 159, pp. 489–504

Abstract

Adapting applications to optimally utilize available hardware is no mean feat: the plethora of choices for optimization techniques are infeasible to maximize manually. To this end, auto-tuning frameworks are used to automate this task, which in turn use optimization algorithms to efficiently search the vast searchspaces. However, there is a lack of comparability in studies presenting advances in auto-tuning frameworks and the optimization algorithms incorporated. As each publication varies in the way experiments are conducted, metrics used, and results reported, comparing the performance of optimization algorithms among publications is infeasible. The auto-tuning community identified this as a key challenge at the 2022 Lorentz Center workshop on auto-tuning. The examination of the current state of the practice in this paper further underlines this. We propose a community-driven methodology composed of four steps regarding experimental setup, tuning budget, dealing with stochasticity, and quantifying performance. This methodology builds upon similar methodologies in other fields while taking into account the constraints and specific characteristics of the auto-tuning field, resulting in novel techniques. The methodology is demonstrated in a simple case study that compares the performance of several optimization algorithms used to auto-tune CUDA kernels on a set of modern GPUs. We provide a software tool to make the application of the methodology easy for authors, and simplifies reproducibility of results.

Authors 6

1. Floris-Jan Willemsen corresponding Aachen

   Leiden University · Netherlands eScience Center

   Affiliation as printed

   Leiden University, Niels Bohrweg 1, 2333 CA, Leiden, The Netherlands

   The Netherlands eScience Center, Science Park 402, 1098 XH, Amsterdam, The Netherlands

2. Richard Schoonhoven

   Centrum Wiskunde & Informatica

   Affiliation as printed

   Centrum Wiskunde & Informatica, Science Park 123, 1098 XG, Amsterdam, The Netherlands

3. Jiří Filipovič

   Masaryk University

   Affiliation as printed

   Institute of Computer Science, Masaryk University, Sumavska 416/15, 602 00, Brno, Czechia

4. Jacob O. Tørring

   Norwegian University of Science and Technology

   Affiliation as printed

   Norwegian University of Science and Technology, Høgskoleringen 1, 7034, Trondheim, Norway

5. Rob V. van Nieuwpoort Aachen

   Leiden University

   Affiliation as printed

   Leiden University, Niels Bohrweg 1, 2333 CA, Leiden, The Netherlands

6. Ben van Werkhoven Aachen

   Leiden University · Netherlands eScience Center

   Affiliation as printed

   Leiden University, Niels Bohrweg 1, 2333 CA, Leiden, The Netherlands

   The Netherlands eScience Center, Science Park 402, 1098 XH, Amsterdam, The Netherlands