Direction de recherche : Evripidis BAMPIS Co-encadrement : MILIS Ioannis
Problèmes algorithmiques dans les systèmes informatiques sous contraintes d'énergie
Cette thèse se focalise sur des algorithmes efficaces en énergie pour des problèmes d’ordonnancement de tâches sur des processeurs pouvant varier la vitesse d’exécution ainsi que sur des processeurs fonctionnant sous un mécanisme de réchauffement-refroidissement, où pour un budget d’énergie donné ou un seuil thermique, l’objectif consiste à optimiser un critère de Qualité de Service. Une partie de notre recherche concerne des problèmes d’ordonnancement de tâches apparaissant dans des environnements de traitement de grandes données. Dans ce contexte, nous nous focalisons sur le paradigme MapReduce en considérant des problèmes d’ordonnancement efficaces en énergie sur un ensemble de processeurs, ainsi que pour la version classique. Premièrement, nous proposons des résultats de complexité, des algorithmes optimaux et approchés pour différentes variantes du problème de la minimisation du retard maximal d’un ensemble de tâches sur un processeur pouvant varier la vitesse d’exécution. Ensuite, nous considérons le problème d’ordonnancement MapReduce dans les versions énergétique et classique sur des processeurs non-reliés où le but est de minimiser le temps d’achèvement pondéré. Nous étudions deux cas spéciaux et les généralisations de ces deux problèmes en proposant des algorithmes d’approximation constante. Enfin, nous étudions le problème d’ordonnancement dans lequel la température du processeur est en-dessous un seuil donné où chaque tâche contribue au réchauffement et le but est de maximiser le nombre de tâches exécutées. Nous considérons le cas où les tâches ont des durées unitaires et ayant la même date d’échéance et nous étudions le rapport d'approximation de ce problème.
Soutenance : 12/12/2014 - 14h30 - Site Jussieu 24-25/405 Membres du jury : Stavros Kolliopoulos, University of Athens [Rapporteur]
Monaldo Mastrolilli, Rapporteur, IDSIA, Lugano [Rapporteur]
Evripidis Bampis, Université Pierre et Marie Curie
Christoph Dürr, CNRS, Université Pierre et Marie Curie
Evangelos Markakis, Athens University of Economics and Business
Ioannis Milis, Athens University of Economics and Business
Denis Trystram, Grenoble INP
Publications 2012-2016
2016
E. Bampis, D. Letsios, I. Milis, G. Zois : “Speed Scaling for Maximum Lateness”, Theory of Computing Systems, vol. 58 (2), pp. 304-321, (Springer Verlag) (2016)
E. Bampis, V. Chau, D. Letsios, G. Lucarelli, I. Milis, G. Zois : “Energy efficient scheduling of MapReduce jobs.”, 20th International Conference on Parallel Processing (Euro-Par 2014), vol. 8632, Lecture Notes in Computer Science, Porto, Portugal, pp. 198-209, (Springer) (2014)
Ch. Dürr, I. Milis, J. Robert, G. Zois : “Approximating the Throughput by Coolest First Scheduling”, WAOA 2012 - 10th International Workshop on Approximation and Online Algorithms, Ljubljana, Slovenia, pp. 187-200, (Springer) (2012)
E. Bampis, D. Letsios, I. Milis, G. Zois : “Speed scaling for maximum lateness”, 18th Annual International Computing and Combinatorics Conference (COCOON 2012), vol. 7434, Lecture Notes in Computer Science, Sydney, NSW, Australia, pp. 25-36, (Springer) (2012)
