Αποτελέσματα - Λεπτομέρειες
Εντολή Αναζήτησης : Συγγραφέας="Φατούρου"
Και Συγγραφέας="Παναγιώτα"
Τρέχουσα Εγγραφή: 6 από 16
|
Κωδικός Πόρου |
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 |
Συλλογή
|
Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
|
|
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
|
Μόνιμη Σύνδεση |
https://elocus.lib.uoc.gr//dlib/6/3/6/metadata-dlib-1581678443-911054-10356.tkl
|
Εμφανίσεις |
578 |