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.

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)
• 2015
  • D. Fotakis, I. Milis, E. Zampetakis, G. Zois : “Scheduling MapReduce Jobs and Data Shuffle on Unrelated Processors”, SEA 2015 - 14^th International Symposium on Experimental Algorithms, Paris, France, pp. 137-150, (Springer) (2015)
• 2014
  • G. Zois : “Problèmes algorithmiques dans les systèmes informatiques sous contraintes d’énergie”, soutenance de thèse, soutenance 12/12/2014, direction de recherche Bampis, Evripidis, co-encadrement : Milis, Ioannis (2014)
  • E. Bampis, V. Chau, D. Letsios, G. Lucarelli, I. Milis, G. Zois : “Energy Efficient Scheduling of MapReduce Jobs”, 20^th International Conference on Parallel Processing (Euro-Par 2014), vol. 8632, Lecture Notes in Computer Science, Porto, Portugal, pp. 198-209, (Springer) (2014)
• 2012
  • Ch. Dürr, I. Milis, J. Robert, G. Zois : “Approximating the Throughput by Coolest First Scheduling”, Approximation and Online Algorithms, Ljubljana, Slovenia, pp. 187-200, (Springer) (2012)
  • E. Bampis, D. Letsios, Ioannis Z. Milis, G. Zois : “Speed scaling for maximum lateness”, 18^th Annual International Computing and Combinatorics Conference (COCOON 2012), vol. 7434, Lecture Notes in Computer Science, Sydney, NSW, Australia, pp. 25-36 (2012)