  Finding optimal parameter configurations for tunable GPU kernels is a
non-trivial exercise for large search spaces, even when automated. This poses
an optimization task on a non-convex search space, using an expensive to
evaluate function with unknown derivative. These characteristics make a good
candidate for Bayesian Optimization, which has not been applied to this problem
before. However, the application of Bayesian Optimization to this problem is
challenging. We demonstrate how to deal with the rough, discrete, constrained
search spaces, containing invalid configurations. We introduce a novel
contextual variance exploration factor, as well as new acquisition functions
with improved scalability, combined with an informed acquisition function
selection mechanism. By comparing the performance of our Bayesian Optimization
implementation on various test cases to the existing search strategies in
Kernel Tuner, as well as other Bayesian Optimization implementations, we
demonstrate that our search strategies generalize well and consistently
outperform other search strategies by a wide margin.
