Online-Autotuning in the Presence of Algorithmic Choice

In this paper we explore the problem of autotuning the choice of algorithm. For a given task, there may be multiple algorithms available, each of which may contain its own set of tunable parameters and may provide optimal performance under different sets of inputs. Algorithmic choice is a type of tuning parameter which has not been well studied in the history of autotuning. To close this gap, we examine established autotuning techniques with regard to their ability of handling these parameters. We discuss the inadequacy of the state-of-the-art autotuning toolbox in manipulating algorithmic choice parameters and introduce four strategies to tackle this task. We evaluate our strategies in two case studies of online-autotuning scenarios, both with and without additional, numeric tuning parameters. The strategies are able to determine the optimal algorithm, and can even interoperate with the autotuning of the additional parameters.