Adaptive Runtime Selection for GPU

It is often hard to predict the performance of a statically generated code. Hardware availability, hardware specification and problem size may change from one execution context to another. The main contribution of this work is an entirely automatic method aiming to predict execution times of semantically equivalent versions of affine loop nests on GPUs, then, to run the best performing one on GPU or CPU. To make accurate predictions, our framework relies on three consecutive stages: a static code generation, an offline profiling and an online prediction. Different versions are statically generated by PPCG, a source-to-source polyhedral compiler, able to generate CUDA code from static control loops written in C. The code versions differ by their block sizes, tiling and parallel schedule. The profiling code carries out the required measurements on the target machine: throughput between host and device memory, and execution time of the kernels with various parameters. At runtime, we rely on those results to calculate a predicted execution time on GPU. This is followed by a "fastest wins" algorithm, that runs instances of the target code concurrently on CPU and GPU, the first completed kills the other one. We validate this proposal on the polyhedral benchmark suite, showing that the predictions are accurate and that the runtime selection is effective on two different architectures.