Αποδοτικές λειτουργίες αναζήτησης εύρους σε Β+-Δέντρα με χρήση RCU-HTM

Abstract

Τα πολυπύρηνα υπολογιστικά συστήματα δε συνιστώνται πλέον μόνο για επιστημονικές εφαρμογές, αλλά αποτελούν συχνή επιλογή για την κάλυψη ποικίλων υπολογιστικών αναγκών. Για την αξιοποίηση των συστημάτων αυτών είναι απαραίτητη η ύπαρξη κατάλληλων παράλληλων αλγορίθμων και δομών δεδομένων, που θα εκμεταλλεύονται στο μέγιστο τους διαθέσιμους πόρους, θα κλιμακώνουν αποδοτικά και θα εγγυόνται τη συνέπεια των αποτελεσμάτων. Κύριος σκοπός της παρούσας διπλωματικής εργασίας είναι η ανάπτυξη μίας παράλληλης δομής δεδομένων που θα υποστηρίζει αποδοτικές λειτουργίες αναζήτησης εύρους. Για να φτάσουμε στο σημείο αυτό, ξεκινάμε παραθέτοντας το θεωρητικό υπόβαθρο που θα μας χρειαστεί, αναλύοντας ιδιαίτερα τα στοιχεία που πρόκειται να χρησιμοποιήσουμε. Στη συνέχεια αναφερόμαστε σε ήδη υπάρχουσες υλοποιήσεις, βλέποντας έτσι τι πρέπει να προσέξουμε για τη δημιουργία ενός αποδοτικού αλγορίθμου. Ακολούθως, αναλύουμε την τεχνική RCU-HTM, η οποία συνδυάζει την τεχνική Read- Copy-Update με Transactional Memory. Έπειτα, την εφαρμόζουμε σε ένα Β+ Δέντρο, δημιουργώντας έτσι μία αποδοτική παράλληλη δομή δεδομένων που προσφέρει ιδιαίτερα αποδοτικές λειτουργίες αναζήτησης εύρους. Τέλος, αξιολογούμε πειραματικά τον αλγόριθμο που αναπτύξαμε, συγκρίνοντας την απόδοση του με ορισμένες από τις ήδη υπάρχουσες υλοποιήσεις. Τα αποτελέσματα δείχνουν ότι η τεχνική RCU-HTM εφαρμοσμένη σε ένα Β+ Δέντρο δίνει μία πολύ αποδοτική υλοποίηση για αρκετά διαφορετικά σενάρια μετρήσεων, στην πλειονότητα των οποίων υπερτερεί των ανταγωνιστών της. Σε ορισμένα σενάρια μάλιστα, η απόδοση της είναι έως και τέσσερις φορές μεγαλύτερη αυτής των υπόλοιπων υλοποιήσεων. Κλείνοντας, οδηγούμαστε σε ενδιαφέροντα συμπεράσματα και προτείνουμε ορισμένες μελλοντικές επεκτάσεις που προκύπτουν από την παρούσα διπλωματική εργασία.