Preemptive Thread Block Scheduling with Online Structural Runtime Prediction for Concurrent GPGPU Kernels

Recent NVIDIA Graphics Processing Units (GPUs) can ex-ecute multiple kernels concurrently. On these GPUs, the thread block scheduler (TBS) currently uses the FIFO pol-icy to schedule thread blocks of concurrent kernels. We show that the FIFO policy leaves performance to chance, resulting in significant loss of performance and fairness. To improve performance and fairness, we propose use of the preemptive Shortest Remaining Time First (SRTF) policy instead. Although SRTF requires an estimate of runtime of GPU kernels, we show that such an estimate of the run-time can be easily obtained using online profiling and ex-ploiting a simple observation on GPU kernels ’ grid struc-ture. Specifically, we propose a novel Structural Runtime Predictor. Using a simple Staircase model of GPU kernel execution, we show that the runtime of a kernel can be pre-dicted by profiling only the first few thread blocks. We eval-uate an online predictor based on this model on benchmarks from ERCBench, and find that it can estimate the actual runtime reasonably well after the execution of only a sin-gle thread block. Next, we design a thread block scheduler that is both concurrent kernel-aware and uses this predictor. We implement the Shortest Remaining Time First (SRTF) policy and evaluate it on two-program workloads from ER-CBench. SRTF improves STP by 1.18x and ANTT by 2.25x over FIFO. When compared to MPMax, a state-of-the-art resource allocation policy for concurrent kernels, SRTF im-proves STP by 1.16x and ANTT by 1.3x. To improve fair-ness, we also propose SRTF/Adaptive which controls re-source usage of concurrently executing kernels to maximize fairness. SRTF/Adaptive improves STP by 1.12x, ANTT by 2.23x and Fairness by 2.95x compared to FIFO. Overall, our implementation of SRTF achieves system throughput to within 12.64 % of Shortest Job First (SJF, an oracle optimal scheduling policy), bridging 49 % of the gap between FIFO and SJF