Accelerating irregular applications via efficient synchronization and data access techniques
Authors: Γιαννούλα Χριστίνα 
Published: October 2022

Οι μη-κανονικές εφαρμογές, όπως οι εφαρμογές επεξεργασίας γράφων, παράλληλων δομών δεδομένων και επίλυσης αραιών γραμμικών συστημάτων, αποτελούν μία από τις πιο σημαντικές οικογένειες υπολογιστικών εφαρμογών στις μέρες μας. Ως αποτέλεσμα, πολλοί ερευνητές έχουν μελετήσει και προτείνει τεχνικές βελτίωσης της επίδοσης και της ενεργειακής κατανάλωσης των μη-κανονικών εφαρμογών σε σύγχρονες πολυπύρηνες αρχιτεκτονικές. Σε αυτήν την διδακτορική διατριβή εντοπίζουμε δύο σημαντικές προκλήσεις σε αυτή την οικογένεια εφαρμογών. Πρώτον, οι παράλληλες μη-κανονικές εφαρμογές είναι δύσκολο να κλιμακώσουν χρησιμοποιώντας ένα μεγάλο αριθμό νημάτων λόγω του υψηλού κόστους συγχρονισμού μεταξύ των νημάτων. Δεύτερον, οι μη-κανονικές εφαρμογές εμφανίζουν πολύπλοκα μοτίβα πρόσβασης των δεδομένων στη μνήμη, και χαμηλή υπολογιστική ικανότητα, με αποτέλεσμα επίδοσή τους περιορίζεται σημαντικά από τις δαπανηρές προσβάσεις δεδομένων στη μνήμη.Αυτή η διδακτορική διατριβή πραγματοποιεί μία εις βάθος ανάλυση της κλιμακωσιμότητας των μη-κανονικών εφαρμογών και αναδεικνύει τα κυριότερα προβλήματα επίδοσής τους. Σε αυτήν την διδακτορική διατριβή υποστηρίζουμε ότι αποδοτικές τεχνικές συγχρονισμού των παράλληλων νημάτων σε συνεργασία με βελτιστοποιημένες τεχνικές διαχείρισης δεδομένων τόσο σε επίπεδο λογισμικού όσο και σε επίπεδο υλικού προσφέρουν υψηλή κλιμακωσιμότητα και σημαντική επίδοση στις μη-κανονικές εφαρμογές. Ως εκ τούτου, προτείνουμε 4 διαφορετικές προσεγγίσεις για την επιτάχυνση μη-κανονικών εφαρμογών σε διαφορετικά περιβάλλοντα, συμπεριλαμβανομένων των κοινών πολυπύρηνων αρχιτεκτονικών και των αρχιτεκτονικών με επεξεργασία κοντά στη μνήμη: (α) Ένας νέος παράλληλος αλγόριθμος χρωματισμού γράφων για πολυπύρηνες αρχιτεκτονικές που προτείνει μία αποδοτική τεχνική διαχείρισης δεδομένων, η οποία συνδυάζεται αρμονικά με το μηχανισμό συγχρονισμού σε επίπεδο υλικού, (β) Μία παράλληλη ουρά προτεραιότητας που εναλλάσσεται δυναμικά μεταξύ δύο αλγοριθμικών σχημάτων, και εκμεταλλεύεται την τοπικότητα δεδομένων με σκοπό να επιτευχθεί υψηλή απόδοση υπό διαφορετικά σενάρια συμφόρησης σε αρχιτεκτονικές με ανομοιόμορφη πρόσβαση στη μνήμη, (γ) Ένας πρακτικός μηχανισμός συγχρονισμού σε επίπεδου υλικού για αρχιτεκτονικές με επεξεργασία κοντά στη μνήμη, και (δ) Μία βιβλιοθήκη αλγορίθμων του υπολογιστικού πυρήνα του πολλαπλασιασμού αραιού πίνακα με διάνυσμα, η οποία περιλαμβάνει μία μεγάλη ποικιλία αποτελεσματικών τεχνικών διαμέρισης δεδομένων και συγχρονισμού για αρχιτεκτονικές με επεξεργασία κοντά στη μνήμη. Συνολικά, στην παρούσα διδακτορική διατριβή αποδεικνύουμε ότι η εκτέλεση μη-κανονικών υπολογιστικών πυρήνων σε πολυπύρηνες αρχιτεκτονικές και αρχιτεκτονικές με επεξεργασία κοντά στη μνήμη μπορεί να επιταχυνθεί με το συν-σχεδιασμό αποδοτικών μηχανισμών συγχρονισμού με βελτιστοποιημένες τεχνικές πρόσβασης και διαχείρισης δεδομένων, παρέχοντας έτσι υψηλά επίπεδα παραλληλισμού, χαμηλό κόστος πρόσβασης στα δεδομένα και χαμηλό κόστος συγχρονισμού για την υψηλή επίδοση και τη χαμηλή ενεργειακή κατανάλωση του συστήματος. Ελπίζουμε ότι η παρούσα διατριβή θα εμπνεύσει μελλοντική έρευνα στο συν-σχεδιασμό μη-κανονικών υπολογιστικών πυρήνων με σύγχρονες υπολογιστικές πλατφόρμες για να επιτευχθεί υψηλή επίδοση και χαμηλή ενεργειακή κατανάλωση σε αναδυόμενες εφαρμογές.