Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Independent tasks on 2 resources with co-scheduling effects

Abstract : Concurrent kernel execution is a relatively new feature in modern GPUs, which was designed to improve hardware utilization and the overall system throughput. However, the decision on the simultaneous execution of tasks is performed by the hardware with a leftover policy, that assigns as many resources as possible for one task and then assigns the remaining resources to the next task. This can lead to unreasonable use of resources. In this work, we tackle the problem of co-scheduling for GPUs with and without preemption, with the focus on determining the kernels submission order to reduce the number of preemptions and the kernels makespan, respectively. We propose a graph-based theoretical model to build preemptive and non-preemptive schedules. We show that the optimal preemptive makespan can be computed by solving a Linear Program in polynomial time, and we propose an algorithm based on this solution which minimizes the number of preemptions. We also propose an algorithm that transforms a preemptive solution of optimal makespan into a non-preemptive solution with the smallest possible preemption overhead. We show, however, that finding the minimal amount of preemptions among all preemptive solutions of optimal makespan is a NP-hard problem, and computing the optimal non-preemptive schedule is also NP-hard. In addition, we study the non-preemptive problem, without searching first for a good preemptive solution, and present a Mixed Integer Linear Program solution to this problem. We performed experiments on real-world GPU applications and our approach can achieve optimal makespan by preempting 6 to 9% of the tasks. Our non-preemptive approach, on the other side, obtains makespan within 2.5% of the optimal preemptive schedules, while previous approaches exceed the preemptive makespan by 5 to 12%.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/hal-02431897
Contributor : Lionel Eyraud-Dubois <>
Submitted on : Wednesday, January 8, 2020 - 11:21:23 AM
Last modification on : Saturday, January 11, 2020 - 1:41:08 AM
Long-term archiving on: : Thursday, April 9, 2020 - 3:12:30 PM

File

ProblemStatement.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02431897, version 1

Collections

Citation

Lionel Eyraud-Dubois, Cristiana Bentes. Independent tasks on 2 resources with co-scheduling effects. 2020. ⟨hal-02431897⟩

Share

Metrics

Record views

81

Files downloads

146