Μελέτη και Σχεδίαση Παράλληλων Ουρών Προτεραιότητας σε Αρχιτεκτονικές Ανομοιόμορφης Πρόσβασης Μνήμης (NUMA)

Abstract

Στις μέρες μας, τα πολυπήρυνα συστήματα αποτελούνται κυρίως από αρχιτεκτονικές ανο-μοιόμορφης πρόσβασης μνήμης (NUMA). Η υψηλή απόδοση και η κλιμακωσιμότητα είναι ζητούμενα των σύγχρονων εφαρμογών, οι οποίες βασίζονται σε παράλληλους αλγορίθμους δομών δεδομένων. Ο σχεδιασμός των αλγορίθμων αυτών θα πρέπει να γίνεται με γνώμονα τα χαρακτηριστικά των σύγχρονων αρχιτεκτονικών. Αντικείμενο της παρούσας διπλωματικής είναι οι παράλληλες δομές δεδομένων, και κυρίως οι ουρές προτεραιότητας. Μελετάμε και αξιολογούμε σε αρχιτεκτονικές ανομοιόμοφης πρόσβασης μνήμης έναν μεγάλο αριθμό παράλληλων υλοποιήσεων, κάποιες απο τις οποίες είναι ειδικά σχεδιασμένες για numa συστήματα (numa-aware υλοποιήσεις). Προτείνουμε μία νέα numa-aware ουρά προτεραιότητας (αλγόριθμος NUDDLE), η οποία αξιοποιεί τα χαρακτηριστικά των αρχιτεκτονικών τύπου ΝUMA και οδηγεί σε καλύτερα αποτελέσματα όταν ο ανταγωνισμός μεταξύ των νημάτων είναι έντονος. Παρόλα αυτά, σε εφαρμογές που χαρακτηρίζονται από υψηλά επίπεδα παραλληλισμού, οι non-numa-aware υλοποιήσεις επιτυγχάνουν μεγαλύτερη απόδοση. Συμπεραίνουμε, λοιπόν, ότι δεν υπάρχει μια ιδανική δομή δεδομένων και οτι οι συνθήκες στις οποίες εκτελείται μια εφαρμογή είναι αυτές που καθορίζουν το είδος του αλγορίθμου που πρέπει να χρησιμοποιηθεί. Στην προσπάθειά μας να προσεγγίσουμε τη λειτουργία μιας ιδανικής δομής, μοντελοποιούμε το πρόβλημα της επιλογής του καλύτερου αλγορίθμου και χρησιμοποιούμε τεχνικές μηχανικής μάθησης για να το επιλύσουμε. Πιο συγκεκριμένα, θεωρούμε δύο κλάσεις υλοποιήσεων (numa-aware και non-numa-aware) και προτείνουμε ένα μοντέλο βασισμένο σε δέντρα αποφάσεων, το οποίο αφού εκπαιδευτεί σε ένα ευρύ φάσμα πειραμάτων, κατηγοροιοποιεί τα διάφορα περιβάλλοντα εκτέλεσης στις δύο κλάσσεις με αρκετά υψηλή ακρίβεια. Στη συνέχεια, χρησιμοποιούμε αυτό το μοντέλο για να δημιουργήσουμε μια δυναμική δομή δεδομένων, η οποία, εξετάζοντας τις συνθήκες κάτω από τις οποίες εκτελείται, μπορεί να μεταβεί εύκολα και γρήγορα από numa-aware σε non-numa-aware αλγόριθμο επιτυγχάνοντας έτσι τη βέλτιστη δυνατή απόδοση. Η μεθοδολογία αυτή, πιστεύουμε ότι μπορεί να επεκταθεί και να χρησιμοποιηθεί για το σχεδιασμό και άλλων παράλληλων δομών δεδομένων, οι οποίες θα μπορούν να προσαρμόζονται στο εκάστοτε περιβάλλον, να αξιοποιούν τα χαρακτηριστικά της κάθε αρχιτεκτονικής και άρα να παρουσιάζουν τα βέλτιστα δυνατά αποτελέσματα.