Techniques for enhancing parallelism in mechanisms that automatically execute sequential code in concurrent environments

Abstract

Two well-known mechanisms for automatically executing sequential code segments in aconcurrent environment are universal constructions and software transactional memory.They both have the same goal of simplifying the task of parallel programming. A universalconstruction is a mechanism which takes as input the sequential code and executes itin a concurrent environment. Software transactional memory (STM) employs transactionsto avoid conflicting accesses to common data (known as data items or transactional variables).A transaction may either commit, in which case it appears as if it has been executedat a single point in time, or abort, in which case it appears as if it is never executed. Noticethat if a transaction commits, then its updates to data items become visible, otherwise, if itaborts, all its changes are discarded.In this thesis, we study how to achieve increased concurrency while designing suchmechanisms, without sacrificing correctness and progress. One well-studied technique forenhancing concurrency is ensuring a property called disjoint-access parallelism. Roughlyspeaking, disjoint-access parallelism guarantees that processes operating on different partsof an implemented object do not interfere with each other. Thus, disjoint-access parallelimplementations allow for increased parallelism.Wait-freedom is a well-known progress property which ensures that each process completesits execution, even when other processes run at arbitrary speeds or crash. Waitfreedomis highly desirable because implementations ensuring this property are highly faulttolerantand usually ensure bounds on the number of steps executed before an implementedoperation responds.In this thesis, we prove that it is not possible for a universal construction to achieveboth disjoint-access parallelism and wait-freedom; this impossibility result holds for STMas well. Specifically, we identify a natural property of universal constructions and provethat there is no universal construction (with this property) that ensures both disjoint-access parallelism and wait-freedom. Our impossibility proof is obtained by considering a dynamicdata structure that can grow arbitrarily large during an execution. This impossibility resultcan be beaten if we focus on data structures that have a bound on the number of piecesof data accessed by each operation they support. For this setting, we present a universalconstruction that ensures both wait-freedom and disjoint-access parallelism.We further introduce and study weaker versions of disjoint-access parallelism, whichstill however allow for increased parallelism. Motivated be the way current STM algorithmwork, we introduce timestamp-ignoring disjoint-access parallelism, which allows operationsoperating on different parts of an implemented data structure to proceed in parallel,except for accesses to a timestamp object. A timestamp object allows a process to know the“time” at which it accesses the object, relative to accesses by other processes (on the sametimestamp object); specifically, a process is able to determine whether it accessed the objectbefore or after some other process accessed it. We present a universal construction that ensures wait-freedom and timestamp-ignoring disjoint-access parallelism, for certain classesof data structures.We next concentrate on important issues in achieving enhanced parallelism in STMcomputing. Most STM algorithms employ an optimistic approach, where transactions areexecuted speculatively, as if they will never read inconsistent data. When a conflict occurs,STM algorithms usually abort one of the transactions to ensure correctness; two concurrenttransactions conflict if they both access the same data item and at least one of themattempts to modify it. The work performed by a transaction that aborts is discarded and itis later re-executed as a new transaction; this incurs a performance penalty. Moreover, forread-intensive workloads, it is really important to ensure that transactions that never updatea data item (which are called read-only transactions) never abort and are wait-free; i.e. theyalways commit within a finite number of steps. For these reasons, the literature also contains pessimistic STM algorithms, which never abort transactions and support wait-freedom for read-only transactions. However, most of them achieve this by “pessimistically” requiring transactions that update data items (called update transactions) to be executed sequentially. This significantly restricts parallelism in many cases and therefore it also leads to performance degradation.As a first step towards achieving enhanced parallelism, we introduce WFR-TM, an STMalgorithm which attempts to combine some of the advantages of pessimistic and optimisticSTM. In WFR-TM, as in pessimistic STMs, read-only transactions never abort and are wait-free. WFR-TM additionally ensures that read-only transactions never execute expensivesynchronization instructions. In contrast to pessimistic STMs, these properties areachieved without sacrificing all parallelism between update transactions. More specifically,update transactions use a pessimistic approach to synchronize with concurrently executedread-only transactions: they wait for read-only transactions to complete. However, they usean optimistic approach to synchronize with each other: they are executed concurrently ina speculative way, and they commit if they have not encountered any conflict with otherupdate transactions during their execution. Thus, WFR-TM achieves more parallelism thanpessimistic STMs.Finally, we introduce SemanticTM, an STM algorithm in which parallelism is achievedat the level of transactional instructions; i.e. not only the transactions themselves but alsothe instructions of each transaction may be executed concurrently. With compiler support,SemanticTM guarantees that simple transactions are wait-free, by ensuring that no transactions conflict. We remark that STM algorithms that never abort transactions are highly desirable since they additionally support transactions that perform irrevocable operations, e.g. I/O operations.

Μέχρι πρόσφατα, η αύξηση της συχνότητας του επεξεργαστή αποτελούσε την κυρίαρχη τεχνική για τη βελτίωση της απόδοσής του. Ωστόσο, τα τελευταία χρόνια, φυσικοί περιορισμοί μικροηλεκτρονικής φύσης δεν επιτρέπουν την περαιτέρω αύξηση της συχνότητας του επεξεργαστή. Η συνεχόμενη ανάγκη των σύγχρονων εφαρμογών για αυξημένη επεξεργαστική ισχύ οδήγησε τους μεγαλύτερους κατασκευαστές επεξεργαστών στη σχεδίαση πολυπύρηνων αρχιτεκτονικών, όπου πολλαπλές επεξεργαστικές μονάδες ή πυρήνες εμπεριέχονται στον ίδιο επεξεργαστή.Σε επίπεδο λογισμικού, χρησιμοποιούμε τον όρο διεργασία για να αναφερθούμε στη συνάρτηση που εκτελείται σε κάποιο πυρήνα και αναλαμβάνει να εκτελέσει την ακολουθία εντολών που καταφθάνουν σε αυτόν τον πυρήνα. Οι διεργασίες αυτές μοιράζονται μία κοινή ή διαμοιραζόμενη μνήμη, στην οποία διατηρούνται τα δεδομένα της εκάστοτε εφαρμογής. Επίσης, οι διεργασίες ενδέχεται να σφάλλουν, δηλαδή να σταματήσουν να λειτουργούν οποιαδήποτε χρονική στιγμή.Οι εφαρμογές μπορούν να ευεργετηθούν από τις πολυπύρηνες αρχιτεκτονικές εάν ο κώδικας τους γραφτεί με τέτοιο τρόπο ώστε τμήματά τους να εκτελούνται παράλληλα από διαφορετικές διεργασίες. Ιδανικά η αύξηση της απόδοσης της εφαρμογής θα ήταν γραμμική ως προς το πλήθος των πυρήνων. Ωστόσο, αυτή η αύξηση επιτυγχάνεται μόνο σε εξαιρετικές περιπτώσεις εφαρμογών. Συνήθως τα διαφορετικά τμήματα μιας εφαρμογής αλληλοεξαρτώνται, επιβάλλοντας έτσι την ανάγκη επίτευξης συγχρονισμού μεταξύ των διεργασιών κατά την προσπέλαση διαμοιραζόμενων δεδομένων. Όμως είναι κοινά αποδεκτό ότι η ανάπτυξη παράλληλων προγραμμάτων επιτυγχάνοντας ταυτόχρονα συγχρονισμό και υψηλή απόδοση, είναι μια δύσκολη διαδικασία, η οποία γίνεται κυρίως από έμπειρους προγραμματιστές. Έχοντας ως κύριο στόχο την απλοποίηση της διαδικασίας παράλληλου προγραμματισμού, στην παρούσα διατριβή μελετούμε δύο γενικούς μηχανισμούς που αυτοματοποιούν τη διαδικασία ανάπτυξης παράλληλων προγραμμάτων, υποστηρίζοντας την εκτέλεση οποιουδήποτε σειριακού κώδικα σε ένα πολυπύρηνο επεξεργαστή. Συγκεκριμένα μελετούμε τα καθολικά αντικείμενα (universal constructions ή UC) και την τεχνική συγχρονισμού διεργασιών μέσω δοσοληψιών (software transactional memory ή STM).Ένα UC σύστημα αναλαμβάνει να εφαρμόσει ατομικά έναν σειριακό κώδικα στα δεδομένα της εφαρμογής που διατηρούνται στη διαμοιραζόμενη μνήμη. Από την άλλη, ένα STM σύστημα επιχειρεί να εκτελέσει ατομικά έναν σειριακό κώδικα ως μία δοσοληψία, η οποία μπορεί να καταλήξει είτε ως επιτυχής, καθιστώντας όλες τις αλλαγές που εφάρμοσε στη διαμοιραζόμενη μνήμη ορατές στις υπόλοιπες δοσοληψίες, είτε ως μη-επιτυχής, οπότε οι αλλαγές της αγνοούνται. Αυτή είναι και η βασική διαφορά των δύο αυτών τεχνικών.Μια εξαιρετικά επιθυμητή ιδιότητα για τη βελτίωση του παραλληλισμού είναι η παραλληλία αποσπασματικής προσπέλασης (disjoint access parallelism, ή DAP). Διαισθητικά, η ιδιότητα DAP απαιτεί από διαφορετικές διεργασίες που προσπελάζουν διαφορετικά τμήματα της διαμοιραζόμενης μνήμης να μην προκαλούν παρεμβολές η μία στην άλλη, έτσι ώστε να μπορούν να εκτελεστούν ταυτόχρονα. Μία ακόμη εξαιρετικά επιθυμητή ιδιότητα είναι η ιδιότητα προόδου ελευθερία-αναμονής, καθώς παρέχει πεπερασμένη χρονική πολυπλοκότητα και μέγιστη ανοχή σφαλμάτων. Συγκεκριμένα κάθε διεργασία εφαρμόζει τον σειριακό κώδικα που εκτελεί σε πεπερασμένο χρονικό διάστημα, ανεξάρτητα από τις αποτυχίες ή την ταχύτητα των υπόλοιπων διεργασιών.Ωστόσο, αποδεικνύουμε με αυστηρό τρόπο ότι είναι αδύνατο να σχεδιασθεί ένας UC ή STM αλγόριθμος που ικανοποιεί ταυτόχρονα τις ιδιότητες ελευθερία-αναμονής και DAP για οποιαδήποτε εφαρμογή. Η απόδειξή μας βασίζεται σε μία δομή δεδομένων το πλήθος των στοιχείων της οποίας μπορεί να μεγαλώσει αυθαίρετα κατά τη διάρκεια μιας εκτέλεσης. Σε αντίθεση, παρουσιάζουμε έναν UC αλγόριθμο που ικανοποιεί τις ιδιότητες ελευθερία-αναμονής και DAP για εφαρμογές που έχουν κάποιο άνω όριο στο πλήθος των δεδομένων που κάθε σειριακός κώδικάς τους μπορεί να προσπελάσει, σε οποιαδήποτε εκτέλεση.Για να ξεπεράσουμε αυτό το αρνητικό αποτέλεσμα, προτείνουμε μία ασθενέστερη έκδοση της ιδιότητας DAP, η οποία επιτρέπει σε δύο διεργασίες να προσπελάζουν το ίδιο αντικείμενο απόδοσης χρονοσφραγίδων, ακόμη και εάν προσπελάζουν διαφορετικά τμήματα της διαμοιραζόμενης μνήμης. Επομένως, ενώ καταστρατηγεί μερικώς την ιδιότητα DAP, και η έκδοση αυτή βελτιώνει τον παραλληλισμό. Στη συνέχεια, παρουσιάζουμε έναν UC αλγόριθμο που ικανοποιεί αυτή την έκδοση της ιδιότητας DAP και την ιδιότητα ελευθερία-αναμονής.Ακόμη, για την επίτευξη προόδου και τη βελτίωση του παραλληλισμού οι περισσότεροι αλγόριθμοι STM ακολουθούν μία αισιόδοξη τεχνική, όπου οι δοσοληψίες εκτελούνται χρησιμοποιώντας τιμές διαμοιραζόμενων δεδομένων που δεν είναι απαραίτητα συνεπής. Σε περιπτώσεις συνωστισμού κατά την προσπέλαση συγκεκριμένων τμημάτων της διαμοιραζόμενης μνήμης, ενδέχεται κάποιες ή και όλες οι δοσοληψίςε να αποτυγχάνουν, μειώνοντας έτσι την απόδοση της εφαρμογής. Από την άλλη, σε έναν απαισιόδοξο STM \grk αλγόριθμο όλες οι δοσοληψίες εκτελούνται επιτυχώς. Ωστόσο, οι δοσοληψίες που τροποποιούν δεδομένα της διαμοιραζόμενης μνήμης, ή αλλιώς δοσοληψίες ενημέρωσης, εκτελούνται σειριακά η μία μετά την άλλη. Αυτό μειώνει σημαντικά τον παραλληλισμό σε πολλές περιπτώσεις και οδηγεί σε μείωση της απόδοσης.Ως πρώτο βήμα για την επίτευξη τόσο προόδου όσο και παραλληλισμού στην τεχνική STM, προτείνουμε τον STM αλγόριθμο WFR-TM ο οποίος συνδυάζει πλεονεκτήματα τόσο από τους αισιόδοξους όσο και από τους απαισιόδοξους STM αλγορίθμους. Ο αλγόριθμος WFR-TM εγγυάται την ιδιότητα προόδου ελευθερίας-αναμονής για όσες δοσοληψίες δεν τροποποιούν δεδομένα της διαμοιραζόμενης μνήμης, ή αλλιώς δοσοληψίες ανάγνωσης, αποφεύγοντας τη σειριακή εκτέλεση των δοσοληψιών ενημέρωσης. Οι δοσοληψίες ενημέρωσης χρησιμοποιούν μία απαισιόδοξη τεχνική για να συγχρονιστούν με τις δοσοληψίες ανάγνωσης. Συγκεκριμένα, περιμένουν τις δοσοληψίες ανάγνωσης να ολοκληρωθούν. Επίσης, οι δοσοληψίες ενημέρωσης χρησιμοποιούν μία αισιόδοξη τεχνική για να συγχρονιστούν μεταξύ τους. Συγκεκριμένα, εκτελούνται ταυτόχρονα και μία δοσοληψία ενημέρωσης ολοκληρώνεται επιτυχώς μόνο εάν καμία άλλη δοσοληψία ενημέρωσης δεν προσπελάζει ταυτόχρονα το τμήμα της διαμοιραζόμενης μνήμης στο οποίο εργάζεται. Αξίζει να σημειωθεί ότι ο αλγόριθμος WFR-TM εγγυάται ότι κάθε δοσοληψία ενημέρωσης περιμένει ένα πεπερασμένο πλήθος από δοσοληψίες ανάγνωσης. Επίσης, με δεδομένο πως καμία διεργασία δε σφάλει, ο αλγόριθμος WFR-TM εγγυάται ότι σε κάθε σημείο της εκτέλεσης υπάρχει μία δοσοληψία ενημέρωσης που μπορεί να εκτελεστεί επιτυχώς σε πεπερασμένο χρονικό διάστημα.Τέλος, προτείνουμε τον STM αλγόριθμο Semantic-TM ο οποίος εγγυάται πως όλες οι δοσοληψίες υποστηρίζουν την ιδιότητα προόδου ελευθερία-αναμονής. Ο αλγόριθμος Semantic-TM επιτυγχάνει λεπτόκοκκο παραλληλισμό στο επίπεδο των εντολών των δοσοληψιών, το οποίο επιτρέπει τόσο την ταυτόχρονη εκτέλεση δοσοληψιών όσο και την ταυτόχρονη εκτέλεση ανεξάρτητων μεταξύ τους εντολών της ίδιας δοσοληψίας.