Γενικές Πληροφορίες

Γενικά

Διδάσκουσα: Παναγιώτα Φατούρου
Γραφείο: 215 (Λευκά Κτίρια Α' όροφος)
Ώρες Γραφείου: Τετάρτη: 11:00 - 13:00, Πέμπτη: 15:00 - 17:00
Ηλεκτρονική Διεύθυνση:
Τηλέφωνο: +30 2810 393549
Βοηθός Μαθήματος: Ελευθέριος Κοσμάς
Γραφείο Βοηθού: Εργαστήριο Μεταπτυχιακών, Υπόγειο Λευκών Κτιρίων
Ώρες Γραφείου Βοηθού: Τρίτη, 19:00-20:00 (οι ώρες γραφείου βοηθού θα πραγματοποιούνται μόνο όταν ζητείται απο τους φοιτητές μέσω ηλεκτρονικού μηνύματος στο λογαριασμό του μαθήματος).
Ηλεκτρονική Διεύθυνση Μαθήματος:
Θεματική Περιοχή: Ζ, Γ, Ε08
Διδακτικές Μονάδες: 4

Ώρες και Αίθουσες Διδασκαλίας

Δευτέρα, 17:00-19:00, στην αίθουσα ΡΑ201. Τετάρτη, 17:00-19:00, στην αίθουσα ΡΑ201.

Σύνοψη Μαθήματος

Η τρέχουσα γενιά επεξεργαστών, αδυνατώντας να μειώσει περαιτέρω την ταχύτητα των ρολογιών, παρέχει αυξημένο παραλληλισμό χρησιμοποιώντας πολλαπλούς επεξεργαστές. Οι κορυφαίες εταιρείες στο χώρο (Intel, AMD) έχουν ήδη παράγει τις πρώτες γενιές πολυπύρηνων επεξεργαστών, ενώ έχουν επίσης αναγγείλει τη δημιουργία επεξεργαστών με ακόμη περισσότερους πυρήνες. Έτσι, πολυεπεξεργαστές έχουν αρχίσει να κατακλύζουν τα γραφεία και τις επιχειρήσεις και συναντιούνται σήμερα σε όλους τους υπολογιστές, από τους κλασικούς προσωπικούς υπολογιστές μέχρι τους φορητούς και ίσως σύντομα να τους βρούμε ακόμη και στα κινητά τηλέφωνα. Ο προγραμματισμός πολυεπεξεργαστικών συστημάτων και η ανάπτυξη κατανεμημένων πολυνηματικών εφαρμογών που θα εκτελούνται αποδοτικά σε αυτούς, είναι επομένως κρίσιμης σημασίας. Ωστόσο, είναι κοινά αποδεκτό ότι ο προγραμματισμός τέτοιων μηχανών είναι ένα δύσκολο εγχείρημα που συνήθως αποτολμάται μόνο από ειδικούς. Η μεγαλύτερη δυσκολία έγκειται στη σχεδίαση αποτελεσματικών κατανεμημένων αλγορίθμων και δομών δεδομένων. Η δυσκολία αυτή πηγάζει από την ανάγκη επίτευξης συγχρονισμού μεταξύ των διεργασιών που εκτελούνται ταυτόχρονα στο σύστημα. Ωστόσο, ανεξάρτητα από τη δυσκολία αυτή, όλες οι σύγχρονες εφαρμογές πρέπει να βασιστούν σε κάποιου είδους παραλληλισμό προκειμένου να βελτιώσουν την απόδοσή τους και να εκμεταλλευτούν πλήρως την υπολογιστική ισχύ των πολυπύρηνων αρχιτεκτονικών.

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

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

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

Το μάθημα επιτρέπεται να παρακολουθήσουν μεταπτυχιακοί και προχωρημένοι προπτυχιακοί φοιτητές. Η επιτυχής διεκπεραίωσή του περιλαμβάνει την εκτέλεση δύο ερευνητικών εργασιών (projects) ατομικά από κάθε φοιτητή, την επίλυση γραπτών ασκήσεων (homework assignments) και την συγγραφή σύντομων γραπτών αναφορών για κάποιες εργασίες που θα επιλέγονται από τον/την διδάσκοντα/διδάσκουσα.

Πρόγραμμα

Εβδομάδα1 Θέμα
1η Εισαγωγή – Κλασικά θέματα και προβλήματα συγχρονισμού
2η Αμοιβαίος Αποκλεισμός
3η Πρακτικά Ζητήματα: Εμβέλεια κλειδωμάτων, ανταγωνισμός & άλλες σημαντικές παράμετροι της απόδοσης
4η Πρακτικά Ζητήματα: Αλγόριθμοι συγχρονισμού που απαιτούν μικρό πλήθος απομακρυσμένων προσβάσεων σε κατανεμημένη διαμοιραζόμενη μνήμη
5η Η τεχνική της επικάλυψης μεταβλητών στην απόδειξη κάτω φραγμάτων και αρνητικών αποτελεσμάτων στον κατανεμημένο υπολογισμό
6η Διαμοιραζόμενα αντικείμενα – Ορθότητα, πρόοδος και αποδοτικότητα
7η Θεμελιώσεις κοινόχρηστης μνήμης: Προσομοιώσεις πολύπλοκων ατομικών αντικειμένων από απλούστερα αντικείμενα
8η Θεμελιώσεις κοινόχρηστης μνήμης: Ατομικά Στιγμιότυπα Μνήμης
9η Η δύναμη προσομοίωσης θεμελιακών μηχανισμών συγχρονισμού
10η Κλασικές διαμοιραζόμενες δομές δεδομένων (συνδεδεμένες λίστες, ουρές, κλπ.)
11η Μέτρηση και Ταξινόμηση
12η Ανταγωνισμός - Προσαρμοστικοί αλγόριθμοι
13η Προσομοίωση μνήμης βάσει χρήσης δοσοληψιών

Εργασίες και Βαθμολόγηση

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

Οι εργασίες του μαθήματος συμπεριλαμβάνουν τη μελέτη τριών ερευνητικών εργασιών, την κατανόησή τους σε βάθος, τη συγγραφή αναφοράς που θα περιγράφει τα βασικότερα σημεία των εργασιών αυτών και την παρουσίαση αυτών στην τάξη. Η προκαταρκτική εργασία αποσκοπεί στην παροχή σχολίων από τον διδάσκοντα και τους βοηθούς και δεν βαθμολογείται (παρότι είναι υποχρεωτική). Οι φοιτητές θα πρέπει να λάβουν υπ’ όψιν στην προετοιμασία της τελικής εργασίας όλα τα σχόλια του διδάσκοντα πάνω στην προκαταρτική εργασία τους.

Ο τελικός βαθμός στο μάθημα υπολογίζεται βάσει της απόδοσης των φοιτητών στις σειρές των θεωρητικών ασκήσεων και στις σύντομες αναφορές εργασιών, στην ομαλή διεκπεραίωση των ερευνητικών εργασιών και στην απόδοση του φοιτητή στην τάξη.

Λίστα Ηλεκτρονικού Ταχυδρομείου & Λογαριασμός Μαθήματος

Για το μάθημα υπάρχει e-mailing λίστα η οποία θα χρησιμοποιείται για την αποστολή e-mail σε όλους τους φοιτητές που έχουν δηλώσει το μάθημα. Για την εγγραφή στη λίστα απαιτείται η αποστολή ενός ηλεκτρονικού μηνύματος (e-mail) στη διεύθυνση::

με κενό θέμα και σώμα:

Η εγγραφή στη λίστα είναι υποχρεωτική. Όποιος φοιτητής δεν εγγραφεί στη λίστα, δεν θα λαμβάνει τα e-mails που αποστέλλονται και δεν θα γνωρίζει σημαντικά θέματα που αφορούν το μάθημα. Το e-mail address της λίστας είναι:

Όλα τα e-mails προς αυτή τη διεύθυνση θα λαμβάνονται από όλους τους φοιτητές που έχουν εγγραφεί στη λίστα. Οι φοιτητές υποχρεούνται να εξετάζουν καθημερινά το e-mail τους ώστε να ενημερώνονται έγκαιρα για τα μηνύματα που αποστέλλονται στη λίστα. Οι φοιτητές υποχρεούνται να εγγραφούν στη λίστα μέχρι τις 10/10.

Για το μάθημα υπάρχει επίσης λογαριασμός στον οποίο οι φοιτητές μπορούν να στέλνουν ηλεκτρονικά μηνύματα με τις απορίες τους. Η ηλεκτρονική διεύθυνση του λογαριασμού είναι:

Προαπαιτούμενα

Για τη δήλωση του μαθήματος ΗΥ586 είναι προαπαιτούμενο το μάθημα ΗΥ380 - Αλγόριθμοι και Πολυπλοκότητα. Οι φοιτητές που δεν έχουν διεκπεραιώσει επιτυχώς το μάθημα αυτό δεν έχουν το υπόβαθρο που απαιτείται για να επιτύχουν στο μάθημα.

Προτεινόμενη Βιβλιογραφία