Θέματα Ατομικής Διπλωματικής Εργασίας

Ακαδημαϊκό Έτος 2009/2010

Επίκουρος Καθηγητής Χρύσης Γεωργίου

Θέμα 1: Προσδιορισμός και Προσομοίωση Χρονισμένων Κατανεμημένων Αλγορίθμων με το Εργαλείο Tempo/TIOA

H ΤΙΟΑ είναι μια γλώσσα προγραμματισμού και μοντελοποίησης βασισμένη στο μοντέλο Timed Input/Output Automata, και είναι ιδιαίτερα κατάλληλη για την περιγραφή και προγραμματισμό χρονισμένων κατανεμημένων αλγορίθμων, δηλαδή αλγορίθμων που η λειτουργία τους βασίζεται έως κάποιο βαθμό σε προθεσμίες-βάσει-χρόνου (timed-based timeouts). Βάσει της γλώσσας αυτής έχει αναπτυχθεί (από την VeroModo Inc) ένα πακέτο εργαλείων (Tempo) το οποίο παρέχει τη δυνατότητα προδιαγραφής και προσομοίωσης χρονισμένων κατανεμημένων αλγορίθμων.

Σκοπός αυτής της διπλωματικής εργασίας είναι η εκμάθηση της γλώσσας ΤIOA και του εργαλείου Tempo και ο προσδιορισμός και η προσομοίωση επιλεγμένων χρονισμένων κατανεμημένων αλγορίθμων.

Προαπαιτούμενα: Πολύ καλή μαθηματική και αλγοριθμική ωριμότητα, και καλές προγραμματιστικές ικανότητες (Δεν προαπαιτείται παρακολούθηση μαθήματος Παράλληλων ή Κατανεμημένων Αλγορίθμων αλλά θα θεωρηθεί επιπλέον προσόν).

Θέμα 2: Υλοποίηση Παράλληλων Αλγορίθμων με το Επικοινωνιακό Πρωτόκολλο MPICH2

Το MPI είναι ένα πρότυπο επικοινωνίας που χρησιμοποιείται στον παράλληλο προγραμματισμό (δηλ. για την υλοποίηση παράλληλων αλγορίθμων). Το MPICH2 είναι μια πολυπλατφορμική υλοποίηση του MPI (MPI-1 και MPI-2). Υποστηρίζεται από πολλά λειτουργικά συστήματα (συμπεριλαμβανομένων Linux και Windows) και μπορεί να χρησιμοποιηθεί με τις γλώσσες προγραμματισμού C/C++ και FORTRAN77/90. Ουσιαστικά το MPICH2 παρέχει τις απαραίτητες βιβλιοθήκες και συναρτήσεις που επιτρέπουν την συγγραφή/μεταγλώττιση/εκτέλεση παράλληλων προγραμμάτων.

Σκοπός αυτής της διπλωματικής εργασίας είναι η αυτοδίδακτη εκμάθηση του MPICH2 και η χρήση του για την υλοποίηση επιλεγμένων παράλληλων αλγορίθμων.

Προαπαιτούμενα: Αλγοριθμική ωριμότητα, καλές προγραμματιστικές ικανότητες σε C και βασικός χειρισμός λειτουργικού συστήματος unix/windows (ικανότητα εγκατάστασης και χρήση νέου λογισμικού). Θα δοθεί προτεραιότητα σε φοιτητές που έχουν παρακολουθήσει το μάθημα ΕΠΛ431 – Σύνθεση Παράλληλων Αλγορίθμων (ή άλλα μαθήματα παράλληλου υπολογισμού/προγραμματισμού), όπου μελετούνται σε βάθος διάφοροι παράλληλοι αλγόριθμοι και γενικότερα οι βασικές έννοιες του παράλληλου υπολογισμού.

Θέμα 3: Προσομοίωση Παράλληλων Αλγορίθμων στο Περιβάλλον XMT

Το PRAM είναι πιθανότατα το πιο δημοφιλή «αλγοριθμικό» μοντέλο παράλληλου υπολογισμού που επιτρέπει την σχεδίαση και ανάλυση παράλληλων αλγορίθμων. Το XMT (eXplicit Mutli-Threading) είναι ένας προσομοιωτής που επιτρέπει την εκτέλεση PRAM αλγορίθμων σε σειριακούς υπολογιστές. Ο προσομοιωτής βασίζεται σε μια απλή επέκταση της γλώσσας προγραμματισμού C (που ονομάζεται XMTC) και υποστηρίζεται από πολλά λειτουργικά συστήματα (συμπεριλαμβανομένων Linux και Windows).

Σκοπός αυτής της διπλωματικής εργασίας είναι η προσομοίωση και πειραματική αξιολόγηση επιλεγμένων παράλληλων αλγορίθμων χρησιμοποιώντας τον προσομοιωτή ΧΜΤ. Αυτό συνεπάγει ουσιαστικά την αυτοδίδακτη εκμάθηση της (απλής) γλώσσας XMTC.

Προαπαιτούμενα: Αλγοριθμική ωριμότητα, καλές προγραμματιστικές ικανότητες σε C και βασικός χειρισμός λειτουργικού συστήματος unix/windows (ικανότητα εγκατάστασης και χρήση νέου λογισμικού). Θα δοθεί προτεραιότητα σε φοιτητές που έχουν παρακολουθήσει το μάθημα ΕΠΛ431 – Σύνθεση Παράλληλων Αλγορίθμων, όπου μελετείται σε βάθος το μοντέλο PRAM.

Θέμα 4: Προσομοίωση Μηχανισμών για Αξιόπιστο Διαδικτυακό Υπολογισμό

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

Σκοπός αυτής της διπλωματικής εργασίας είναι η δημιουργία γραφικής διεπαφής χρήστη (Graphical User Interface) και η προσομοίωση των μηχανισμό αυτών με χρήση της γλώσσας προγραμματισμού Java και του εργαλείου Java Swing. Αυτό συνεπάγει την μελέτη των μηχανισμών αξιόπιστου Διαδικτυακού υπολογισμού και την αυτοδίδακτη εκμάθηση του εργαλείου Java Swing.

Προαπαιτούμενα: Καλή μαθηματική και αλγοριθμική ωριμότητα, πολύ καλές προγραμματιστικές ικανότητες σε Java.

Θέμα 5: Υλοποίηση και Πειραματική Αξιολόγηση Αλγορίθμων Κατανεμημένης Αποθήκευσης στο PlanetLab

Το PlanetLab είναι ένα παγκοσμίας κλίμακας δίκτυο υπολογιστών που υποστηρίζει την ανάπτυξη και διάχυση νέων δικτυακών και διαδικτυακών υπηρεσιών. Την παρούσα στιγμή το δίκτυο αυτό περιέχει πέρα των 950 υπολογιστικών κόμβων οι οποίοι είναι κατανεμημένοι σε πέρα των 480 ακαδημαϊκών και ερευνητικών ιδρυμάτων. Το τμήμα Πληροφορικής, μέσω του Εργαστηρίου HPCL, συμμετέχει σε αυτό το δίκτυο με δύο υπολογιστικούς κόμβους.

Σκοπός αυτής της διπλωματικής εργασίας είναι η μελέτη και εξοικείωση με το PlanetLab και η υλοποίηση και η πειραματική αξιολόγηση επιλεγμένων αλγορίθμων κατανεμημένης αποθήκευσης στο δίκτυο αυτό με τη χρήση προγραμματισμού υποδοχών (Socket Programming). Αυτό συνεπάγει την αυτοδίδακτη εκμάθηση προγραμματισμού υποδοχών (C ή Java Sockets).

Προαπαιτούμενα: Βασική γνώση χειρισμού του λειτουργικού συστήματος unix και πολύ καλές προγραμματιστικές ικανότητες σε C/C++ ή Java. (Δεν προαπαιτείται παρακολούθηση μαθήματος Παράλληλων ή Κατανεμημένων Αλγορίθμων ή Προγραμματισμού Συστημάτων, αλλά θα θεωρηθεί επιπλέον προσόν).