Βιβλιοθήκη ΟΠΑ - Ψηφιακό Αποθετήριο

ΠΥΞΙΔΑ Ιδρυματικό Αποθετήριο
και Ψηφιακή Βιβλιοθήκη

Όνομα χρήστη
Κωδικός πρόσβασης

Συλλογές :	Ιδρυματικό Αποθετήριο ΟΠΑ / AUEB Institutional Repository Σχολή Επιστημών και Τεχνολογίας της Πληροφορίας / School of Informatics Τμήμα Πληροφορικής / Department of Informatics Μεταπτυχιακές Εργασίες / Postgraduate dissertations

Τίτλος :	Ευρετικοί αλγόριθμοι ανάθεσης εργασιών σε κατανεμημένα συστήματα

Δημιουργός :	Βατρικάς, Αναστάσιος

Συντελεστής :	Μήλης, Ιωάννης (Επιβλέπων καθηγητής) Οικονομικό Πανεπιστήμιο Αθηνών, Τμήμα Πληροφορικής (Degree granting institution)

Τύπος :	Text

Φυσική περιγραφή :	122σ.

Γλώσσα :	el

Περίληψη :	Η βέλτιστη αξιοποίηση των πόρων ενός κατανεμημένου συστήματος από τις διεργασίες ενός προγράμματος ή/και πολλών προγραμμάτων είναι, ο αντικειμενικός σκοπός κάθε σχετικής έρευνας, από την αρχή της σύλληψης της ιδέας ενός τέτοιου συστήματος.Στην παρούσα εργασία ως πόροι ενός κατανεμημένου συστήματος εννοούνται οι διαθέσιμοι επεξεργαστές του και οι μεταξύ τους συνδέσεις επικοινωνίας. Το αντικείμενο της εργασίας αυτής λοιπόν, είναι η μελέτη και η σύγκριση μερικών διαφορετικών αλγορίθμων ανάθεσης εργασιών στους επεξεργαστές ενός κατανεμημένου συστήματος. Ο απώτερος στόχος της ανάθεσης αυτής είναι η βελτιστοποίηση της χρήσεως ενός τέτοιου συστήματος. Ως κριτήρια βελτιστοποίησης μπορούν να θεωρηθούν τα παρακάτω [SHI]:1. Η ελαχιστοποίηση του κόστους επικοινωνίας μεταξύ των επί μέρους εργασιών (των διεργασιών).2. Ο γρήγορος χρόνος εκτελέσεως για όλη την διεργασία.3. Ο υψηλός βαθμός παραλληλισμού.4. Η αποτελεσματική χρήση των πόρων του συστήματος.Ο αντικειμενικός σκοπός είναι η ελαχιστοποίηση του κόστους μίας τέτοιας ανάθεσης, δηλαδή η κατανομή εκείνη των εργασιών στους επεξεργαστές του συστήματος, η οποία θα έχει ως συνέπεια το άθροισμα των κοστών εκτελέσεως και των κοστών επικοινωνίας να έχει την μικρότερη δυνατή τιμή. Έχει αποδειχθεί [ΜΜ], ότι για έναν αριθμό επεξεργαστών μεγαλύτερο του δύο (2), το πρόβλημα δεν είναι επιλύσιμο σε πολυωνυμικό χρόνο (NP-complete). Εντός των πλαισίων αυτών, παρουσιάζονται και συγκρίνονται μεταξύ τους, τρεις διαφορετικοί ευρετικοί αλγόριθμοι. Ο πρώτος αλγόριθμος μερικής ανάθεσης (V. Μ. Lo) [LO] βασίζεται στην παρακάτω ιδέα: Σε κάθε επανάληψη του πρώτου βήματος του αλγορίθμου, οι εργασίες που ανετέθησαν στο προηγούμενο βήμα (βάσει του αλγορίθμου του Stone) διαγράφονται και ένας νέος γράφος εργασιών και επεξεργαστών με ενημερωμένα (νέα) βάρη ακμών, κατασκευάζεται. Η διαδικασία αυτή επαναλαμβάνεται μέχρις ότου καμμία εργασία να μην μπορεί να ανατεθεί σε ένα βήμα. Όσες εργασίες δεν έχουν ανατεθεί μέχρι αυτό το στάδιο, ανατίθενται στα επόμενα βήματα του αλγορίθμου.Ο δεύτερος αλγόριθμος (Υ. Kopidakis, L. Lamari και V. Zissimopoulos) [KLZ], είναι ένας νέος ευρετικός αλγόριθμος ο οποίος είτε ομαδοποιεί τις εργασίες, είτε τις αναθέτει στους διαθέσιμους επεξεργαστές, βασιζόμενος σε μία ακμή μεγίστου βάρους ενός τροποποιημένου γράφου. Ο τροποποιημένος αυτός γράφος προκύπτει εάν αναθεωρήσουμε το πρόβλημα: Αντί της ελαχιστοποίησης του συνολικού κόστους επικοινωνίας και του συνολικού κόστους εκτελέσεως, προσπαθούμε να δούμε το πρόβλημα, ως ένα πρόβλημα μεγιστοποίησης. Βάσει της λογικής αυτής, ο σκοπός επικεντρώνεται στην αποφυγή μεγάλων επικοινωνιακών κοστών μεταξύ εργασιών και, αναποτελεσματικών αναθέσεων. Δηλαδή, αντί ο αλγόριθμος αυτός να ψάχνει πως θα προσδιορίσει τις καλλίτερες, εξ απόψεως κοστών εκτελέσεως και επικοινωνίας, αναθέσεις, προσπαθεί να αποφύγει τα υψηλά κόστη επικοινωνίας και εκτελέσεως.Ο τρίτος αλγόριθμος (I. Milis) [MM], είναι επίσης ένας ευρετικός αλγόριθμος, ο οποίος καταλήγει σε μία πλήρη ανάθεση εργασιών στους διαθέσιμους επεξεργαστές. Εν αντιθέσει με τους αλγορίθμους μερικής ανάθεσης, ο αλγόριθμος αυτός βασίζεται στην ιδέα της πλήρους ανάθεσης των εργασιών στους διαθέσιμους επεξεργαστές, σε κάθε βήμα εκτέλεσης του.Και οι τρεις αλγόριθμοι υλοποιήθησαν σε γλώσσα προγραμματισμού Pascal (σε σύστημα Open VMS ver.6.2. Kronos, στον Alpha Server 1000 του Κέντρου Υπολογιστών του Οικονομικού Πανεπιστημίου Αθηνών) και συνεκρίθησαν μεταξύ τους, ως προς τα κόστη ανάθεσης. Τα αποτελέσματα των συγκρίσεων αυτών και εν γένει της μελέτης αυτής, εμπεριέχονται στο 5° Κεφάλαιο της εργασίας αυτής, όπου ευρίσκονται τα δεδομένα του προβλήματος, οι πίνακες, τα διαγράμματα και τα τελικά μας συμπεράσματα.Τελειώνοντας, θα πρέπει να αναφερθεί ότι το πρόβλημα της ανάθεσης των εργασιών ενός κατανεμημένου συστήματος στους διαθέσιμους επεξεργαστές του, εντάσσεται στο γενικότερο πλαίσιο της βέλτιστης χρήσης των πόρων του συστήματος αυτού. Εντός του πλαισίου αυτού, πρέπει να ληφθεί υπ’ όψιν και ένα πλήθος άλλων παραγόντων, όπως και κάποιοι άλλοι περιορισμοί τους οποίους δεν συμπεριέλαβε η μελέτη αυτή.

Περίληψη :

Η βέλτιστη αξιοποίηση των πόρων ενός κατανεμημένου συστήματος από τις διεργασίες ενός προγράμματος ή/και πολλών προγραμμάτων είναι, ο αντικειμενικός σκοπός κάθε σχετικής έρευνας, από την αρχή της σύλληψης της ιδέας ενός τέτοιου συστήματος.Στην παρούσα εργασία ως πόροι ενός κατανεμημένου συστήματος εννοούνται οι διαθέσιμοι επεξεργαστές του και οι μεταξύ τους συνδέσεις επικοινωνίας. Το αντικείμενο της εργασίας αυτής λοιπόν, είναι η μελέτη και η σύγκριση μερικών διαφορετικών αλγορίθμων ανάθεσης εργασιών στους επεξεργαστές ενός κατανεμημένου συστήματος. Ο απώτερος στόχος της ανάθεσης αυτής είναι η βελτιστοποίηση της χρήσεως ενός τέτοιου συστήματος. Ως κριτήρια βελτιστοποίησης μπορούν να θεωρηθούν τα παρακάτω [SHI]:1. Η ελαχιστοποίηση του κόστους επικοινωνίας μεταξύ των επί μέρους εργασιών (των διεργασιών).2. Ο γρήγορος χρόνος εκτελέσεως για όλη την διεργασία.3. Ο υψηλός βαθμός παραλληλισμού.4. Η αποτελεσματική χρήση των πόρων του συστήματος.Ο αντικειμενικός σκοπός είναι η ελαχιστοποίηση του κόστους μίας τέτοιας ανάθεσης, δηλαδή η κατανομή εκείνη των εργασιών στους επεξεργαστές του συστήματος, η οποία θα έχει ως συνέπεια το άθροισμα των κοστών εκτελέσεως και των κοστών επικοινωνίας να έχει την μικρότερη δυνατή τιμή. Έχει αποδειχθεί [ΜΜ], ότι για έναν αριθμό επεξεργαστών μεγαλύτερο του δύο (2), το πρόβλημα δεν είναι επιλύσιμο σε πολυωνυμικό χρόνο (NP-complete). Εντός των πλαισίων αυτών, παρουσιάζονται και συγκρίνονται μεταξύ τους, τρεις διαφορετικοί ευρετικοί αλγόριθμοι. Ο πρώτος αλγόριθμος μερικής ανάθεσης (V. Μ. Lo) [LO] βασίζεται στην παρακάτω ιδέα: Σε κάθε επανάληψη του πρώτου βήματος του αλγορίθμου, οι εργασίες που ανετέθησαν στο προηγούμενο βήμα (βάσει του αλγορίθμου του Stone) διαγράφονται και ένας νέος γράφος εργασιών και επεξεργαστών με ενημερωμένα (νέα) βάρη ακμών, κατασκευάζεται. Η διαδικασία αυτή επαναλαμβάνεται μέχρις ότου καμμία εργασία να μην μπορεί να ανατεθεί σε ένα βήμα. Όσες εργασίες δεν έχουν ανατεθεί μέχρι αυτό το στάδιο, ανατίθενται στα επόμενα βήματα του αλγορίθμου.Ο δεύτερος αλγόριθμος (Υ. Kopidakis, L. Lamari και V. Zissimopoulos) [KLZ], είναι ένας νέος ευρετικός αλγόριθμος ο οποίος είτε ομαδοποιεί τις εργασίες, είτε τις αναθέτει στους διαθέσιμους επεξεργαστές, βασιζόμενος σε μία ακμή μεγίστου βάρους ενός τροποποιημένου γράφου. Ο τροποποιημένος αυτός γράφος προκύπτει εάν αναθεωρήσουμε το πρόβλημα: Αντί της ελαχιστοποίησης του συνολικού κόστους επικοινωνίας και του συνολικού κόστους εκτελέσεως, προσπαθούμε να δούμε το πρόβλημα, ως ένα πρόβλημα μεγιστοποίησης. Βάσει της λογικής αυτής, ο σκοπός επικεντρώνεται στην αποφυγή μεγάλων επικοινωνιακών κοστών μεταξύ εργασιών και, αναποτελεσματικών αναθέσεων. Δηλαδή, αντί ο αλγόριθμος αυτός να ψάχνει πως θα προσδιορίσει τις καλλίτερες, εξ απόψεως κοστών εκτελέσεως και επικοινωνίας, αναθέσεις, προσπαθεί να αποφύγει τα υψηλά κόστη επικοινωνίας και εκτελέσεως.Ο τρίτος αλγόριθμος (I. Milis) [MM], είναι επίσης ένας ευρετικός αλγόριθμος, ο οποίος καταλήγει σε μία πλήρη ανάθεση εργασιών στους διαθέσιμους επεξεργαστές. Εν αντιθέσει με τους αλγορίθμους μερικής ανάθεσης, ο αλγόριθμος αυτός βασίζεται στην ιδέα της πλήρους ανάθεσης των εργασιών στους διαθέσιμους επεξεργαστές, σε κάθε βήμα εκτέλεσης του.Και οι τρεις αλγόριθμοι υλοποιήθησαν σε γλώσσα προγραμματισμού Pascal (σε σύστημα Open VMS ver.6.2. Kronos, στον Alpha Server 1000 του Κέντρου Υπολογιστών του Οικονομικού Πανεπιστημίου Αθηνών) και συνεκρίθησαν μεταξύ τους, ως προς τα κόστη ανάθεσης. Τα αποτελέσματα των συγκρίσεων αυτών και εν γένει της μελέτης αυτής, εμπεριέχονται στο 5° Κεφάλαιο της εργασίας αυτής, όπου ευρίσκονται τα δεδομένα του προβλήματος, οι πίνακες, τα διαγράμματα και τα τελικά μας συμπεράσματα.Τελειώνοντας, θα πρέπει να αναφερθεί ότι το πρόβλημα της ανάθεσης των εργασιών ενός κατανεμημένου συστήματος στους διαθέσιμους επεξεργαστές του, εντάσσεται στο γενικότερο πλαίσιο της βέλτιστης χρήσης των πόρων του συστήματος αυτού. Εντός του πλαισίου αυτού, πρέπει να ληφθεί υπ’ όψιν και ένα πλήθος άλλων παραγόντων, όπως και κάποιοι άλλοι περιορισμοί τους οποίους δεν συμπεριέλαβε η μελέτη αυτή.

Λέξη κλειδί :	Ευρετικοί αλγόριθμοι Λειτουργικό σύστημα Λογισμικό Αλγόριθμοι Επεξεργασία δεδομένων Κατανεμημένα συστήματα Heuristic algorithms Data processing Distributed systems

Ημερομηνία έκδοσης :	28-02-2001

Άδεια χρήσης :

Αρχείο: Vatrikas_2001.pdf

Τύπος: application/pdf

Είσοδος