|
Institute Personnel > Research > Savvas Ilias |
|
| |
|
| Scheduling and Assignment of CPU-Intensive Tasks on Large Heterogeneous Distributed Systems |
| 15/12/2008 |
| |
In this research, the problem of scheduling and allocation of tasks
to processing nodes of large heterogeneous distributed systems is
studied. Each node of the system is considered as an autonomous
stand-alone processing unit, ranging from workstations or small
computing devices to computational clusters. Each node has its own
processing power and they are interconnected through a network.
The network structure has been considered irregular and dynamic,
although some specific topologies like grids, hyper-cubes and
rings were examined. In such an environment the task scheduling
problem was approached with heuristic techniques.
For large-scale scheduling on very large distributed systems, two
Tabu-Search-like algorithms were applied and tested. These
techniques do not try to perfectly balance the load of the system
since that is completely unrealistic especially for large
distributed systems, but they try to solve the problem locally,
using only the local information of each node. The simulation
results had shown the efficiency of the proposed algorithms. They
can achieve an approximate improvement of 80\% of the efficiency
of the whole system.
Finally, in a cluster-computing environment, a dynamic technique,
which perfectly balances the load among the nodes of the cluster,
was employed. Using the divide and conquer principle, the
algorithm splits the cluster to hyper-planes and then balances the
load among them. Recursively, the hyper-planes are dividing into
planes of smaller dimensions, until the dimensionality becomes
zero and each hyper-plane becomes a single node. Then, all the
nodes of the cluster are equally loaded.
|
|
| Ανάπτυξη Ευρεστικών Αλγορίθμων Βελτιστοποίησης Της Απόδοσης Ετερογενών Κατανεμημένων Συστημάτων. |
| 15/12/2008 |
| |
Ένα Κατανεμημένο Σύστημα Υπολογιστών μπορεί να ορισθεί σαν ένα δίκτυο από σταθμούς εργασίας (workstations) ή υπολογιστικών μονάδων ή πολύ γενικότερα κόμβων. Αυτοί οι κόμβοι είναι δυνατόν να διαφέρουν μεταξύ τους τόσο σε υπολογιστική ισχύ όσο και σε διάφορα άλλα επίπεδα όπως μνήμη, περιφερειακές συσκευές κλπ. Συνδέονται μεταξύ τους με συνδέσμους οι οποίοι επίσης μπορεί να έχουν διαφορετικά χαρακτηριστικά όπως το bandwidth ή απόσταση (Ευκλείδεια απόσταση) κλπ. Η τοπολογία αυτών των δικτύων μπορεί να είναι ή κανονική όπως για παράδειγμα αστέρας, υπερ-κύβος κλπ. ή μη κανονική. Ένα σύστημα στο οποίο οι συμμετέχοντες κόμβοι είναι διαφορετικοί και συνδέονται μεταξύ τους με συνδέσεις οι οποίες έχουν διαφορετικά χαρακτηριστικά είναι γνωστό σαν Ετερογενές Κατανεμημένο Σύστημα (ΕΚΣ). Το βασικό πλεονέκτημα ενός ΕΚΣ είναι η ικανότητά του να μοιράζεται δεδομένα και διαφορετικούς πόρους κόμβων που βρίσκονται διεσπαρμένοι σε μεγάλες γεωγραφικές περιοχές. Διαθέτουν τοπική αυτονομία, πράγμα το οποίο τα κάνει να είναι πάντα διαθέσιμα, και ένα βασικό χαρακτηριστικό είναι ότι η ασφάλεια του συστήματος αποτελεί τοπικό ζήτημα και όχι συνολικό.
Πολλοί ερευνητές στο παρελθόν αλλά και τώρα, έχουν καταβάλλει πολλές προσπάθειες ώστε να βελτιστοποιήσουν την απόδοση τέτοιων συστημάτων, χρησιμοποιώντας είτε στατικές είτε δυναμικές τεχνικές προγραμματισμού των εργασιών (χρονοπρογραμματισμός) που ανατίθενται στο ΕΚΣ (static / dynamic task scheduling). Ένα από τα κύρια χαρακτηριστικά των στατικών τεχνικών είναι η προσπάθεια να επιταχύνουν την εκτέλεση των εφαρμογών ενώ παράλληλα να ελαχιστοποιήσουν την διάρκεια των επικοινωνιών μεταξύ των κόμβων. Υποθέτοντας ότι μία εφαρμογή αποτελείται από ένα σύνολο εργασιών, ο στόχος των στατικών τεχνικών είναι:
1. Να μπορέσει να εκτιμηθεί η χρονική διάρκεια κάθε εργασίας,
2. Υπολογισμός του χρόνου μεταφοράς της, εάν είναι να μεταφερθεί σε άλλο κόμβο,
3. Την συνένωση εργασιών σε μεγαλύτερα σύνολα ώστε να ελαχιστοποιηθεί ο χρόνος μεταφοράς τους στο δίκτυο, και τέλος
4. Να μεταφέρει τις εργασίες ή τα σύνολα εργασιών στους κόμβους που φαίνεται να έχουν γι’ αυτές την καλύτερη απόδοση.
Από την άλλη μεριά, οι δυναμικές τεχνικές βασίζονται στην μεταφορά των εργασιών κατά την διάρκεια της εκτέλεσής τους από τους πολύ απασχολημένους κόμβους στους λιγότερο ή και καθόλου απασχολημένους. Η βασική υπόθεση εδώ είναι ότι αν το σύνολο των φορτίων είναι ισοκατανεμημένα στους κόμβους τότε βελτιστοποιείται και ο χρόνος εκτέλεσης της κάθε εφαρμογής. Εδώ, ο κάθε κόμβος αποφασίζει (ανάλογα με την τεχνική και την διαθέσιμη πληροφορία) για το εάν θα κρατήσει κάποια εργασία ή όχι, και εάν όχι σε ποιόν κόμβο θα την στείλει, φυσικά χρησιμοποιώντας κάποια κριτήρια. Ανάλογα με την χρησιμοποιούμενη τεχνική, οι δυναμικές μέθοδοι χωρίζονται στις εξής υποκατηγορίες:
• Κεντρικοποιημένες / Κατανεμημένες,
• Αποστολέας / Παραλήπτης,
• Στατικές / Προσαρμόσιμες
Ένα πολύ σημαντικό χαρακτηριστικό αυτών των τεχνικών είναι ότι η πληροφορία που χρειάζεται κάθε κόμβος για να ενεργήσει είναι σχετικά μικρή και έχει ήδη αποδειχτεί ότι απλοί ευρεστικοί (heuristics) αλγόριθμοι αποδίδουν πάρα πολύ καλά, ειδικά εάν η πολιτική μεταφοράς εργασιών έχει επιλεχθεί πολύ προσεκτικά.
Το συμπέρασμα είναι ότι ενώ πολλοί αλγόριθμοι έχουν προταθεί και δοκιμασθεί, και πάρα πολλές παράμετροι έχουν εξετασθεί, φαίνεται ότι καμία τεχνική δεν υπερέχει των άλλων σε πολύ γενικά ΕΚΣ. Εν αντιθέσει, κάθε ΕΚΣ ανάλογα με την φύση του και τις προσδοκίες των χρηστών του απαιτεί διαφορετικές τεχνικές και πολιτικές.
Σε αυτό το ερευνητικό πρόγραμμα, θεωρούμε ένα ΕΚΣ αποτελούμενο από Ν κόμβους στους οποίους ανατίθενται ανεξάρτητες μεταξύ τους εργασίες / εφαρμογές προς εκτέλεση. Οι εργασίες αυτές έρχονται σε κάθε κόμβο προς εκτέλεση είτε άμεσα, από τον εξωτερικό κόσμο, είτε από κάποιον άλλο κόμβο. Η συχνότητα άφιξης των εργασιών στο ΕΚΣ ακολουθεί την κατανομή Poisson και το υπολογιστικό μέγεθός τους είναι τυχαίο. Επίσης τυχαίο είναι και το μέγεθός τους σε περίπτωση μετακίνησής τους σε κάποιον άλλο κόμβο. Επομένως, όλες αυτές οι παράμετροι πρέπει να μοντελοποιηθούν σαν τυχαίες μεταβλητές. Τέλος, κάθε χρονική στιγμή, η κατάσταση κάποιας εργασίας μπορεί να είναι μία από τις ακόλουθες:
• Να εκτελείται,
• Να περιμένει στην τοπική ουρά κάποιου κόμβου για να εκτελεσθεί, ή τέλος
• Να μεταφέρεται από κάποιο κόμβο προς κάποιον άλλο.
Σε ένα περιβάλλον σαν αυτό που αναπτύχθηκε, σ’ αυτό το ερευνητικό πρόγραμμα έχουμε σκοπό να προσεγγίσουμε το πρόβλημα της δυναμικής ισοκατανομής του φόρτου των κόμβων με μία διαφορετική λογική: αντί να προσπαθήσουμε να βρούμε έναν αλγόριθμο ισοκατανομής των φορτίων των κόμβων θα θεωρήσουμε σαν πρωταρχικό στόχο την μείωση ή και ελαχιστοποίηση του χρόνου που μία εργασία μένει στο σύστημα. Σαν χρονική διάρκεια μίας εργασίας ορίζουμε τον χρόνο που απαιτείται από την στιγμή της εισόδου της εργασίας στο σύστημα μέχρι και να εκτελεσθεί. Θα προσπαθήσουμε να αποδείξουμε ότι ακόμη και ένα όχι τέλεια ισοκατανεμημένο σύστημα συμπεριφέρεται πολύ καλά επικεντρώνοντας τις προσπάθειές μας σε αυτές καθαυτές τις εργασίες που υποβάλλονται στο ΕΚΣ.
Ο αλγόριθμος που θα προταθεί λειτουργεί σε δύο φάσεις. Πρώτα θα εφαρμόζεται μία επαναληπτική ανίχνευση του γειτονικού περιβάλλοντος του κάθε κόμβου ανάλογα με την πληροφορία που διαθέτει ο ενεργών κόμβος. Θεωρούμε σαν γειτονικούς μόνο τους πρώτου επιπέδου γειτονικούς κόμβους (δηλαδή αυτού με τους οποίους επικοινωνεί άμεσα ο ενεργών κόμβος). Αυτός ο αλγόριθμος θα αποφασίζει εάν ο η εργασία θα παραμείνει να εκτελεσθεί στον ενεργούντα κόμβο ή εάν θα μεταφερθεί κάπου αλλού. Τα αποτελέσματα αυτού του αλγόριθμου αποτελούν τοπικά βέλτιστες λύσεις και εξαρτώνται αποκλειστικά από το πλήθος των γειτονικών κόμβων. Στη συνέχεια, και εάν το σύστημα φτάσει σε μία μη αποδεκτή κατάσταση, ένας δεύτερος μετά-ευρεστικός αλγόριθμος του τύπου Tabu Search θα «ανακινεί» το όλο ΕΚΣ.
Οι στόχοι αυτού του ερευνητικού προγράμματος αναλύονται ως εξής:
1. Δημιουργία του μαθηματικού μοντέλου του συστήματος.
2. Ανάπτυξη αλγορίθμων που θα λειτουργούν σαν τους προγραμματιστές των εισερχομένων εφαρμογών / εργασιών στο σύστημα.
3. Υλοποίηση των αλγορίθμων στο εργαστήριο “Sun” του τμήματος Τεχνολογίας Πληροφορικής & Τηλεπικοινωνιών.
4. Εγκατάσταση ανάλογων λογισμικών στο ίδιο εργαστήριο με σκοπό την σύγκριση των προταθέντων αλγορίθμων με άλλους που ήδη έχουν υλοποιηθεί και χρησιμοποιούνται εμπορικά.
Τα προσδοκώμενα αποτελέσματα του ερευνητικού προγράμματος είναι τα ακόλουθα:
1. Ανάπτυξη του μοντέλου / αλγορίθμων και ανακοίνωσή τους σε διεθνή συνέδρια καθώς και δημοσίευσή τους σε έγκριτα επιστημονικά περιοδικά του χώρου.
2. Υλοποίηση των προτεινόμενων αλγορίθμων και σύγκρισή τους με άλλους του ίδιου χώρου.
3. Δημιουργία λογισμικού των προταθέντων μεθόδων.
|
|
| Τεχνικές Διαχείρισης Πόρων για Επαύξηση της Χωρητικότητας των Δικτύων Κινητών Επικοινωνιών για Παροχή Εγγυημένης Ποιότητας Υπηρεσιών |
| 15/12/2008 |
| |
|
|
| Μελέτη και Ανάπτυξη Ασύρματου Δικτύου Αισθητήρων με Εφαρμογή στη Γεωργία Ακριβείας» , στα πλαίσια του ερευνητικού προγράμματος Αρχιμήδης |
| 15/12/2008 |
| |
|
|
|
|
|
| |
|
|
|
| |
|
|
