Scheduling Independent Tasks on Multi-cores with GPU Accelerators - Archive ouverte HAL Access content directly
Conference Papers Year : 2014

## Scheduling Independent Tasks on Multi-cores with GPU Accelerators

(1) , (2, 3, 1) , (2, 3) , (2, 4, 3)
1
2
3
4
Grégory Mounié
Denis Trystram

#### 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.

### Dates and versions

hal-00921357 , version 1 (10-11-2014)

### Identifiers

• HAL Id : hal-00921357 , version 1
• DOI :

### Cite

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⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

266 View