ΛΙΣΤΑ ΚΟΙΝΟΠΟΙΗΣΕΩΝ ΣΤΗ ΦΙΛΟΣΟΦΙΚΗ ΣΧΟΛΗ

ΘΕΜΑ: prosklhsh dhmosia parousiash Didaktorikhs Diatrivhs_ Kosmas Eleftherios_19/12/2014_ 17:00_ K206_ dept. Computer Science UoC- oral defense of PhD by Kosmas Eleftherios _Friday 19 December, 17-19 (GR)

ΑΠΟΣΤΟΛΕΑΣ: Gramateia Metaptyxiakou CSD [mailto:pgram@xxxxxxxxxx]

Πρόσκληση σε Δημόσια Παρουσίαση της Διδακτορικής Διατριβής του

κ. Kοσμάς Ελευθέριος

Την Παρασκευή, 19 Δεκεμβρίου 2014 και ώρα 17:00 στην αίθουσα Τηλεδιάσκεψης Κ206 του Τμήματος Επιστήμης Υπολογιστών του Πανεπιστημίου Κρήτης στο Ηράκλειο, θα γίνει η δημόσια παρουσίαση και υποστήριξη της Διδακτορικής Διατριβής του υποψηφίου διδάκτορος του Τμήματος Επιστήμης Υπολογιστών κ. Κοσμά με θέμα:

“ Τεχνικές ενίσχυσης παραλληλισμού για μηχανισμούς αυτόματης εκτέλεσης σειριακού κώδικα σε περιβάλλοντα παραλληλισμού ”

“Techniques for Enhancing Parallelism in Mechanisms that Automatically Execute Sequential Code in Concurrent Environments”

ΠΕΡΙΛΗΨΗ

Δύο γνωστοί μηχανισμοί αυτόματης εκτέλεσης σειριακού κώδικα σε περιβάλλοντα παραλληλισμού είναι τα καθολικά αντικείμενα (universal constructions) και ο συγχρονισμός διεργασιών μέσω δοσοληψιών (software transactional memory ή STM). Και οι δύο μηχανισμοί έχουν ως στόχο να απλουστεύουν τη διαδικασία του παράλληλου προγραμματισμού.

Σε αυτή την εργασία, μελετώνται μέθοδοι επίτευξης αυξημένου παραλληλισμού κατά τη σχεδίαση τέτοιων μηχανισμών, χωρίς να θυσιάζεται η ορθότητα και η πρόοδος. Μια καλά μελετημένη τεχνική για την ενίσχυση του παραλληλισμού είναι η εξασφάλιση μιας ιδιότητας που ονομάζεται παραλληλία αποσπασματικής προσπέλασης (disjoint-access parallelism ή dap). Σε αυτή την εργασία, αποδεικνύουμε ότι είναι αδύνατο να σχεδιαστούν τέτοιοι μηχανισμοί που να ικανοποιούν ταυτόχρονα την παραλληλία αποσπασματικής προσπέλασης και μια ισχυρή ιδιότητα προόδου που είναι γνωστή ως ελευθερία αναμονής (wait-freedom), για κάθε δομή δεδομένων.

Για δομές δεδομένων οι οποίες έχουν ένα άνω όριο στο πλήθος των δεδομένων που κάθε λειτουργία τους μπορεί να προσπελάσει, σε οποιαδήποτε εκτέλεση, παρουσιάζουμε ένα καθολικό αντικείμενο, το οποίο ονομάζεται DAP-UC, που ικανοποιεί την παραλληλία αποσπασματικής προσπέλασης και την ελευθερία αναμονής. Επιπλέον, προτείνουμε και μελετούμε ασθενέστερες εκδοχές της ιδιότητας παραλληλία αποσπασματικής προσπέλασης, οι οποίες εξακολουθούν ωστόσο να επιτυγχάνουν αυξημένο παραλληλισμό. Συγκεκριμένα, παρουσιάζουμε ένα καθολικό αντικείμενο που εξασφαλίζει την ελευθερία αναμονής καθώς και μία νεοεισαχθείσα ιδιότητα παραλληλίας αποσπασματικής προσπέλασης, για μεγαλύτερο πλήθος δομών δεδομένων από αυτό που υποστηρίζεται από τον DAP-UC.

Τέλος, μελετήσαμε σημαντικά θέματα για την επίτευξη αυξημένου παραλληλισμού στο μηχανισμό STM. Προτείνουμε τον STM αλγόριθμο WFR-ΤΜ, o οποίος εξασφαλίζει ισχυρή πρόοδο για τις δοσοληψίες που ποτέ δεν τροποποιούν τα δεδομένα της δομή δεδομένων. Αυτό επιτυγχάνεται χωρίς να μειώνεται ο παραλληλισμός που επιτυγχάνεται από τους αισιόδοξους STM αλγορίθμους, μεταξύ των δοσοληψιών που ενημερώνουν τα δεδομένα της δομή των δεδομένων. Ακόμη, προτείνουμε τον STM αλγόριθμο SemanticTM, ο οποίος, για πρώτη φορά στο μηχανισμό STM, επιτυγχάνει παραλληλισμό σε επίπεδο εντολών δοσοληψιών. Αυτό σημαίνει ότι όχι μόνο οι δοσοληψίες αλλά και οι πράξεις της κάθε δοσοληψίας μπορούν να εκτελεστούν παράλληλα. Ο αλγόριθμος SemanticTM εξασφαλίζει την ισχυρή πρόοδο για απλές λειτουργίες, χωρίς να αποτυγχάνουν οι δοσοληψίες. Σημειώνεται ότι οι STM αλγόριθμοι που ποτέ δεν επανεκκινούν δοσοληψίες είναι ιδιαίτερα επιθυμητοί, δεδομένου ότι υποστηρίζουν δοσοληψίες που εκτελούν αμετάκλητες εντολές, π.χ. εντολές εισόδου/εξόδου.

Επόπτης: Επικ. Καθηγήτρια, Παναγιώτα Φατούρου

ABSTRACT

Two well-known mechanisms for automatically executing sequential code segments in a concurrent environment are universal constructions and software transactional memory (STM). They both have the same goal of simplifying the task of parallel programming.

In this thesis, we study how to achieve increased concurrency while designing such mechanisms without sacrificing correctness and progress. One well-studied technique for enhancing concurrency is ensuring a property called disjoint-access parallelism (dap). In this thesis, we prove that it is not possible for such mechanisms to achieve both disjoint-access parallelism and strong progress guarantees for data structures whose operations may access an unbounded number of pieces of data.

For data structures that have a bound on the number of pieces of data accessed by each operation they support, we present a universal construction, called DAP-UC, that ensures both disjoint-access parallelism and strong progress. We further introduce and study weaker versions of disjoint-access parallelism, which still however allow for increased parallelism. Specifically, we present a universal construction that ensures strong progress and a newly introduced dap property, for more classes of data structures than those supported by DAP-UC.

We finally study important issues in achieving enhanced parallelism in STM computing. We introduce WFR-TM, an STM algorithm which ensures strong progress for read-only transactions, i.e. transactions that never update the data structure. Ensuring this property is highly desirable for read-intensive workloads. In WFR-TM, this is achieved without reducing the parallelism provided to update transactions in optimistic STM systems. We also introduce SemanticTM, an STM algorithm which is the first to achieve parallelism at the level of transactionsʼ instructions. This means that not only the transactions themselves but also the instructions of each transaction may be executed concurrently. SemanticTM guarantees strong progress for simple transactions without ever causing any aborts. STM algorithms that never restart transactions are highly desirable since they support transactions that contain irrevocable instructions, e.g. I/O instructions.

Supervisor: Assistant Professor, Panagiota Faturu

Panagiotis Tsakalides

Chairman

Department of Computer Science

--

Postgraduate Secretariat

Computer Science Department

Voutes University Campus

Heraklion, Crete

GR-70013, Greece

tel: + 30 2810 393592, 393504

fax:+ 30 2810 393804

e-mail: pgram@xxxxxxxxxx

Url: http://www.csd.uoc.gr