Skip to Main content Skip to Navigation
Conference papers

Algorithms for Preemptive Co-scheduling of Kernels on GPUs

Abstract : 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.
Complete list of metadata

https://hal.inria.fr/hal-03148711
Contributor : Lionel Eyraud-Dubois Connect in order to contact the contributor
Submitted on : Monday, February 22, 2021 - 2:35:52 PM
Last modification on : Friday, January 21, 2022 - 3:10:44 AM
Long-term archiving on: : Sunday, May 23, 2021 - 6:47:34 PM

File

ProblemStatement.submitted.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03148711, version 1

Collections

Citation

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⟩

Share

Metrics

Les métriques sont temporairement indisponibles