Ποιότητα υπηρεσίας στο υπολογιστικό πλέγμα

Abstract

A grid is a wide-area distributed system spanning a large number of heterogeneous resources, which are bridged by middleware. Those characteristics, combined with the generally unpredictable node availability on a loosely coupled system, render QoS assurance for those systems a highly challenging task. The problem can be logically split into three subproblems; The first subproblem is obtaining accurate metrics for supporting QoS decisions, as well as disseminating those metrics throughout the grid on time. For instance, it is desirable for a grid scheduler to know the (static and real-time) performance characteristics of the worker nodes it is managing, so as to forward high-priority jobs to the fastest nodes. The second subproblem concerns 1-1 mapping of low-level system performance metrics and qualitative characteristics suitable for dealing with resources when performing a task to/from high-level ontologies which are more suitable for signing and enforcing Service Level Agreements. The third subproblem deals with designing the middleware itself so that it supports notions inherent in QoS-aware systems, such as optimal resource use, scalability and execution migration. This thesis deals with the first and third research directions by implementing decentralized (choreography-based) solutions to concrete problems. Regarding the first research direction, the thesis focuses on the problem of distance measurement in volunteer computing systems (an important class of grids). A completely decentralized algorithm with zero network overhead is proposed and tested through its implementation. Additionally, we present a generic framework for implementing simple peer-to-peer and grid systems. The framework (sp2p) is specifically tuned to research purposes, featuring a very steep learning curve and allowing rapid implementation and easy testing of experimental architectures and protocols. Regarding the third research direction, the thesis focuses on the problem of fine-grained scheduling on clusters (clusters being by far the most important class of resources operating within a grid). We implement and present a low-level middleware (Cronus) which performs fine-grained parallel execution of uniform nested loops on clusters, employing a dynamic and decentralized scheduling algorithm. Finally, we introduce Cronus/G, a grid service that “wraps” Cronus and functions as a mediation core for submitting uniform nested loops on a grid with QoS assurance.

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