Algorithmic problems in power management of computing systems

Abstract

This 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.

Η εργασία αυτή επικεντρώνεται σε ενεργειακά αποδοτικούς αλγόριθμους για προβλήματα χρονοδομολόγησης σε επεξεργαστές δυναμικής κλιμάκωσης της ταχύτητας, καθώς επίσης και σε επεξεργαστές οι οποίοι λειτουργούν κάτω από ένα μηχανισμό θέρμανσης και ψύξης, με στόχο την ελαχιστοποίηση ενός ποιοτικού κριτηρίου απόδοσης.Ένα σημαντικό μέρος της έρευνάς μας έχει ώς πρωταρχικό κίνητρο τη χρονοδρομολόγηση σε περιβάλλοντα επεξεργασίας μεγάλου όγκου δεδομένων. Σε αυτό το πλαίσιο, επικεντρωνόμαστε στο πρότυπο MapReduce και μελετάμε προβλήματα ενεργειακά αποδοτικής χρονοδρομολόγησης σε πολλαπλούς επεξεργαστές κλιμακούμενης ταχύτητας, καθώς επίσης και τυπικά προβλήματα χρονοδρομολόγησης σε μη σχετιζόμενους επεξεργαστές.Αρχικά, προτείνουμε το πρόβλημα ελαχιστοποίησης της μέγιστης καθυστέρησης ενός συνόλου εργασιών σε μοναδικό επεξεργαστή κλιμακούμενης ταχύτητας.Μελετάμε δύο εκδοχές του προβλήματος: εκδοχή δεδομένου προϋπολογισμού, όπου ο στόχος είναι η ελαχιστοποίηση της μέγιστης καθυστέρησης για δεδομένο προϋπολογισμό ενέργειας και μία συγκεντρωτική εκδοχή όπου ο στόχος είναι η ελαχιστοποίηση ενός γραμμικού συνδυασμού της μέγιστης καθυστέρησης και της ενέργειας που καταναλώνεται. Προτείνουμε βέλτιστους αλγόριθμους πολυωνυμικού χρόνου για τις δύο εκδοχές στην περίπτωση που οι εργασίες διαθέτουν κοινούς χρόνους αποδέσμευσης. Οι προτεινόμενοι αλγόριθμοι βασίζονται σε ένα σύνολο δομικών χαρακτηριστικών της βέλτιστης χρονοδρομολόγησης, τα οποία εξάγονται με την εφαρμογή των KKT (Karush-Kuhn-Tucker) συνθηκών σε ένα κυρτό πρόγραμμα αντίστοιχο του προβλήματός μας. Στην περίπτωση που οι εργασίες διαθέτουν αυθαίρετους χρόνους αποδέσμευσης, αποδεικνύουμε ότι και οι δύο εκδοχές είναι strongly NP-hard. Επιπλέον, στην τελευταία περίπτωση, για την εκδοχή δεδομένου προϋπολογισμού δείχνουμε ότι δεν επιδέχεται ντετερμιστικό αλγόριθμο σταθερού λόγου ανταγωνισμού, ενώ για την συγκεντρωτική εκδοχή προτείνουμε έναν 2-ανταγωνιστικό αλγόριθμο.Στη συνέχεια μελετάμε προβλήματα MapReduce χρονοδρομολόγησης με επίγνωση της ενέργειας και στόχο την ελαχιστοποίηση του συνολικού βεβαρημένου χρόνου ολοκλήρωσης ενός συνόλου MapReduce εργασιών, δεδομένου ενός προϋπολογισμού ενέργειας. Αρχικά προτείνουμε τη διατύπωση ενός χαλαρωμένου κυρτού προγράμματος για το πρόβλημα, δεδομένης μίας διάταξης εκτέλεσης των εργασιών. Συνδυάζουμε τη λύση της κυρτής χαλάρωσης με δύο συνήθεις στρατηγικές χρονοδρομολόγησης (First Come First Served and Highest Density First) και συγκρίνουμε πειραματικά τις λύσεις τους. Μολονότι η απόδοση τους για τυχαία στιγμιότυπα είναι αρκετά καλή, όπως αποδεικνύουμε, υπάρχουν στιγμιότυπα για τα οποία αποκλίνει αρκετά από αυτή της βέλτιστη λύσης. Επομένως, προτείνουμε μία μεθόδευση γραμμικού προγραμματισμού, η οποία βασίζεται στη διατύπωση μίας γραμμικής χαλάρωσης του προβλήματος μέσω διακριτοποίησης τόσο του χρονικού ορίζοντα καθώς επίσης και των πιθανών τιμών των ταχυτήτων εκτέλεσης. Ο προτεινόμενος αλγόριθμος μετασχηματίζει μία βέλτιστη λύση της γραμμικής χαλάρωσης σε μία εφικτή λύση του προβλήματος εκτελώντας τις εργασίες βάσει της διάταξης που υποδεικνύεται από τα α-points, α ανήκει στο (0,1), των εργασιών στη λύση του γραμμικού προγράμματος.Πετυχαίνουμε έναν αλγόριθμο σταθερής προσέγγισης για το πρόβλημα ελαχιστοποίησης του συνολικού βεβαρημένου χρόνου ολοκλήρωσης ενός συνόλου MapReduce εργασιών, ο οποίος χρησιμοποιεί προσαύξηση της ενέργειας. Στο πλαίσιο της MapReduce χρονοδρομολόγησης, όταν η ενέργεια δεν αποτελεί στόχο, μελετάμε επίσης την πιο γενική περίπτωση χρονοδρομολόγησης ενός συνόλου MapReduce εργασιών σε μη σχετιζόμενους επεξεργαστές, με στόχο την ελαχιστοποίηση της συνολικής βεβαρημένης ολοκλήρωσής τους. Προτείνουμε έναν 54-προσεγγιστικό αλγόριθμο ο οποίος υπολογίζει μία εφικτή χρονοδρομολόγηση για το πρόβλημα, συνενώνοντας δύο ξεχωριστές χρονοδρομολογήσεις (για τις Map ή τις Reduce εργασίες) σε μία. Επιπλέον, επεκτείνουμε το μοντέλο μας ώστε να συμπεριλάβει μία επιπλέον σημαντική παράμετρο στις MapReduce εφαρμογές, αυτή του data shuffle. Επιτυγχάνουμε να διατηρήσουμε τον παράγοντα προσέγγισης ίσο με 54 στην περίπτωση που οι Shuffle εργασίες εκτελούνται στους ίδιους επεξεργαστές με τις Reduce εργασίες, ο οποίος γίνεται 84 στην περίπτωση που οι Shuffle και οι Reduce εργασίες εκτελούνται σε διαφορετικούς επεξεργαστές.Τέλος, επικεντρωνόμαστε σε προβλήματα χρονοδρομολόγησης με επίγνωση της θερμοκρασίας, σε ένα μοναδικό επεξεργαστή που λειτουργεί βάσει ενός αυστηρού θερμικού κατωφλίου, όπου κάθε εργασία έχει τη δική της θερμική συνεισφορά και ο στόχος είναι η μεγιστοποίηση του throughput της χρονοδρομολόγησης. Μελετάμε την περίπτωση όπου οι εργασίες είναι μοναδιαίου μήκους και έχουν μία κοινή προθεσμία και επανεξετάζουμε μία κλάση προβλημάτων όπου μία εργασία δεν εκτελείται εφόσον μία άλλη, μικρότερης θερμικής συνεισφοράς ή προθεσμίας, έχει αποδεσμευτεί και είναι διαθέσιμη και επικεντρωνόμαστε στη μεγιστοποίηση του throughput στην offline εκδοχή του προβλήματος, κάτω από την CoolestFirst χρονοδρομολόγηση. Αναλύουμε την προσεγγισιμότητα του αλγόριθμου CoolestFirst και προτείνουμε δύο διαφορετικά σχήματα στρογγυλοποίησης. Το πρώτο βασίζεται στη διαμέριση της χρονοδρομολόγησης σύμφωνα με τις θερμικές συνεισφορές των εργασιών, ενώ το δεύτερο σε μία θεώρηση μέσω γραμμικού προγραμματισμού. Το δεύτερο σχήμα βελτιώνει το πρώτο και δίνει ένα κάτω φράγμα μεγαλύτερο ή ίσο του 0.72.