Ομιλία

Κατανεμημένα Αντικείμενα - Πολυνηματικοί Υπολογισμοί
18.11.2005
Ομιλητής: Παναγιωτα Φατουρου, Πανεπιστήμιο Ιωαννίνων
Ημερομηνία: Παρασκευή 18 Νοεμβρίου, 2005 Ώρα: 15:00 - 16:30
Τοποθεσία: Αίθουσα Μεσογειακών Σπουδών
Host:

Abstract:

Θα παρουσιαστεί ερευνητική εργασία που αφορά αλγορίθμους που υλοποιούν χρήσιμα αλλά πολύπλοκα κατανεμημένα αντικειμένα (distributed objects), όπως είναι τα ατομικά στιγμιότυπα μνήμης (atomic snapshots), χρησιμοποιώντας άλλα απλούστερα διαμοιραζόμενα αντικείμενα (όπως π.χ., καταχωρητές). Πιο συγκεκριμένα, θα συζητηθούν τα εξής αποτελέσματα που έχουμε αποδείξει (STOC'03) για την ανάλυση τέτοιων αλγορίθμων: (1) ένα αυστηρό κάτω όριο στην χρονική πολυπλοκότητα χωρικά-βέλτιστων υλοποιήσεων ατομικών στιγμιοτύπων πολλαπλής εγγραφής (multi-writer snapshot objects), (2) ένα κάτω όριο στην χρονική πολυπλοκότητα υλοποιήσεων ατομικών στιγμιοτύπων πολλαπλής-εγγραφής που χρησιμοποιούν επιπλέον του ελάχιστου αριθμού καταχωρητών πολλαπλής εγγραφής (multi-writer registers) και οποιοδήποτε αριθμό καταχωρητών απλής εγγραφής (single-writer registers), και (3) κάτω όρια στον απαιτούμενο αριθμό καταχωρητών πολλαπλής εγγραφής σε κάθε περίπτωση.

Θα παρουσιαστούν επίσης αλγόριθμοι χρονοδρομόλογησης πολυνηματικών υπολογισμών (multithreaded computations ή MTCs) σε κατανεμημένα και παράλληλα συστήματα και πιο συγκεκριμένα οι ακόλουθοι αλγόριθμοι που έχουμε προτείνει και αναλύσει (SPAA `01, Information & Computation): (1) ένας αλγόριθμος χρονοδρομολόγησης MTCs με τυχαιότητα, που έχει αποδεδειγμένα καλή χρονική & χωρική πολυπλοκότητα για μια γενική κλάση υπολογισμών που ονομάζονται χαλαρά-αυστηροί υπολογισμοί (strict MTCs) και (2) ένας αλγόριθμος χρονοδρομολόγησης πολυνηματικών υπολογισμών με μεταβλητές συγχρονισμού μοναδικής εγγραφής (write-once synchronization variables), που συνδυάζει αποτελεσματικές τεχνικές δρομολόγησης, όπως εκείνες της κλοπής εργασίας (work-stealing) & της δρομολόγησης κατά βάθος (depth-first scheduling), προκειμένου να επιτύχει καλή χρονική και χωρική πολυπλοκότητα. Οι αλγόριθμοι αυτοί βελτιώνουν έναντι όλων των δημοσιευμένων αλγορίθμων στην περιοχή (FOCS'94, JACM'99, SPAA'95, SPAA'97, SPAA'99, JACM'99) γιατί δουλεύουν αποτελεσματικά για πιο γενικούς υπολογισμούς και επιτυγχάνουν καλύτερη τοπικότητα και χαμηλότερο κόστος συμφόρησης.

Bio:

Βασικές Σπουδές στο Πανεπιστήμιο Κρήτης (Πτυχίο Επιστήμης Υπολογιστών, 1995), μεταπτυχιακές σπουδές στο Πανεπιστήμιο Πατρών (Ph.D. στην Πληροφορική, 1999). Εργάσθηκε ως μεταδιδακτορικός ερευνήτρια στο Max-Planck Institute fuer Informatik, Saarbruecken, Germany (1999-2001), και στο Τμήμα Επιστήμης Υπολογιστών (Computer Science Department) του Πανεπιστημίου του Τορόντο (2001). Το ακαδημαϊκό έτος 2001-2002 κατείχε θέση διδάσκουσας βάσει του Π.Δ. 407/1980 στο Τμήμα Πληροφορικής του Πανεπιστημίου Ιωαννίνων. Το 2002 εξελέγη Λέκτορας στο Τμήμα Πληροφορικής του Πανεπιστημίου Ιωαννίνων όπου εργάζεται μέχρι σήμερα. Τα ερευνητικά της ενδιαφέροντα εστιάζονται στους χώρους της κατανεμημένης και παράλληλης επεξεργασίας και των δικτύων των υπολογιστών.

© Copyright 2007 FOUNDATION FOR RESEARCH & TECHNOLOGY - HELLAS, All rights reserved.