Athens University Economics and Business (AUEB)
Algorithmic problems in power management of computing systems
Abstract
dc:descriptionThis work is focused on energy-efficient algorithms for job schedulingproblems on speed-scalable processors, as well as on processors operatingunder a thermal and cooling mechanism, where, for a given budget of energyor a thermal threshold, the goal is to optimize a Quality of Servicecriterion. A part of our research concerns scheduling problems arising inlarge-data processing environments. In this context, we focus on theMapReduce paradigm and we consider problems of energy-efficient schedulingon multiple speed-scalable processors as well as classical scheduling on aset of unrelated processors.First, we propose complexity results, optimal and constant competitivealgorithms for different energy-aware variants of the problem ofminimizing the maximum lateness of a set of jobs on a singlespeed-scalable processor. Then, we consider energy-aware MapReducescheduling as well as classical MapReduce scheduling (where energy is notour concern) on unrelated processors, where the goal is to minimize thetotal weighted completion time of a set of MapReduce jobs. We studyspecial cases and generalizations of both problems and propose constantapproximation algorithms. Finally, we study temperature-aware schedulingon a single processor that operates under a strict thermal threshold,where each job has its own heat contribution and the goal is to maximizethe schedule's throughput. We consider the case of unit-length jobs with acommon deadline and we study the approximability of the problem.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2014
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Zois, Georgios
- Ζώης, Γεώργιος
Subjects
dc:subject × 20- Χρονοδρομολόγηση
- Προσεγγιστικοί αλγόριθμοι
- Δυναμική κλιμακωση της ταχύτητας
- Θερμικό κατώφλι
- Ενεργειακή αποδοτικότητα
- Διαχείρηση θερμοκρασίας
- MapReduce χρονοδομολόγηση
- Άμεσοι αλγόριθμοι
- Scheduling
- Approximation algorithms
- Speed scaling
- Thermal threshold
- Energy efficiency
- Temperature management
- MapReduce scheduling
- Online algorithms
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/35876