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