  The prohibitive expense of automatic performance tuning at scale has largely
limited the use of autotuning to libraries for shared-memory and GPU
architectures. We introduce a framework for approximate autotuning that
achieves a desired confidence in each algorithm configuration's performance by
constructing confidence intervals to describe the performance of individual
kernels (subroutines of benchmarked programs). Once a kernel's performance is
deemed sufficiently predictable for a set of inputs, subsequent invocations are
avoided and replaced with a predictive model of the execution time. We then
leverage online execution path analysis to coordinate selective kernel
execution and propagate each kernel's statistical profile. This strategy is
effective in the presence of frequently-recurring computation and communication
kernels, which is characteristic to algorithms in numerical linear algebra. We
encapsulate this framework as part of a new profiling tool, Critter, that
automates kernel execution decisions and propagates statistical profiles along
critical paths of execution. We evaluate performance prediction accuracy
obtained by our selective execution methods using state-of-the-art
distributed-memory implementations of Cholesky and QR factorization on
Stampede2, and demonstrate speed-ups of up to 7.1x with 98% prediction
accuracy.
