Βιβλιοθήκη ΟΠΑ - Ψηφιακό Αποθετήριο

ΠΥΞΙΔΑ Ιδρυματικό Αποθετήριο
και Ψηφιακή Βιβλιοθήκη

Όνομα χρήστη
Κωδικός πρόσβασης

Συλλογές :	Ιδρυματικό Αποθετήριο ΟΠΑ / AUEB Institutional Repository Σχολή Επιστημών και Τεχνολογίας της Πληροφορίας / School of Informatics Τμήμα Πληροφορικής / Department of Informatics Διδακτορικές διατριβές / PhD Theses

Τίτλος :	Algorithmic problems in power management of computing systems

Δημιουργός :	Zois, Georgios

Συντελεστής :	Bampis, Evripidis (Επιβλέπων καθηγητής) Milis, Ioannis (Επιβλέπων καθηγητής) Athens University of Economics and Business, Department of Informatics (Degree granting institution) Universite Pierre et Marie Curie (Degree granting institution) Ecole doctorale Informatique, Telecommunications et Electronique, Laboratoire d' Informatique de Paris 6, Decision, Systemes Intelligents et Recherche Operationnelle (Degree granting institution)

Συντελεστής :

Bampis, Evripidis (Επιβλέπων καθηγητής)
Milis, Ioannis (Επιβλέπων καθηγητής)
Athens University of Economics and Business, Department of Informatics (Degree granting institution)
Universite Pierre et Marie Curie (Degree granting institution)
Ecole doctorale Informatique, Telecommunications et Electronique, Laboratoire d' Informatique de Paris 6, Decision, Systemes Intelligents et Recherche Operationnelle (Degree granting institution)

Τύπος :	Text

Φυσική περιγραφή :	123p.

Γλώσσα :	en

Περίληψη :	This thesis is focused on energy-efficient algorithms for job scheduling problems on speed-scalableprocessors, 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 study the minimization of the maximum lateness of a set of jobs on a single speed-scalable processor. We consider two variants of the problem: a budget variant, where we aim in minimizing maximum lateness for a given budget of energy and an aggregated variant, where we want to minimize a linear combination of maximum lateness and energy. We propose optimal algorithms for both variants in the non-preemptive case where jobs have common release dates. Our algorithms are based on a number of structural properties that can be obtained after applying the KKT (Karush-Kuhn-Tucker) conditions on a convex programming formulation of the problem. In the presence of arbitrary release dates, we prove that both variants become strongly NP-hard. Moreover, for the budget variant we show that it does not admit any O(1)-competitive deterministic algorithm, while for the aggregated variant we propose a 2-competitive online algorithm. Then, we study energy-aware MapReduce scheduling where the goal is to minimize the total weighted completion time of a set of MapReduce jobs under a given budget of energy. We first propose a convex programming relaxation of the problem, when the execution orderof jobs is known. We combine the solution of this relaxation with two natural list scheduling policies (First Come First Served and Highest Density First) and compare experimentally their effectiveness. Although their performance for random instances is fairly good, we prove that there are instances for which it is very far from the optimal. Next, we propose a linear programming approach which is based on an interval indexed LP-relaxation of the problem that incorporates a discretization of the possible speed values. Our algorithm transforms an optimal solution to this LP into a feasible solution for the problem by list scheduling in the order of tasks' _-points, where _ 2 (0; 1). We obtain a constant factorapproximation algorithm for the total weighted completion time of a set of MapReduce jobs using energy augmentation. In the context of classical MapReduce scheduling (where energy is not our concern) we also study the scheduling of a set of MapReduce jobs on unrelated processors with the goal of minimizing their total weighted completion time. We propose a 54-approximation algorithm which computes a feasible schedule by merging two individual schedules (of either Map or Reduce tasks) into a single schedule. Moreover, we consider the significant part of data shuffle in MapReduce applications and extend our model to capture the shuffle phase. We manage to keep the same ratio of 54 when the Shuffle tasks are scheduled on the same processors with the corresponding Reduce tasks, which becomes81 when the Shuffle and the Reduce tasks are scheduled on different processors. Finally, we focus on 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 revisit the offline CoolestFirst scheduling, i.e., the job with the smaller heat contribution is scheduled first. We study the approximability of Algorithm CoolestFirst and propose two different rounding schemes that yield lower bounds on its approximation factor. The first is based on a partition of the schedule according to theheat contributions of the jobs, while the second is based on a linear programming approach. The latter, which is actually more refined, yields a lower bound of at least 0.72.i Cette these se focalise sur des algorithmes efficaces en energie pour des problemes d'ordonnancement de taches sur des processeurs de variation de vitesse ainsi que sur des processeurs fonctionnant sous un mecanisme de rechauffement-refroidissement, ou, pour un budget d' energie donne ou un seuil thermique, l'objectif consiste a optimiser un critere de Qualite de Service. Une partie de notre recherche concerne des problemes d'ordonnancement de taches apparaissant dans des environnements de traitement de grandes donnees. Dans ce contexte, nous nous focalisons sur le paradigme MapReduce et nous considerons des problemes d'ordonnancement efficaces en energie sur un ensemble de processeurs pouvant varier leur vitesse, ainsi que des problemes d'ordonnancements classiques sur un ensemble des processeurs non-relies. Premierement, nous etudions la minimisation du retard maximal d'un ensemble de taches sur un seul processeur de variation de vitesse. Nous considerons deux variantes de ce probleme: la variante budgetaire, ou nous voulons minimiser le retard maximal etant donne un budget d'energie et la variante agregee, ou nous voulons minimiser une combinaison lineaire du retard maximal et de l'energie maximale. Nous proposons des algorithmes optimaux pour ces deux variantes dans le cas non-preemptif ou les taches ont des dates de disponibilites communes. Nos algorithmes sont bases sur un nombre de propri et es structurales qui peuvent etre obtenues en appliquant les conditions KKT (Karush- Kuhn-Tucker) sur une formulation de programmation convexe du probleme. Nous prouvons que les deux variantes deviennent fortement NP-difficile lorsque les taches ont des dates de disponibilites arbitraires. En outre, nous montrons que la variante budgetaire n'admet aucun algorithme deterministe O (1)-competitif, alors que pour la variante agregee nous proposons un algorithme en ligne 2-competitif. Par la suite, nous etudions l'ordonnancement MapReduce ou le but est de minimiser le temps d'achevement pondere d'un ensemble de taches MapReduce etant donne un budget d'energie: d'abord, nous proposons un programme convexe relache de ce probleme, ou l'ordre d'execution des travaux est connu. Nous combinons la solution de ce relachement avec deux politiques naturelles de listes (First Come First Served et Highest Density First) et nous comparons leur ecacite experimentalement. Malgre leur bonne performance pour le cas aleatoire, nous prouvons qu'il y a des cas pour lesquels elles sont loin de l'optimum. Deuxiemement, nous proposons une approche d'ordonnancement lineaire qui est basee sur un intervalle indexe LP-relachement du probleme qui incorpore une discretisation des va leurs de vitesse possibles. Notre algorithme transforme une solution optimale de ce programme lineaire en une solution realisable du probleme en ordonnancant les taches dans l'ordre deni par les -points des taches, ou a e (0, 1). Nous obtenons un algorithme d'approximation de facteur constant pour le temps de completude pondere total d'un ensemble de taches MapReduce en utilisant une augmentation d'energie. Dans le contexte d'ordonnancement MapReduce classique (ou l'energie n'est pas prise en compte) nous etudions aussi l'ordonnancement d'un ensemble des travaux MapReduce sur des processeurs non-relies en minimisant la somme des temps de completude pondere. Nous proposons un algorithme 54- approche qui calcule un ordonnancement realisable en fusionnant deux ordonnancements individuels (de taches Map ou Reduce) dans un ordonnancement unique. En outre, nous considerons la partie principale de data shuffle dans des applications shuffle phase. Nous arrivons a garder le meme rapport d'approximation de 54 lorsque les taches Shuffle sont ordonnancees sur les memes processeurs avec les taches correspondantes, et devient 81 quand les taches Shuffle et Reduce sont ordonnancees sur des processeurs differents. Enfin, nous nous focalisons sur l'ordonnancement sous contraintes thermiques sur un seul processeur fonctionnant en-dessous d'un seuil de temperature stricte ou chaque tache a sa propre contribution thermique et le but est de maximiser le nombre de tache executee. Nous considerons le cas ou les taches ont des durees unitaires ayant la meme date d'echeance et nous revisitons l'algorithme hors-ligne CoolestFirst, c'est-a-dire la tache ayant la contribution thermique la plus petite est ordonnancee en premier. Nous etudions l'approximabilite de l'Algorithme CoolestFirst et proposons deux differents schemas d'arrondis qui produisent des bornes maximales sur son facteur d'approximation. Le premier est base sur une partition de l'ordonnancement selon les contributions thermiques des taches, tandis que le second est base sur un programme lineaire. Celui-ci, qui est en effet plus raffine, produit une borne minimale d'au moins 0:72. Η εργασία αυτή επικεντρώνεται σε ενεργειακά αποδοτικούς αλγόριθμους για προβλήματα χρονοδρομολόγησης σε επεξεργαστές δυναμικής κλιμάκωσης της ταχύτητας, καθώς επίσης και σε επεξεργαστές οι οποίοι λειτουργούν κάτω από ένα μηχανισμό θέρμανσης και ψύξης, με στόχο την ελαχιστοποίηση ενός ποιοτικού κριτηρίου απόδοσης. Ένα σημαντικό μέρος της έρευνάς μας έχει ως πρωταρχικό κίνητρο τη χρονοδρομολόγηση σε περιβάλλοντα επεξεργασίας μεγάλου όγκου δεδομένων. Σε αυτό το πλαίσιο, επικεντρωνόμαστε στο πρότυπο MapReduce και μελετάμε προβλήματα ενεργειακά αποδοτικής χρονοδρομολόγησης σε πολλαπλούς επεξεργαστές κλιμακούμενης ταχύτητας, καθώς επίσης και τυπικά προβλήματα χρονοδρομολόγησης σε μη σχετιζόμενους επεξεργαστές. Αρχικά, προτείνουμε το πρόβλημα ελαχιστοποίησης της μέγιστης καθυστέρησης ενός συνόλου εργασιών σε μοναδικό επεξεργαστή κλιμακούμενης ταχύτητας. Μελετάμε δύο εκδοχές του προβλήματος: μια εκδοχή δεδομένου προϋπολογισμού, όπου ο στόχος είναι η ελαχιστοποίηση ενός γραμμικού συνδυασμού της μέγιστης καθυστέρησης και της ενέργειας που καταναλώνεται. Προτείνουμε βέλτιστους αλγόριθμους πολυωνυμικού χρόνου για τις δύο εκδοχές στην περίπτωση που οι εργασίες διαθέτουν κοινούς χρόνους αποδέσμευσης. Οι προτεινόμενοι αλγόριθμοι βασίζονται σε ένα σύνολο δομικών χαρακτηριστικών της βέλτιστης χρονοδρομολόγησης , τα οποία εξάγονται με την εφαρμογή των ΚΚΤ (Karush-Kuhn-Tucker) συνθηκών σε ένα κυρτό πρόγραμμα αντίστοιχο του προβλήματος μας. Στην περίπτωση που οι εργασίες διαθέτουν αυθαίρετους χρόνους αποδέσμευσης, αποδεικνύουμε ότι και οι δύο εκδοχές είναι strongly NP-hard. Επιπλέον, στην τελευταία περίπτωση, για την εκδοχή δεδομένου προϋπολογισμού δείχνουμε ότι δεν επιδέχεται ντετερμιστικό αλγόριθμο σταθερού λόγου ανταγωνισμού, ενώ για τη συγκεντρωτική εκδοχή προτείνουμε ένα 2-ανταγωνιστικό αλγόριθμο. Στη συνέχεια, μελετάμε προβλήματα MapReduce χρονοδρομολόγησης με επίγνωση της ενέργειας και στόχο την ελαχιστοποίηση του συνολικού βεβαρημένου χρόνου ολοκλήρωσης ενός συνόλου MapReduce εργασιών, δεδομένου ενός προϋπολογισμού ενέργειας. Αρχικά προτείνουμε τη διατύπωση ενός χαλαρωμένου κυρτού προγράμματος για το πρόβλημα, δεδομένης μίας διάταξης εκτέλεσης των εργασιών. Συνδυάζουμε τη λύση της κυρτής χαλάρωσης με δύο συνήθεις στρατηγικές χρονοδρομολόγησης (First Come First Served and Highest Density First) και συγκρίνουμε πειραματικά τις λύσεις τους. Μολονότι η απόδοση τους για τυχαία στιγμιότυπα είναι αρκετά καλή, όπως αποδεικνύουμε, υπάρχουν στιγμιότυπα για τα οποία αποκλίνει αρκετά από αυτή της βέλτιστης λύσης. Επομένως, προτείνουμε μία μεθόδευση γραμμικού προγραμματισμού, η οποία βασίζεται στη διατύπωση μια γραμμικής χαλάρωσης του προβλήματος μέσω διακριτοποίησης τόσο του χρονικού ορίζοντα καθώς επίσης και των πιθανών τιμών των ταχυτήτων εκτέλεσης. Ο προτεινόμενος αλγόριθμος μετασχηματίζει μία βέλτιστη λύση της γραμμικής χαλάρωσης σε μία εφικτή λύση του προβλήματος εκτελώντας τις εργασίες βάσει της διάταξης που υποδεικνύεται από τα a-points, a e (0,1) των εργασιών στη λύση του γραμμικού προγράμματος. Πετυχαίνουμε έναν αλγόριθμο σταθερής προσέγγισης για το πρόβλημα ελαχιστοποίησης του συνολικού βεβαρημένου χρόνου ολοκλήρωσης ενός συνόλου MapReduce εργασιών, ο οποίος χρησιμοποιεί προσαύξηση της ενέργειας. Στο πλάισιο της MapReduce χρονοδρομολόγησης, όταν η ενέργεια δεν αποτελεί στόχο, μελετάμε επίσης την πιο γενική περίπτωση χρονοδρομολόγησης ενός συνόλου MapReduce εργασιών σε μη σχετιζόμενους επεξεργαστές, με στόχο την ελαχιστοποίηση της συνολικής βεβαρημένης ολοκλήρωσής τους. Προτείνουμε έναν 54-προσεγγιστικό αλγόριθμο ο οποίος υπολογίζει μια εφικτή χρονοδρομολόγηση για το πρόβλημα, συνενώνοντας δύο ξεχωριστές χρονοδρομολογήσεις (για τις Map ή τις Reduce εργασίες) σε μία. Επιπλέον, επεκτείνουμε το μοντέλο μας ώστε να συμπεριλάβει μία επιπλέον σημαντική παράμετρο στις MapReduce εφαρμογές, αυτή του data shuffle. Επιτυγχάνουμε να διατηρήσουμε τον παράγοντα προσέγγισης ίσο με 54 στην περίπτωση που οι Shuffle εργασίες εκτελούνται στους ίδιους επεξεργαστές με τις Reduce εργασίες, ο οποίος γίνεται 84 στην περίπτωση που οι Shuffle και οι Reduce εργασίες εκτελούνται σε διαφορετικούς επεξεργαστές. Τέλος, επικεντρωνόμαστε σε προβλήματα χρονοδρομολόγησης με επίγνωση της θερμοκρασίας, σε ένα μοναδικό επεξεργαστή που λειτουργεί βάσει ενός αυστηρού θερμικού κατωφλίου, όπου κάθε εργασία έχει τη δική της θερμική συνεισφορά και ο στόχος είναι η μεγιστοποίηση του throughput της χρονοδρομολόγησης. Μελετάμε την περίπτωση όπου οι εργασίες είναι μοναδιαίου μήκους και έχουν μία κοινή προθεσμία και επανεξετάζουμε μια κλάση προβλημάτων όπου μια εργασία δεν εκτελείται εφόσον μία άλλη, μικρότερης θερμικής συνεισφοράς ή προθεσμίας, έχει αποδεσμευτεί και είναι διαθέσιμη και επικεντρωνόμαστε στη μεγιστοποίηση του throughput στην offline εκδοχή του προβλήματος, κάτω από την COOLESTFIRST χρονοδρομολόγηση. Αναλύουμε την προσεγγισιμότητα του αλγόριθμου COOLESTFIRST και προτείνουμε δύο διαφορετικά σχήματα στρογγυλοποίησης. Το πρώτο βασίζεται στη διαμέριση της χρονοδρομολόγησης σύμφωνα με τις θερμικές συνεισφορές εργασιών, ενώ το δεύτερο σε μία θεώρηση μέσω γραμμικού προγραμματισμού. Το δεύτερο σχήμα βελτιώνει το πρώτο και δίνει ένα κάτω φράγμα μεγαλύτερο ή ίσο του 0.72.

Περίληψη :

This thesis is focused on energy-efficient algorithms for job scheduling problems on speed-scalableprocessors, 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 study the minimization of the maximum lateness of a set of jobs on a single speed-scalable processor. We consider two variants of the problem: a budget variant, where we aim in minimizing maximum lateness for a given budget of energy and an aggregated variant, where we want to minimize a linear combination of maximum lateness and energy. We propose optimal algorithms for both variants in the non-preemptive case where jobs have common release dates. Our algorithms are based on a number of structural properties that can be obtained after applying the KKT (Karush-Kuhn-Tucker) conditions on a convex programming formulation of the problem. In the presence of arbitrary release dates, we prove that both variants become strongly NP-hard. Moreover, for the budget variant we show that it does not admit any O(1)-competitive deterministic algorithm, while for the aggregated variant we propose a 2-competitive online algorithm. Then, we study energy-aware MapReduce scheduling where the goal is to minimize the total weighted completion time of a set of MapReduce jobs under a given budget of energy. We first propose a convex programming relaxation of the problem, when the execution orderof jobs is known. We combine the solution of this relaxation with two natural list scheduling policies (First Come First Served and Highest Density First) and compare experimentally their effectiveness. Although their performance for random instances is fairly good, we prove that there are instances for which it is very far from the optimal. Next, we propose a linear programming approach which is based on an interval indexed LP-relaxation of the problem that incorporates a discretization of the possible speed values. Our algorithm transforms an optimal solution to this LP into a feasible solution for the problem by list scheduling in the order of tasks' _-points, where _ 2 (0; 1). We obtain a constant factorapproximation algorithm for the total weighted completion time of a set of MapReduce jobs using energy augmentation. In the context of classical MapReduce scheduling (where energy is not our concern) we also study the scheduling of a set of MapReduce jobs on unrelated processors with the goal of minimizing their total weighted completion time. We propose a 54-approximation algorithm which computes a feasible schedule by merging two individual schedules (of either Map or Reduce tasks) into a single schedule. Moreover, we consider the significant part of data shuffle in MapReduce applications and extend our model to capture the shuffle phase. We manage to keep the same ratio of 54 when the Shuffle tasks are scheduled on the same processors with the corresponding Reduce tasks, which becomes81 when the Shuffle and the Reduce tasks are scheduled on different processors. Finally, we focus on 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 revisit the offline CoolestFirst scheduling, i.e., the job with the smaller heat contribution is scheduled first. We study the approximability of Algorithm CoolestFirst and propose two different rounding schemes that yield lower bounds on its approximation factor. The first is based on a partition of the schedule according to theheat contributions of the jobs, while the second is based on a linear programming approach. The latter, which is actually more refined, yields a lower bound of at least 0.72.i
Cette these se focalise sur des algorithmes efficaces en energie pour des problemes d'ordonnancement de taches sur des processeurs de variation de vitesse ainsi que sur des processeurs fonctionnant sous un mecanisme de rechauffement-refroidissement, ou, pour un budget d' energie donne ou un seuil thermique, l'objectif consiste a optimiser un critere de Qualite de Service. Une partie de notre recherche concerne des problemes d'ordonnancement de taches apparaissant dans des environnements de traitement de grandes donnees. Dans ce contexte, nous nous focalisons sur le paradigme MapReduce et nous considerons des problemes d'ordonnancement efficaces en energie sur un ensemble de processeurs pouvant varier leur vitesse, ainsi que des problemes d'ordonnancements classiques sur un ensemble des processeurs non-relies. Premierement, nous etudions la minimisation du retard maximal d'un ensemble de taches sur un seul processeur de variation de vitesse. Nous considerons deux variantes de ce probleme: la variante budgetaire, ou nous voulons minimiser le retard maximal etant donne un budget d'energie et la variante agregee, ou nous voulons minimiser une combinaison lineaire du retard maximal et de l'energie maximale. Nous proposons des algorithmes optimaux pour ces deux variantes dans le cas non-preemptif ou les taches ont des dates de disponibilites communes. Nos algorithmes sont bases sur un nombre de propri et es structurales qui peuvent etre obtenues en appliquant les conditions KKT (Karush- Kuhn-Tucker) sur une formulation de programmation convexe du probleme. Nous prouvons que les deux variantes deviennent fortement NP-difficile lorsque les taches ont des dates de disponibilites arbitraires. En outre, nous montrons que la variante budgetaire n'admet aucun algorithme deterministe O (1)-competitif, alors que pour la variante agregee nous proposons un algorithme en ligne 2-competitif. Par la suite, nous etudions l'ordonnancement MapReduce ou le but est de minimiser le temps d'achevement pondere d'un ensemble de taches MapReduce etant donne un budget d'energie: d'abord, nous proposons un programme convexe relache de ce probleme, ou l'ordre d'execution des travaux est connu. Nous combinons la solution de ce relachement avec deux politiques naturelles de listes (First Come First Served et Highest Density First) et nous comparons leur ecacite experimentalement. Malgre leur bonne performance pour le cas aleatoire, nous prouvons qu'il y a des cas pour lesquels elles sont loin de l'optimum. Deuxiemement, nous proposons une approche d'ordonnancement lineaire qui est basee sur un intervalle indexe LP-relachement du probleme qui incorpore une discretisation des va leurs de vitesse possibles. Notre algorithme transforme une solution optimale de ce programme lineaire en une solution realisable du probleme en ordonnancant les taches dans l'ordre deni par les -points des taches, ou a e (0, 1). Nous obtenons un algorithme d'approximation de facteur constant pour le temps de completude pondere total d'un ensemble de taches MapReduce en utilisant une augmentation d'energie. Dans le contexte d'ordonnancement MapReduce classique (ou l'energie n'est pas prise en compte) nous etudions aussi l'ordonnancement d'un ensemble des travaux MapReduce sur des processeurs non-relies en minimisant la somme des temps de completude pondere. Nous proposons un algorithme 54- approche qui calcule un ordonnancement realisable en fusionnant deux ordonnancements individuels (de taches Map ou Reduce) dans un ordonnancement unique. En outre, nous considerons la partie principale de data shuffle dans des applications shuffle phase. Nous arrivons a garder le meme rapport d'approximation de 54 lorsque les taches Shuffle sont ordonnancees sur les memes processeurs avec les taches correspondantes, et devient 81 quand les taches Shuffle et Reduce sont ordonnancees sur des processeurs differents. Enfin, nous nous focalisons sur l'ordonnancement sous contraintes thermiques sur un seul processeur fonctionnant en-dessous d'un seuil de temperature stricte ou chaque tache a sa propre contribution thermique et le but est de maximiser le nombre de tache executee. Nous considerons le cas ou les taches ont des durees unitaires ayant la meme date d'echeance et nous revisitons l'algorithme hors-ligne CoolestFirst, c'est-a-dire la tache ayant la contribution thermique la plus petite est ordonnancee en premier. Nous etudions l'approximabilite de l'Algorithme CoolestFirst et proposons deux differents schemas d'arrondis qui produisent des bornes maximales sur son facteur d'approximation. Le premier est base sur une partition de l'ordonnancement selon les contributions thermiques des taches, tandis que le second est base sur un programme lineaire. Celui-ci, qui est en effet plus raffine, produit une borne minimale d'au moins 0:72.
Η εργασία αυτή επικεντρώνεται σε ενεργειακά αποδοτικούς αλγόριθμους για προβλήματα χρονοδρομολόγησης σε επεξεργαστές δυναμικής κλιμάκωσης της ταχύτητας, καθώς επίσης και σε επεξεργαστές οι οποίοι λειτουργούν κάτω από ένα μηχανισμό θέρμανσης και ψύξης, με στόχο την ελαχιστοποίηση ενός ποιοτικού κριτηρίου απόδοσης. Ένα σημαντικό μέρος της έρευνάς μας έχει ως πρωταρχικό κίνητρο τη χρονοδρομολόγηση σε περιβάλλοντα επεξεργασίας μεγάλου όγκου δεδομένων. Σε αυτό το πλαίσιο, επικεντρωνόμαστε στο πρότυπο MapReduce και μελετάμε προβλήματα ενεργειακά αποδοτικής χρονοδρομολόγησης σε πολλαπλούς επεξεργαστές κλιμακούμενης ταχύτητας, καθώς επίσης και τυπικά προβλήματα χρονοδρομολόγησης σε μη σχετιζόμενους επεξεργαστές. Αρχικά, προτείνουμε το πρόβλημα ελαχιστοποίησης της μέγιστης καθυστέρησης ενός συνόλου εργασιών σε μοναδικό επεξεργαστή κλιμακούμενης ταχύτητας. Μελετάμε δύο εκδοχές του προβλήματος: μια εκδοχή δεδομένου προϋπολογισμού, όπου ο στόχος είναι η ελαχιστοποίηση ενός γραμμικού συνδυασμού της μέγιστης καθυστέρησης και της ενέργειας που καταναλώνεται. Προτείνουμε βέλτιστους αλγόριθμους πολυωνυμικού χρόνου για τις δύο εκδοχές στην περίπτωση που οι εργασίες διαθέτουν κοινούς χρόνους αποδέσμευσης. Οι προτεινόμενοι αλγόριθμοι βασίζονται σε ένα σύνολο δομικών χαρακτηριστικών της βέλτιστης χρονοδρομολόγησης , τα οποία εξάγονται με την εφαρμογή των ΚΚΤ (Karush-Kuhn-Tucker) συνθηκών σε ένα κυρτό πρόγραμμα αντίστοιχο του προβλήματος μας. Στην περίπτωση που οι εργασίες διαθέτουν αυθαίρετους χρόνους αποδέσμευσης, αποδεικνύουμε ότι και οι δύο εκδοχές είναι strongly NP-hard. Επιπλέον, στην τελευταία περίπτωση, για την εκδοχή δεδομένου προϋπολογισμού δείχνουμε ότι δεν επιδέχεται ντετερμιστικό αλγόριθμο σταθερού λόγου ανταγωνισμού, ενώ για τη συγκεντρωτική εκδοχή προτείνουμε ένα 2-ανταγωνιστικό αλγόριθμο. Στη συνέχεια, μελετάμε προβλήματα MapReduce χρονοδρομολόγησης με επίγνωση της ενέργειας και στόχο την ελαχιστοποίηση του συνολικού βεβαρημένου χρόνου ολοκλήρωσης ενός συνόλου MapReduce εργασιών, δεδομένου ενός προϋπολογισμού ενέργειας. Αρχικά προτείνουμε τη διατύπωση ενός χαλαρωμένου κυρτού προγράμματος για το πρόβλημα, δεδομένης μίας διάταξης εκτέλεσης των εργασιών. Συνδυάζουμε τη λύση της κυρτής χαλάρωσης με δύο συνήθεις στρατηγικές χρονοδρομολόγησης (First Come First Served and Highest Density First) και συγκρίνουμε πειραματικά τις λύσεις τους. Μολονότι η απόδοση τους για τυχαία στιγμιότυπα είναι αρκετά καλή, όπως αποδεικνύουμε, υπάρχουν στιγμιότυπα για τα οποία αποκλίνει αρκετά από αυτή της βέλτιστης λύσης. Επομένως, προτείνουμε μία μεθόδευση γραμμικού προγραμματισμού, η οποία βασίζεται στη διατύπωση μια γραμμικής χαλάρωσης του προβλήματος μέσω διακριτοποίησης τόσο του χρονικού ορίζοντα καθώς επίσης και των πιθανών τιμών των ταχυτήτων εκτέλεσης. Ο προτεινόμενος αλγόριθμος μετασχηματίζει μία βέλτιστη λύση της γραμμικής χαλάρωσης σε μία εφικτή λύση του προβλήματος εκτελώντας τις εργασίες βάσει της διάταξης που υποδεικνύεται από τα a-points, a e (0,1) των εργασιών στη λύση του γραμμικού προγράμματος. Πετυχαίνουμε έναν αλγόριθμο σταθερής προσέγγισης για το πρόβλημα ελαχιστοποίησης του συνολικού βεβαρημένου χρόνου ολοκλήρωσης ενός συνόλου MapReduce εργασιών, ο οποίος χρησιμοποιεί προσαύξηση της ενέργειας. Στο πλάισιο της MapReduce χρονοδρομολόγησης, όταν η ενέργεια δεν αποτελεί στόχο, μελετάμε επίσης την πιο γενική περίπτωση χρονοδρομολόγησης ενός συνόλου MapReduce εργασιών σε μη σχετιζόμενους επεξεργαστές, με στόχο την ελαχιστοποίηση της συνολικής βεβαρημένης ολοκλήρωσής τους. Προτείνουμε έναν 54-προσεγγιστικό αλγόριθμο ο οποίος υπολογίζει μια εφικτή χρονοδρομολόγηση για το πρόβλημα, συνενώνοντας δύο ξεχωριστές χρονοδρομολογήσεις (για τις Map ή τις Reduce εργασίες) σε μία. Επιπλέον, επεκτείνουμε το μοντέλο μας ώστε να συμπεριλάβει μία επιπλέον σημαντική παράμετρο στις MapReduce εφαρμογές, αυτή του data shuffle. Επιτυγχάνουμε να διατηρήσουμε τον παράγοντα προσέγγισης ίσο με 54 στην περίπτωση που οι Shuffle εργασίες εκτελούνται στους ίδιους επεξεργαστές με τις Reduce εργασίες, ο οποίος γίνεται 84 στην περίπτωση που οι Shuffle και οι Reduce εργασίες εκτελούνται σε διαφορετικούς επεξεργαστές. Τέλος, επικεντρωνόμαστε σε προβλήματα χρονοδρομολόγησης με επίγνωση της θερμοκρασίας, σε ένα μοναδικό επεξεργαστή που λειτουργεί βάσει ενός αυστηρού θερμικού κατωφλίου, όπου κάθε εργασία έχει τη δική της θερμική συνεισφορά και ο στόχος είναι η μεγιστοποίηση του throughput της χρονοδρομολόγησης. Μελετάμε την περίπτωση όπου οι εργασίες είναι μοναδιαίου μήκους και έχουν μία κοινή προθεσμία και επανεξετάζουμε μια κλάση προβλημάτων όπου μια εργασία δεν εκτελείται εφόσον μία άλλη, μικρότερης θερμικής συνεισφοράς ή προθεσμίας, έχει αποδεσμευτεί και είναι διαθέσιμη και επικεντρωνόμαστε στη μεγιστοποίηση του throughput στην offline εκδοχή του προβλήματος, κάτω από την COOLESTFIRST χρονοδρομολόγηση. Αναλύουμε την προσεγγισιμότητα του αλγόριθμου COOLESTFIRST και προτείνουμε δύο διαφορετικά σχήματα στρογγυλοποίησης. Το πρώτο βασίζεται στη διαμέριση της χρονοδρομολόγησης σύμφωνα με τις θερμικές συνεισφορές εργασιών, ενώ το δεύτερο σε μία θεώρηση μέσω γραμμικού προγραμματισμού. Το δεύτερο σχήμα βελτιώνει το πρώτο και δίνει ένα κάτω φράγμα μεγαλύτερο ή ίσο του 0.72.

Λέξη κλειδί :	MapReduce jobs Energy-efficient algorithms Algorithm CoolestFirst Shuffle tasks Scheduling

Ημερομηνία :	12-12-2014

Άδεια χρήσης :

Αρχείο: Zois_2014.pdf

Τύπος: application/pdf

Είσοδος