Scheduling Independent Tasks on Multi-cores with GPU Accelerators

Abstract : More and more computers use hybrid architectures combin-ing multi-core processors and hardware accelerators like GPUs (Graphics Processing Units). We present in this paper a new method for scheduling efficiently parallel applications with $m$ CPUs and $k$ GPUs, where each task of the application can be processed either on a core (CPU) or on a GPU. The objective is to minimize the makespan. The corresponding scheduling problem is NP-hard, we propose an efficient approximation algorithm which achieves an approximation ratio of $\frac{4}{3} + \frac{1}{3k}$ . We first detail and analyze the method, based on a dual approximation scheme, that uses a dynamic programming scheme to balance evenly the load between the heterogeneous resources. Finally, we run some simulations based on realistic benchmarks and compare the solution obtained by a relaxed version of this method to the one provided by a classical greedy algorithm and to lower bounds on the value of the optimal makespan.
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00921357
Contributor : Grégory Mounié <>
Submitted on : Monday, November 10, 2014 - 11:56:18 AM
Last modification on : Wednesday, May 15, 2019 - 3:40:43 AM
Long-term archiving on : Wednesday, February 11, 2015 - 3:29:18 PM

File

4tiers.pdf
Files produced by the author(s)

Identifiers

Citation

Safia Kedad-Sidhoum, Florence Monna, Grégory Mounié, Denis Trystram. Scheduling Independent Tasks on Multi-cores with GPU Accelerators. HeteroPar 2013 - 11th International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Platforms, Aug 2013, Aachen, Germany. pp.228-237, ⟨10.1007/978-3-642-54420-0_23⟩. ⟨hal-00921357⟩

Share

Metrics

Record views

564

Files downloads

429