Η εξάπλωση των πολυπύρηνων επεξεργαστών έχει καταστήσει εξαιρετικά αναγκαία την εκμετάλλευση της υπολογιστικής ισχύος τους. Ένας τρόπος για την αποδοτική χρήση συστημάτων που βασίζονται σε πολυπύρηνους επεξεργαστές είναι ο σχεδιασμός αποδοτικών διαμοιραζόμενων (παράλληλα προσπελάσιμων από πολλά νήματα) δομών δεδομένων, οι οποίες χρησιμοποιούνται ως θεμελιώδεις μηχανισμοί επικοινωνίας μεταξύ των νημάτων του συστήματος. Για την αποτελεσματική παράλληλη εκτέλεση πολλών εφαρμογών απαιτείται η ανάπτυξη αποδοτικών αλγορίθμων συγχρονισμού.Σε αυτή τη διατριβή παρουσιάζονται τρεις οικογένειες νέων αλγορίθμων συγχρονισμού υψηλής απόδοσης που ονομάζονται 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 είναι οι πρώτες υλοποιήσεις κοινόχρηστων στοιβών και ουρών που πληρούν την ιδιότητα ελευθερία-αναμονής και ταυτόχρονα επιτυγχάνουν υψηλή απόδοση στην πράξη.
