E-Locus - Ιδρυματικό Καταθετήριο Πανεπιστημίου Κρήτης - Concurrent lock-free binary search tree implementations with range query support

Αρχική Concurrent lock-free binary search tree implementations with range query support

Αποτελέσματα - Λεπτομέρειες

[Προσθήκη στο καλάθι]

Κωδικός Πόρου

000428263

Τίτλος

Concurrent lock-free binary search tree implementations with range query support

Άλλος τίτλος

Ταυτόχρονα προσπελάσιμες υλοποιήσεις δυαδικών δένδρων αναζήτησης που υποστηρίζουν επερωτήσεις εύρους τιμών

Συγγραφέας

Παπαβασιλείου, Ηλίας Β.

Σύμβουλος διατριβής

Φατούρου, Παναγιώτα

Μέλος κριτικής επιτροπής

Μαρκάτος, Ευάγγελος
Μαγκούτης, Κώστας

Περίληψη

Σε αυτή την εργασία, μελετάμε ταυτόχρονα προσπελάσιμες υλοποιήσεις δυαδικών δένδρων αναζήτησης που υποστηρίζουν επερωτήσεις εύρους τιμών. Συγκεκριμένα, παρουσιάζουμε τον BPNB-BST, τον πρώτο αλγόριθμο που παρέχει επερωτήσεις εύρους τιμών εξασφαλίζοντας την ισχυρή ιδιότητα προόδου Ελευθερία Αναμονής (wait-freedom) και έχει συγκρίσιμη απόδοση με εκείνη άλλων αλγορίθμων αιχμής, οι οποίοι όμως παρέχουν ασθενέστερες εγγυήσεις προόδου. Συγκεκριμένα, προηγούμενες υλοποιήσεις εγγυώνται μόνο την ιδιότητα Ελευθερία Κλειδωμάτων (ή και ακόμη πιο ασθενείς ιδιότητες προόδου) κατά την απάντηση επερωτήσεων εύρους τιμών. Αντίθετα, ο BPNB-BST εγγυάται την ισχυρότερη ιδιότητα προόδου Ελευθερία Αναμονής. Η διάκριση μεταξύ των ιδιοτήτων αυτών είναι σημαντική σε περιβάλλοντα που υποστηρίζουν χρονοβόρες λειτουργίες, όπως οι επερωτήσεις εύρους τιμών, καθώς χωρίς ισχυρές εγγυήσεις προόδου, ο τερματισμός τέτοιων λειτουργιών μπορεί να καθυστερεί επ' άπειρον. Ο BPNB-BST είναι σειριοποιήσιμος, χρησιμοποιεί εντολές compare-and-swap που παρέχονται από το υλικό και είναι ανθεκτικός σε οποιοδήποτε αριθμό από αποτυχίες. Επιπλέον, στον BPNB-BST: (1) οι λειτουργίες ενημέρωσης εκτελούνται ανεξάρτητα, αλληλεπιδρώντας μεταξύ τους μόνο αν προσβούν την ίδια γειτονιά του δένδρου, (2) ο μηχανισμός βοήθειας που χρησιμοποιείται από τον αλγόριθμο για να διασφαλίσει τις ισχυρές εγγυήσεις προόδου που εγγυάται είναι ελαφρύς και (3) ο αλγόριθμος λειτουργεί σε ένα δυναμικό περιβάλλον όπου τα νήματα μπορούν να εισέρχονται ή να εγκαταλείπουν το σύστημα ανά πάσα χρονική στιγμή. Έχουμε πραγματοποιήσει μια λεπτομερή πειραματική ανάλυση που δείχνει ότι ο BPNB-BST έχει καλύτερη δυνατότητα κλιμάκωσης με το μέγεθος της επερώτησης εύρους τιμών, συγκριτικά με τους τρέχοντες αλγόριθμους αιχμής. Η πειραματική μας ανάλυση φέρνει στην επιφάνεια τις ιδιότητες (και τις σχεδιαστικές αποφάσεις) που παίζουν καθοριστικό ρόλο στην απόδοση του BPNB-BST, καθώς και ενδιαφέροντα trade-offs μεταξύ των διάφορων αλγορίθμων. Τα πειράματά μας οδήγησαν σε μεγάλο βαθμό τις βελτιστοποιήσεις που εφαρμόσαμε στον αλγόριθμο για να έχει τόσο καλή απόδοση.

Φυσική περιγραφή

vi, 85 σ. : σχεδ., πιν., εικ. ; 30 εκ.

Γλώσσα

Αγγλικά

Θέμα

Concurrency

Data structures

Δένδρα

Δομές δεδομένων

Ταυτόχρονη προσπέλαση

Ημερομηνία έκδοσης

2019-07-26