Αποτίμηση της απόδοσης πολιτικών χρονοδρομολόγησης παράλληλων εργασιών σε συστήματα πλέγματος με μοντέλα προσομοίωσης

Abstract

The demand for computing resources of modern applications has been increased significantly as compared to the past. Meeting the modern demands with existing resources has become feasible by organizing the available resources appropriately and sharing them. A grid system coordinates resources that are not subject to centralized control using general-purpose protocols to deliver non-trivial qualities of service. The development of efficient scheduling algorithms is required in order to efficiently utilize grid systems. The main subject of this thesis is the performance evaluation of parallel job scheduling policies in grid systems by means of simulation models. The workload characteristics are responsible for the performance of the system. Therefore, the system must implement the necessary algorithms and techniques that will provide adequate flexibility to cope with all possible situations. For this reason we examine the performance in the case of workload which comprises Bags of Gangs. We also utilize a migration schema to balance the load in the heterogeneous system. Fragmentation is a situation which frequently occurs in the case of gang scheduling in systems. We suggest a migration technique which alleviates this problem and improves the system performance drastically. We examine this technique under various workloads. We consider the presence of critical sporadic jobs and we also examine the impact of the variability in gangs’ service time on the scheduling performance. Load balancing plays a significant role on the overall system performance. We examine a new grid scheduler which implements periodic feedback. The goal of this scheduler is to evenly distribute the load across the available clusters. The scheduler is considered suitable for gang scheduling. This thesis also analyses a workload model which comprises gangs with precedence constraints. In this case a subsequent gang can be dynamically generated in the system after the execution of the initial gang based on affinity information which resides in the caches of the previously seized processors. Different gang scheduling policies are examined under the new workload model. Another interesting topic which we consider in this study is the scheduling of gangs in multi-core clusters. We modify the gang scheduling policies and make them suitable for homogeneous and heterogeneous multi-core clusters. Furthermore, we provide a migration schema which is suitable for scheduling gangs in multi-core clusters. We investigate the benefits and differences between the performance of single-core algorithms and their multi-core counterparts. Finally, we deal with the case of heterogeneous multi-core clusters and present the impact on the performance of our policies. To sum up, the main contribution of this thesis is the development of new scheduling algorithms for parallel jobs in order to improve the performance of grid systems. The suggested scheduling algorithms allow for better resource utilization and have a significant impact on grid systems’ performance. We achieve this by implementing various techniques such as improved grid scheduling algorithms with periodic feedback and new migration schemas. We also consider and examine complicated workload models which include Bags of Gangs, gangs with precedence constraints and critical jobs. Finally, we suggest new gang scheduling and load balancing algorithms for multi-core clusters.

Οι ανάγκες σε υπολογιστική ισχύ των σύγχρονων εφαρμογών έχουν αυξηθεί κατά πολύ σε σχέση με τα παρελθόν. Η κάλυψη των αναγκών με τους υπάρχοντες πόρους έγινε εφικτή συλλέγοντας τους διαθέσιμους πόρους και οργανώνοντας τους κατάλληλα. Ένα σύστημα πλέγματος αποτελείται από ένα σύνολο διαμοιραζόμενων πόρων που δεν υπόκεινται σε κεντρικό έλεγχο, χρησιμοποιεί γενικού σκοπού πρωτόκολλα και προσφέρει σημαντικές υπηρεσίες στους χρήστες. Για την αποτελεσματικότερη αξιοποίηση ενός συστήματος πλέγματος καθίσταται επιτακτική η ανάπτυξη αποδοτικών πολιτικών χρονοδρομολόγησης. Το αντικείμενο που πραγματεύεται η παρούσα διατριβή είναι η αποτίμηση της απόδοσης πολιτικών χρονοδρομολόγησης παράλληλων εργασιών σε συστήματα πλέγματος. Η απόδοση των πολιτικών μελετάται με τη χρήση μοντέλων προσομοίωσης. Οι ιδιαιτερότητες του φόρτου εργασίας είναι καθοριστικές για την απόδοση του συστήματος. Το σύστημα πρέπει να είναι εφοδιασμένο με τεχνικές και αλγορίθμους που θα του παρέχουν την κατάλληλη ευελιξία ώστε να αντιμετωπίσει όλες τις πιθανές καταστάσεις. Για το λόγο αυτό εξετάζουμε την απόδοση στην περίπτωση που στο φόρτο έχουμε δέσμες παράλληλων εργασιών τύπου ομάδας και χρησιμοποιούμε τεχνικές μεταναστεύσεων για την εξισορρόπηση του φόρτου σε ετερογενές σύστημα πλέγματος. Σε ένα σύστημα πλέγματος που εξυπηρετεί παράλληλες εργασίες τύπου ομάδας παρουσιάζεται έντονα το φαινόμενο της κατάτμησης. Προτείνουμε μια τεχνική μεταναστεύσεων για την επίλυση αυτού του φαινομένου και για τη βελτίωση της απόδοσης την οποία εξετάζουμε κάτω από διάφορες συνθήκες φόρτου εργασίας. Μελετάμε τον τρόπο με τον οποίο μπορεί η τεχνική των μεταναστεύσεων να διαχειριστεί την άφιξη κρίσιμων εργασιών που εμφανίζονται σποραδικά και επίσης εξετάζουμε την επίδραση της μεταβλητότητας του χρόνου εκτέλεσης στη χρονοδρομολόγηση των παράλληλων εργασιών τύπου ομάδας. Η εξισορρόπηση του φόρτου στο σύστημα είναι πολύ σημαντικός παράγοντας που συμβάλλει στη ομαλή λειτουργία και τη βελτίωση της απόδοσης. Εξετάζουμε ένα νέο δρομολογητή εργασιών σε επίπεδο πλέγματος που υποστηρίζει περιοδική ανάδραση με το σύστημα. Στόχος του αλγορίθμου περιοδικής ανάδρασης είναι η εξισορρόπηση του φόρτου μεταξύ των διαθέσιμων συστοιχιών. Ο αλγόριθμος που εξετάζουμε θεωρείται κατάλληλος για τη δρομολόγηση παράλληλων εργασιών. Στην παρούσα διατριβή αναλύουμε επίσης το μοντέλο φόρτου παράλληλων εργασιών τύπου ομάδας με περιορισμούς προτεραιοτήτων. Εξετάζουμε την περίπτωση που μία παράλληλη εργασία μπορεί να δημιουργηθεί δυναμικά στο σύστημα βάσει εξαρτήσεων με το περιεχόμενο της λανθάνουσας μνήμης (cache) από προηγούμενες εκτελεσθείσες εργασίες. Μελετάμε την απόδοση διαφορετικών πολιτικών χρονοδρομολόγησης που αφορούν το νέο μοντέλο εργασιών κάτω από διάφορες συνθήκες φόρτου. Ένα ακόμη θέμα που μας απασχολεί είναι η χρονοδρομολόγηση παράλληλων εργασιών τύπου ομάδας σε συστοιχίες πολυπύρηνων επεξεργαστών. Επιλέγουμε μία τεχνική μεταναστεύσεων κατάλληλη για αυτή την περίπτωση και τροποποιούμε κατάλληλα τις υπάρχουσες πολιτικές χρονοδρομολόγησης για την εξυπηρέτηση παράλληλων εργασιών τύπου ομάδας σε πολυπύρηνες ομοιογενείς και ετερογενείς συστοιχίες. Επίσης, εξετάζουμε τα οφέλη και τη διαφορά στην απόδοση μεταξύ των αλγορίθμων για πολυπύρηνες συστοιχίες και των εναλλακτικών αλγορίθμων για μονοπύρηνες συστοιχίες. Τέλος, ασχοληθήκαμε και με την περίπτωση της ετερογένειας των πολυπύρηνων συστοιχιών και παρουσιάζουμε τον αντίκτυπο που έχει στην απόδοση των πολιτικών που εφαρμόζουμε. Συνοψίζοντας, η συνεισφορά της διατριβής έγκειται στην ανάπτυξη νέων πολιτικών χρονοδρομολόγησης παράλληλων εργασιών για καλύτερη αξιοποίηση των διαθέσιμων πόρων στην περίπτωση των συστημάτων πλέγματος. Προτείνονται και εξετάζονται διεξοδικά διάφορες τεχνικές όπως αλγόριθμοι με ανάδραση από το σύστημα, τεχνικές μεταναστεύσεων εργασιών καθώς και περίπλοκες περιπτώσεις μοντέλων εργασιών όπως δέσμες παράλληλων εργασιών τύπου ομάδας, εργασίες με περιορισμούς προτεραιότητας και κρίσιμες εργασίες. Επίσης, μελετήσαμε το θέμα της εξισορρόπησης φόρτου σε συστήματα πλέγματος και προτείνουμε νέους αλγορίθμους χρονοδρομολόγησης που κάνουν ομαλότερη τη μετάβαση σε συστήματα συστοιχιών πολυπύρηνων επεξεργαστών.