Autotuning Algorithmic Choice for Input Sensitivity

Empirical autotuning is increasingly being used in many do-mains to achieve optimized performance in a variety of dif-ferent execution environments. A daunting challenge faced by such autotuners is input sensitivity, where the best auto-tuned configuration may vary with different input sets. In this paper, we propose a two level solution that: first, clusters to find input sets that are similar in input feature space; then, uses an evolutionary autotuner to build an opti-mized program for each of these clusters; and, finally, builds an adaptive overhead aware classifier which assigns each in-put to a specific input optimized program. Our approach ad-dresses the complex trade-off between using expensive fea-tures, to accurately characterize an input, and cheaper fea-tures, which can be computed with less overhead. Experi-mental results show that by adapting to different inputs one can obtain up to a 3x speedup over using a single configura-tion for all inputs. 1