MONNA Florence

Doutor em PhD
Equipe : RO
Data de partida : 28/02/2015
https://lip6.fr/Florence.Monna

Direção de pesquisa : Safia KEDAD-SIDHOUM

Scheduling for new computing platforms with GPUs

More and more computers use hybrid architectures combining multi-core processors (CPUs) and hardware accelerators like GPUs (Graphics Processing Units). These hybrid parallel platforms require new scheduling strategies. This work is devoted to a characterization of this new type of scheduling problems. The most studied objective in this work is the minimization of the makespan, which is a crucial problem for reaching the potential of new platforms in High Performance Computing. The core problem studied in this work is scheduling efficiently n independent sequential tasks with m CPUs and k GPUs, where each task of the application can be processed either on a CPU or on a GPU, with minimum makespan. This problem is NP-hard, therefore we propose approximation algorithms with performance ratios ranging from 2 to (2q+1)/(2q)+1/(2qk), q>0, and corresponding polynomial time complexities. The proposed solving method is the first general purpose algorithm for scheduling on hybrid machines with a theoretical performance guarantee that can be used for practical purposes. Some variants of the core problem are studied: a special case where all the tasks are accelerated when assigned to a GPU, with a 3/2-approximation algorithm, a case where preemptions are allowed on CPUs, the same problem with malleable tasks, with an algorithm with a ratio of 3/2. Finally, we studied the problem with dependent tasks, providing a 6-approximation algorithm. Experiments based on realistic benchmarks have been conducted. Some algorithms have been integrated into the scheduler of the xKaapi runtime system for linear algebra kernels, and compared to the state-of-the-art algorithm HEFT.

Defesas : 25/11/2014

Membros da banca :

CERIN Chrsitophe (LIPN, Université Paris 13) [Rapporteur]
SAKELLARIOU Rizos (Université de Manchester) [Rapporteur]
BLAZEWICZ Jacek (Université de Technologie de Poznan, Pologne)
KEDAD-SIDHOUM Safia (LIP6, UPMC)
MOUNIE Grégory (LIG Université de Grenoble)
MUNIER Alix (LIP6, UPMC)
THIBAULT Samuel (INRIA, Université de Bordeaux)
TRYSTRAM Denis (ENSIMAG, Université de Grenoble)

Data de partida : 28/02/2015

Publicações 2013-2018

Mentions légales
Mapa do site