Ανάπτυξη Λογισμικού Και Τεχνικών Συμπίεσης Δεδομένων Για Τη Βελτίωση Της Επίδοσης Υπολογιστικών Εφαρμογών Σε Παράλληλες Αρχιτεκτονικές Μοιραζόμενης Μνήμης

Abstract

Η παρούσα διατριβή ασχολείται με την ανάπτυξη τεχνικών συμπίεσης δεδομένων, που ως στόχο έχουν τη βελτίωση της επίδοσης πολυνηματικών εφαρμογών με έντονες προσβάσεις στην κύρια μνήμη. Συγκεκριμένα, επικεντρώνεται σε παράλληλες αρχιτεκτονικές μοιραζόμενης μνήμης, όπου ο ρυθμός μεταφοράς δεδομένων είναι ανεπαρκής, αλλά υπάρχει άφθονη υπολογιστική ισχύς. Οι προτεινόμενες τεχνικές περιορίζουν το μη-κλιμακώσιμο μέρος του χρόνου εκτέλεσης (πρόσβαση στη μνήμη), αυξάνοντας το υπολογιστικό κόστος. Δεδομένου ότι το υπολογιστικό κόστος είναι κλιμακώσιμο, θα μετριαστεί όσο αυξάνει ο αριθμός των επεξεργαστικών μονάδων που χρησιμοποιούνται. Η διατριβή εστιάζει σε υπολογισμούς αραιών πινάκων. Συγκεκριμένα, μελετάται η επίδοση του πολλαπλασιασμού αραιού πίνακα με διάνυσμα, που αποτελεί έναν ιδιαίτερα σημαντικό υπολογιστικό πυρήνα και συναντάται σε πληθώρα εφαρμογών. Το συμπέρασμα που προκύπτει είναι ότι η επίδοση του συγκεκριμένου πυρήνα, όταν εκτελείται σε παράλληλες αρχιτεκτονικές μοιραζόμενης μνήμης, περιορίζεται από τον ρυθμό μεταφοράς δεδομένων από την κύρια μνήμη. Με στόχο τη μείωση του κορεσμού του συστήματος μνήμης και τη βελτίωση της επίδοσης του πυρήνα, η διατριβή προτείνει δύο σχήματα συμπίεσης. Το πρώτο είναι το CSR-DU, το οποίο μειώνει τον όγκο των δομικών δεδομένων του πίνακα χρησιμοποιώντας κωδικοποίηση δέλτα χοντρού κόκκου. Το δεύτερο είναι CSR-VI και στοχεύει στη μείωση του όγκου δεδομένων των αριθμητικών τιμών σε πίνακες με μικρό αριθμό μοναδικών τιμών, χρησιμοποιώντας έμμεσες αναφορές. Εκτεταμένη πειραματική αξιολόγηση των παραπάνω μεθόδων και του συνδυασμού τους σε δύο συστήματα, δείχνει σημαντικά οφέλη σε ό,τι αφορά την επίδοση του υπολογιστικού πυρήνα πολλαπλασιασμού αραιού πίνακα με διάνυσμα. Τέλος, με κίνητρο το σχεδιασμό του σχήματος CSR-DU, η διατριβή προτείνει μια γενικευμένη προσέγγιση για ένα σχήμα αποθήκευσης αραιών πινάκων, το οποίο ονομάζεται CSX. Το CSX στοχεύει στην εκμετάλλευση της δομής αραιών πινάκων υποστηρίζοντας διαφορετικά σχήματα συμπίεσης. Παρουσιάζεται μια πρώτη υλοποίηση, η οποία βασίζεται σε κωδικοποίηση δέλτα και σε περιορισμό των επαναλαμβανόμενων τιμών. Η πειραματική αξιολόγηση που πραγματοποιείται δείχνει αξιόλογα οφέλη στην επίδοση του πυρήνα πολλαπλασιασμού αραιού πίνακα με διάνυσμα, και ιδιαίτερα για πίνακες για τους οποίους το σχήμα CSR-DU δεν προσφέρει σημαντική βελτίωση.