ZOIS Georgios
Supervision : Evripidis BAMPIS
Co-supervision : MILIS Ioannis
Algorithmic problems in power management of computing systems
This thesis is focused on energy-efficient algorithms for job scheduling problems on speed-scalable processors, as well as on processors operating under a thermal and cooling mechanism, where, for a given budget of energy or a thermal threshold, the goal is to optimize a Quality of Service criterion. A part of our research concerns scheduling problems arising in large-data processing environments. In this context, we focus on the MapReduce paradigm and we consider problems of energy-efficient scheduling on multiple speed-scalable processors as well as classical scheduling on a set of unrelated processors.
First, we propose complexity results, optimal and constant competitive algorithms for different energy-aware variants of the problem of minimizing the maximum lateness of a set of jobs on a single speed-scalable processor. Then, we consider energy-aware MapReduce scheduling as well as classical MapReduce scheduling (where energy is not our concern) on unrelated processors, where the goal is to minimize the total weighted completion time of a set of MapReduce jobs. We study special cases and generalizations of both problems and propose constant approximation algorithms. Finally, we study temperature-aware scheduling on a single processor that operates under a strict thermal threshold, where each job has its own heat contribution and the goal is to maximize the schedule's throughput. We consider the case of unit-length jobs with a common deadline and we study the approximability of the problem.
Defence : 12/12/2014
Jury members :
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
2012-2016 Publications
-
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 - 14th 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”, thesis, defence 12/12/2014, supervision Bampis, Evripidis, co-supervision : Milis, Ioannis (2014)
- 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)
-
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”, 18th Annual International Computing and Combinatorics Conference (COCOON 2012), vol. 7434, Lecture Notes in Computer Science, Sydney, NSW, Australia, pp. 25-36 (2012)