Algorithms for Preemptive Co-scheduling of Kernels on GPUs - Archive ouverte HAL Access content directly
Conference Papers Year :

Algorithms for Preemptive Co-scheduling of Kernels on GPUs


Modern GPUs allow concurrent kernel execution and preemption to improve hardware utilization and responsiveness. Currently, the decision on the simultaneous execution of kernels is performed by the hardware, which can lead to unreasonable use of resources. In this work, we tackle the problem of co-scheduling for GPUs in high competition scenarios. We propose a novel graphbased preemptive co-scheduling algorithm, with the focus on reducing the number of preemptions. We show that the optimal preemptive makespan can be computed by solving a Linear Program in polynomial time. Based on this solution we propose graph theoretical model and an algorithm to build preemptive schedules which minimizes the number of preemptions. We show, however, that finding the minimal amount of preemptions among all preemptive solutions of optimal makespan is a NP-hard problem. We performed experiments on real-world GPU applications and our approach can achieve optimal makespan by preempting 6 to 9% of the tasks.
Fichier principal
Vignette du fichier
ProblemStatement.submitted.pdf (334.1 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03148711 , version 1 (22-02-2021)


  • HAL Id : hal-03148711 , version 1


Lionel Eyraud-Dubois, Cristiana Bentes. Algorithms for Preemptive Co-scheduling of Kernels on GPUs. HiPC 2020 : 27th IEEE International Conference on High Performance Computing, Data, and Analytics, Dec 2020, Pune / Virtual, India. ⟨hal-03148711⟩
50 View
129 Download


Gmail Facebook Twitter LinkedIn More