GPUs are widely used to accelerate scientific computing for high performance, with OpenMP providing readily available directive-based programming support for developers to offload computations. Unlike CUDA support, OpenMP provides default offloading configurations. However, for optimal performance, a developer must be able to select the best relevant offloading configurations to meet performance expectations (e.g. how many threads and blocks) for each kernel. Finding the best launch parameter values using auto-tuning and/or machine learning optimizations can be time-consuming and resource intensive. This paper seeks to address this challenge by developing a machine learning surrogate model that predicts relative kernel performance at minimal costs. The shape of the relative run-time execution distribution of the application has fundamental implications for performance prediction, leading us to implement a novel two-stage approach. Given an application’s compile-time information, our novel two-stage classifier predicts whether the launch configuration yields optimal or suboptimal relative performance. When applied to real-world benchmarks, we achieved \(\approx 91\%\) prediction accuracy classifying unseen instances and \(\approx 70\%\) with unseen benchmark sets.