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

Abstract

Grid systems integrate heterogeneous distributed resources that are not subject to centralized control, creating powerful infrastructures that can provide a variety of services. This thesis studies the allocation of jobs to resources in computational grids, with the use of simulation. The job allocation occurs at two levels. At the first level, the grid scheduler dispatches the jobs to the distributed independent sites, and at the next level, the local scheduler in each site allocates specific processors in order to start the actual process of jobs. Some of the challenges, which are taken into account in this thesis, are the effectiveness of resource management, the variability of job service demands, the system’s performance and the energy consumption. The main objective of the grid scheduler is the discovery and selection of the most appropriate sites and the efficient load sharing. To accomplish this task, the grid scheduler must have some sort of static information about the characteristics of sites. Additionally, it can utilize dynamic site load information in order to watch their state. In the present thesis, policies that utilize dynamic site load information are examined. Two different hybrid policies, which combine two policies, are proposed and evaluated. The first hybrid policy, which is applied in the case where the grid scheduler does not know in advance the service demands of jobs, selects a scheduling type based on the arrival time of a job. The second hybrid policy, which is applied when the grid scheduler is aware of the service demands of jobs, selects the scheduling policy based on a job’s demand. Jobs that are submitted to a computational grid can show high variability regarding their service demands, due to the different user demands. Schedulers must be able to deal with such a situation, especially when service demands are unknown. The performance of various policies at grid and local level, when service demands of jobs are highly variable, is studied in the present thesis. Different levels of variability are examined, and simulations are conducted in order to find the most effective combinations. The frequent transmission of dynamic load information from sites to the grid scheduler results in heavy network traffic and overhead. Two new site allocation policies are presented. One of their main advantages is that they require less frequent dynamic load information in order to operate. They are evaluated under the load balancing among the heterogeneous sites, in addition to performance. Besides performance evaluation, energy consumption is another issue that requires attention. In order to study the case where the energy consumption is taken into account, three local job scheduling polices in a cluster are proposed and evaluated. The cluster involves processors with different performance and power characteristics. One policy is optimized for energy conservation, while the other two policies are optimized for high performance. Simulation experiments are used to discover the most suitable policy according to system’s status and the desired priority (high performance or energy conservation

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