Ενοποιημένη Εφαρμογή Μετασχηματισμών Κώδικα Και Δεδομένων Για Την Αντιμετώπιση Της Καθυστέρησης (latency) Σε Πολυεπίπεδες Ιεραρχίες Μνήμης Πολυνηματικών Αρχιτεκτονικών

Abstract

Ένα από τα πιο σοβαρά προβλήματα των σημερινών υπολογιστικών συστημάτων είναι το χάσμα επίδοσης μεταξύ μονάδας επεξεργασίας και συστήματος μνήμης. Το πρόβλημα αυτό αντιμετωπιζεται με την ιεράρχηση του συστήματος μνήμης σε πολλαπλά επίπεδα (καταχωρητές, κρυφή μνήμη, εικονική μνήμη), όπου τα δεδομένα ενός επιπέδου αποτελούν υποσύσολο των δεδομένων του αμέσως χαμηλώτερου επιπέδου. Αν και η εισαγωγή της ιεραρχίας λύνει σημαντικά το πρόβλημα, η επίδοση μπορεί να αυξηθεί ακόμη περισσότερο όταν τα ίδια τα προγράμματα σχεδιάζονται με στόχο την μέγιστη δυνατή αξιοποίηση της ιεραρχίας μνήμης.Σκοπός της παρούσας διπλωματικής εργασίας είναι η αξιοποίηση των πολυεπίπεδων ιεραρχιών μνήμης των σύγχρονων υπολογιστικών συστημάτων μέσω της ενιαίας εφαρμογής μετασχηματισμών κώδικα και μετασχηματισμών διατάξεων δεδομένων, οι οποίοι αύξάνουν την τοπικότητα των αναφορών και μείωνουν επομένως τις αστοχίες στα διάφορα επίπεδα. Παρουσιάζουμε μεταξύ άλλων τον μετασχηματισμό tiling ο οποίος αποτελεί τον πιο διαδεδομένο μετασχηματισμό κώδικα για την αναδιάταξη των επαναλήψεων σε φωλιασμένους βρόχους με στόχο την αύξηση της τοπικότητας, καθώς και τις διατάξεις ενοτήτων οι οποίες αναδιατάσσουν το χώρο δεδομένων, έτσι ώστε τα δεδομένα να αποθηκεύονται με τη σειρά που αυτά προσπελάνονται από τους tiled κώδικες. Για την δεικτοδότηση των ενοτήτων στηριζόμαστε στον αποδοτικό μηχανισμό δεικτοδότησης MBaLt.Η μελέτη της αποτελεσματικότητας των μετασχηματισμών, καθώς και του μηχανισμού δεικτοδότηση ενοτήτων, γίνεται μέσω της υλοποίησης διαφόρων εκδοχών του μετροπρογράμματος ``Παραγοντοποίηση Cholesky''. Τα πραγματικά αποτελέσματα που λαμβάνουμε από την εκτέλεση των εκδοχών του μετροπρογράμματος σε δύο διαφορετικά υπολογιστικά συστήματα δείχουν ότι η επίδοση αυξάνεται σημαντικά με την ενιαία εφαρμογή της πλακόστρωσης και διατάξεων ενοτήτων με δεικτοδότηση MBaLt. Επιπρόσθετα, τα αναλυτικά αποτελέσματα που λαμβάνονται από την εξομείωση μέσω του εργαλείου SimpleScalar, επιβεβαιώνουν ότι η βελτίωση της επίδοσης οφείλεται στην ελάττωση των αστοχιών κρυφής μνήμης και τον περιορισμό της υπερχείλησης TLB. Τέλος, υλοποιούμε πολυνηματικές εκδοχές του μετροπρογράμματος με στόχο την μελέτη της επίδοσης της ενιαίας εφαρμογής των προαναφερομένων μετασχηματισμών σε ιεραρχίες μνήμης πολυνηματικών αρχιτεκτονικών τύπου SMT. Τα αποτελέσματα που προκύπτουν, αποκαλύπτουν την αδυναμία επίδοσης αυτών των αρχιτεκτονικών κατά την εκτέλεση παράλληλων εκδοχών βελτιστοποιημένων προγραμμάτων που παρουσιάζουν υψηλή παραλληλία σε επίπεδο εντολής.