Efficient synchronization techniques for shared memory systems

Abstract

Overcoming the difficulty of concurrent programming has never become more urgent due to the proliferation of multicore machines and the imperative necessity of exploiting their computational power. One way to achieve this is by designing efficient concurrent data structures; common structures, like stacks and queues, are the most widely used inter-thread communication mechanisms. Additionally, synchronization techniques are required to efficiently execute, in a concurrent environment, those parts of modern applications that require significant synchronization. Although the efficient parallelization of these parts is not an easy task, Amdhal's law implies that achieving this is necessary in order to avoid significant reductions in speed-up.In this dissertation three families of highly efficient synchronization algorithms, called RedBlue, Sim and Synch are presented for executing concurrently blocks of code that have originally been programmed to be executed sequentially in asynchronous shared-memory distributed systems.We start by presenting the RedBlue family of adaptive synchronization algorithms that use common base objects (LL/SC or CAS and Read-Write) provided by the majority of the real-world machines.The first of these algorithms achieves better time complexity than all previously presented algorithms. This algorithm uses large LL/SC base objects and it comprises the keystone for the design of the other RedBlue algorithms that use smaller base objects. Specifically, the second algorithm significantly reduces the size of the required base objects. The rest of the algorithms have been designed for large objects.The Sim family of synchronization algorithms achieves at (1) getting better time complexity by using base objects other than LL/SC and read-write (i.e. Swap, AtomicAdd, etc) and (2) competing in terms of performance with the state-of-the-art synchronization algorithms (i.e. high performance spin-locks, etc. Sim is a simple synchronization algorithm with constant step complexity using a Fetch&Add additional to an LL/SC object. Sim has been implemented for a real shared-memory machine architecture. Its practical version, called P-Sim, outperforms several state-of-the-art lock-based and lock-free synchronization algorithms, while being wait-free, i.e. satisfying a stronger progress condition than all the algorithms that it outperforms.We further study blocking implementations of the combining technique with the goal of discovering where their real performance power resides and whether or how performance is impacted by ensuring some desired properties (e.g. fairness in serving requests). This is accomplished by presenting two new blocking implementations of the combining technique; the first (CC-Synch) is highly-efficient in systems that support coherent caches, whereas the second (DSM-Synch) works better in cache-less NUMA machines. In comparison to previous blocking implementations, the new implementations (1) provide bounds on the number of remote memory references (RMRs) that they perform, (2) support a stronger notion of fairness, and (3) use simpler and fewer base objects. CC-Synch and DSM-Synch achieve better performance than P-Sim as well as any other algorithm provided in the past.Several modern multicore systems organize the cores into clusters and provide fast communication within the same cluster and much slower communication across clusters. A hierarchical version of CC-Synch, called H-Synch, is presented, which exploits the hierarchical communication nature of such systems to achieve better performance. Experiments show that H-Synch significantly outperforms previous state-of-the-art hierarchical approaches.Based on P-Sim, CC-Synch, DSM-Synch, and H-Synch, we provide very efficient implementations of common shared data structures like stacks and queues. Specifically, the implementations SimStack and SimQueue that are based on P-Sim are wait-free, whereas those based on CC-Synch, DSM-Synch and H-Synch are blocking but achieve better performance than SimStack and SimQueue as well as any other algorithm provided in the past. SimStack and SimQueue are the first stack and queue implementations that satisfy both wait-freedom and high performance.

Η εξάπλωση των πολυπύρηνων επεξεργαστών έχει καταστήσει εξαιρετικά αναγκαία την εκμετάλλευση της υπολογιστικής ισχύος τους. Ένας τρόπος για την αποδοτική χρήση συστημάτων που βασίζονται σε πολυπύρηνους επεξεργαστές είναι ο σχεδιασμός αποδοτικών διαμοιραζόμενων (παράλληλα προσπελάσιμων από πολλά νήματα) δομών δεδομένων, οι οποίες χρησιμοποιούνται ως θεμελιώδεις μηχανισμοί επικοινωνίας μεταξύ των νημάτων του συστήματος. Για την αποτελεσματική παράλληλη εκτέλεση πολλών εφαρμογών απαιτείται η ανάπτυξη αποδοτικών αλγορίθμων συγχρονισμού.Σε αυτή τη διατριβή παρουσιάζονται τρεις οικογένειες νέων αλγορίθμων συγχρονισμού υψηλής απόδοσης που ονομάζονται RedBlue, Sim και Synch. Οι εν λόγω αλγόριθμοι χρησιμοποιούνται για την παράλληλη εκτέλεση κώδικα που έχει προγραμματιστεί για να εκτελείται σειριακά.Αρχικά, παρουσιάζονται οι αλγόριθμοι συγχρονισμού RedBlue που είναι προσαρμοστικοί (οι προσαρμοστικοί αλγόριθμοι έχουν χρονική πολυπλοκότητα ανάλογη του αριθμού των ενεργών νημάτων και όχι του συνολικού πλήθους αυτών), Οι αλγόριθμοι RedBlue πληρούν την ιδιότητα ελευθερία-αναμονής (wait-free) που εγγυάται υψηλή ανθεκτικότητα σε σφάλματα. Ο πρώτος αλγόριθμος, ο οποίος ονομάζεται F-RedBlue, επιτυγχάνει καλύτερη χρονική πολυπλοκότητα από τους αλγορίθμους που είχαν παρουσιαστεί παλιότερα και είναι χρονικά βέλτιστος (από θεωρητική σκοπιά). Οι υπόλοιποι αλγόριθμοι της οικογένειας RedBlue, χρησιμοποιούν αντικείμενα μικρότερου μεγέθους και έτσι μπορούν να υλοποιηθούν πιο εύκολα στην πράξη.Οι αλγόριθμοι συγχρονισμού Sim επιτυγχάνουν (1) περαιτέρω μείωση της χρονικής πολυπλοκότητας χρησιμοποιώντας βασικά αντικείμενα διαφορετικά των LL/SC και Read/Write, και (2) βελτίωση της απόδοσης. Ειδικότερα, ο αλγόριθμος συγχρονισμού Sim χρησιμοποιεί Add και LL/SC βασικά αντικείμενα και επιτυγχάνει O(1) χρονική πολυπλοκότητα. Ο P-Sim είναι η πρακτική έκδοση του Sim, ξεπερνά σε επιδόσεις τους γρηγορότερους αλγορίθμους συγχρονισμού στην βιβλιογραφία, ενώ ταυτόχρονα πληροί τη συνθήκη τερματισμού ελευθερία αναμονής που είναι ισχυρότεροι από εκείνες που εξασφαλίζονταν από προηγούμενους αλγόριθμους. Σε αυτή τη διατριβή μελετήθηκε σε βάθος η συνεργατική τεχνική (combining technique) με στόχο την ανάπτυξη εμποδιστικών (blocking) αλγορίθμων συγχρονισμού με ακόμη καλύτερη απόδοση και με χαρακτηριστικά δικαιότερης εξυπηρέτησης. Αναπτύχθηκαν δύο νέοι εμποδιστικοί αλγόριθμοι συγχρονισμού. Ο πρώτος, που ονομάζεται CC-Synch, είναι κατάλληλος για μηχανές που υποστηρίζουν συνεπείς κρυφές μνήμες (coherent NUMA), ενώ ο δεύτερος, που ονομάζεται DSM-Synch, είναι κατάλληλος για πολυεπεξεργαστές χωρίς κρυφές μνήμες (cache-less NUMA). Σε αντίθεση με παλαιότερους εμποδιστικούς συνδυαστικούς αλγορίθμους, οι παραπάνω αλγόριθμοι (1) επιβάλλουν άνω όρια στον αριθμό των απομακρυσμένων αναφορών στη μνήμη, (2) επιτυγχάνουν περισσότερη δικαιοσύνη κατά την προσπέλαση στα κοινόχρηστα αντικείμενα, και (3) χρησιμοποιούν απλούστερα βασικά αντικείμενα. Ο CC-Synch και ο DSM-Synch επιτυγχάνουν καλύτερη απόδοση από τον P-Sim και όλους τους παλαιότερους αλγόριθμους συγχρονισμού.Πολλά πολυπύρηνα συστήματα οργανώνουν τα επεξεργαστικά στοιχεία σε ομάδες και παρέχουν γρήγορη επικοινωνία μεταξύ των επεξεργαστικών στοιχείων που βρίσκονται στην ίδια ομάδα, ενώ παρέχουν αργή επικοινωνία μεταξύ των επεξεργαστικών στοιχείων διαφορετικών ομάδων. Ο H-Synch, που είναι μια ιεραρχική έκδοση του CC-Synch, εκμεταλλεύεται την ιεραρχική φύση της επικοινωνίας τέτοιων συστημάτων και η πειραματική του μελέτη έδειξε ότι ξεπερνά κατά πολύ σε απόδοση όλους τους παλαιότερους ιεραρχικούς και μη αλγορίθμους συγχρονισμού.Σε αυτή τη διατριβή παρουσιάζονται τέλος αποδοτικές υλοποιήσεις διαμοιραζόμενων ουρών και στοιβών που βασίζονται στους P-Sim, CC-Synch, DSM-Synch και H-Synch. Αυτές που βασίζονται στους CC-Synch, DSM-Synch και H-Synch επιτυγχάνουν καλύτερες επιδόσεις από όλες τις παλαιότερες υλοποιήσεις, ενώ οι SimStack και SimQueue είναι οι πρώτες υλοποιήσεις κοινόχρηστων στοιβών και ουρών που πληρούν την ιδιότητα ελευθερία-αναμονής και ταυτόχρονα επιτυγχάνουν υψηλή απόδοση στην πράξη.