Your browser does not support JavaScript!

Αρχική    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
Συλλογή   Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
  Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
Εμφανίσεις 36

Ψηφιακά τεκμήρια
No preview available

Προβολή Εγγράφου
Εμφανίσεις : 4