Reduction of the average-performance degradation and/or performance variance caused by defects in CPU caches
Authors: Μαυρόπουλος Μιχαήλ 
Published: October 2024

Η πρόοδος στις τεχνολογίες ολοκλήρωσης έχει συμβάλει καθοριστικά στην εξέλιξη των ολοκληρωμένων κυκλωμάτων τα οποία αποτελούνται από ένα μεγάλο και ολοένα αυξανόμενο αριθμό τρανζίστορ. Ωστόσο όσο προχωράμε σε μικρότερες τεχνολογίες ολοκλήρωσης αυξάνεται σημαντικά ο αριθμός των ελλαττωματικών στοιχείων που απαρτίζουν τα ολοκληρωμένα κυκλώματα, δηλαδή των τρανζίστορ, τα οποία δεν λειτουργούν σύμφωνα με τις αρχικές τους προδιαγραφές. Σύγχρονες μελέτες έχουν δείξει πως η πιθανότητα ύπαρξης ελαττωματικών τρανζίστορ αυξάνεται σημαντικά καθώς η τεχνολογία ολοκλήρωσης αγγίζει τα όρια των νόμων της φυσικής για την κατασκευή ηλεκτρονικών στοιχείων με τη χρήση πυριτίου. Αυτή η διατριβή προτείνει μεθοδολογίες για τoν περιορισμό της υποβάθμισης της απόδοσης καθώς επίσης και της διακύμανσης της απόδοσης που προκαλούνται από ελαττώματα στις κρυφές μνήμες ενός επεξεργαστή. Έμφαση δίνεται στα στοιχεία μνήμης για δύο κύριους λόγους. Αρχικά οι δομές μνήμης καταλαμβάνουν ένα πολύ μεγάλο μέρος της επιφάνειας του ολοκληρωμένου του επεξεργαστή (μάλιστα το συγκεκριμένο ποσοστό αυξάνεται καθώς μεταβαίνουμε σε πολυπύρηνα επεξεργαστικά συστήματα). Ο δεύτερος λόγος είναι ότι οι δομές μνήμης υλοποιούνται με τρανζίστορ ελάχιστου μεγέθους, τα οποία έχουν ως αποτέλεσμα την αύξηση της ευαισθησίας της λειτουργίας των ολοκληρωμένων κυκλωμάτων στις διακυμάνσεις των χαρακτηριστικών κατασκευής τους, της τάσης τροφοδοσίας και της θερμοκρασίας. Οι αυξανόμενες απαιτήσεις για μείωση της κατανάλωσης ισχύος των ολοκληρωμένων κυκλωμάτων οδηγούν ολοένα και περισσότερο στην ανάγκη για μείωση της τάσης τροφοδοσίας σε συνδυασμό με την μείωση της συχνότητας λειτουργίας. Η τάση τροφοδοσίας έχει σημαντικό αντίκτυπο στην μείωση της δυναμικής ισχύος, εξαιτίας του τετραγώνου στην σχέση που τις συνδέει. Η πτώση της τάσης όμως κάτω από τα όρια "ασφαλούς λειτουργίας" συμβάλει σημαντικά στην εμφάνιση σφαλμάτων. Επιπρόσθετα, ακόμα δύο παράγοντες οι οποίοι συμβάλουν αθροιστικά στην κακή λειτουργία των κυκλωμάτων είναι η γήρανση του ολοκληρωμένου κυκλώματος, αλλά και εξωγενείς παράγοντες, όπως είναι η κοσμική ακτινοβολία. Στο πρώτο μέρος της διατριβής γίνεται μια επισκόπηση της κρισιμότητας της ανοχής σφαλμάτων στο υποσύστημα κρυφής μνήμης ενός επεξεργαστικού συστήματος και παρουσιάζονται οι βασικές μεθοδολογίες αντιμετώπισης του προβλήματος. Πιο συγκεκριμένα, στο κεφάλαιο 1, δίνεται μια σύντομη περιγραφή των χαρακτηριστικών των δομών κρυφής μνήμης και παρουσιάζεται το πρόβλημα αξιοπιστίας του. Στη συνέχεια παρουσιάζουμε τις μεθοδολογίες που έχουν προταθεί στη βιβλιογραφία και έχουν σκοπό την αντιμετώπιση του προβλήματος της αξιοπιστίας των κρυφών μνημών και τις κατατάσσουμε σε δύο βασικές κατηγορίες. Τέλος, γίνεται αναγωγή του προβλήματος της παρουσίας σφαλμάτων στις δομές μνήμης, στο πρόβλημα της μείωσης της απόδοσης, αλλά και το πρόβλημα της διακύμανσης (μη-προβλεψιμότητας) της απόδοσης. Τα δύο προβλήματα αυτά είναι ο κύριος λόγος για τον οποίο καθίσταται επιτακτική η ανάγκη μεθοδολογιών αντιμετώπισής τους και αποτελούν το κίνητρο της διδακτορικής διατριβής. Στο κεφάλαιο 2 συγκεκριμενοποιούμε το πρόβλημα στην παρουσία στοιχείων μνήμης που δεν λειτουργούν σύμφωνα με τις προδιαγραφές τους. Γίνεται μια παρουσίαση των μοντέλων σφαλμάτων, τα οποία χρησιμοποιούνται για να περιγράψουν τα χαρακτηριστικά και τη φύση των σφαλμάτων στα ολοκληρωμένα κυκλώματα. Στη συνέχεια, γίνεται μια αναφορά στον αριθμό, αλλά και στην διασπορά των στοιχείων μνήμης που πιθανοτικά δεν θα λειτουργούν βάση των αρχικών προδιαγραφών καθώς μεταβάλλονται οι τεχνολογίες ολοκλήρωσης, αλλά και το επίπεδο της τάσης τροφοδοσίας (κοντά στο κατώφλι δυναμικού των τρανζίστορ). Τέλος, στην ενότητα αυτή παρουσιάζονται οι βασικές έννοιες που θα χρησιμοποιηθούν στην συνέχεια της διατριβής. Το κεφάλαιο 3 παρουσιάζει το περιβάλλον εξομοίωσης καθώς και τις επεκτάσεις που ήταν απαραίτητες για να μπορέσουμε να αξιολογήσουμε τις προτεινόμενες μεθοδολογίες που αναπτύχτηκαν στα πλαίσια της διατριβής. Παρουσιάζουμε τα εργαλεία και τις τεχνικές που χρησιμοποιήθηκαν για την υλοποίηση και την αποτίμηση της απόδοσης των προτεινόμενων μεθοδολογιών καθώς επίσης και της αξιοπιστίας των αποτελεσμάτων. Παρουσιάζουμε τα δυο περιβάλλοντα εξομοίωσης που χρησιμοποιήσαμε και αξιολογούμε τα πλεονεκτήματα και τα μειονεκτήματα του καθενός. Το πρώτο βασίζεται πάνω σε έναν ευρέως διαδεδομένο αρχιτεκτονικό εξομοιωτή, ο οποίος επεκτάθηκε έτσι ώστε να υποστηρίζει την εξομοίωση δομών μνήμης που περιέχουν σφάλματα. Το δεύτερο αναπτύχθηκε εξολοκλήρου για τους σκοπούς της διατριβής αυτής και βασίζεται στην ανάγνωση από αρχείο των προσπελάσεων του συστήματος μνήμης που θέλουμε να μελετήσουμε. Κλείνοντας το κεφάλαιο αυτό παρουσιάζουμε τις οικογένειες μετροπρογραμμάτων (benchmarks suites) που χρησιμοποιήθηκαν για την αξιολόγηση των προτεινόμενων μεθοδολογιών. Στη συνέχεια της διατριβής παρουσιάζουμε τις προτεινόμενες μεθοδολογίες που αναπτύχθηκαν στα πλαίσια του διδακτορικού. Στο κεφάλαιο 4 παρουσιάζουμε μια μεθοδολογία ανοχής σφαλμάτων που βασίζεται στη χρήση κωδίκων ανίχνευσης και διόρθωσης σφαλμάτων. Πιο συγκεκριμένα, αναλύεται πως το πρόβλημα της χρήσης κωδίκων ανίχνευσης και διόρθωσης λαθών στις κρυφές μνήμες πρώτου επιπέδου, είναι η μεγάλη καθυστέρηση που εισάγουν κατά τη διόρθωση των λαθών. Η καθυστέρηση αυτή είναι ανάλογη του αριθμού των λαθών που μπορούν να διορθωθούν από τον εκάστοτε κώδικα. Η προτεινόμενη μεθοδολογία προσπαθεί να προβλέψει την κρισιμότητα της προς εκτέλεση εντολής. Η πληροφορία της πρόβλεψης έχει διπλή σημασία. Στην περίπτωση που υπάρχει αστοχία εύρεσης του ζητούμενου δεδομένου στην κρυφή μνήμη πρώτου επιπέδου, η πρόβλεψη αυτή επηρεάζει τον αλγόριθμό αντικατάστασης. Ενώ στην περίπτωση που το δεδομένο βρέθηκε στην κρυφή μνήμη τότε η πρόβλεψη της κρισιμότητας της εντολής καθορίζει τον κώδικα ανίχνευσης και διόρθωσης σφαλμάτων που θα εφαρμοστεί. Στο κεφάλαιο 5 περιγράφεται μια μεθοδολογία που βασίζεται στη χρήση μιας επιπλέον πολύ μικρής μνήμης που λειτουργεί συνεργατικά με την κρυφή μνήμη πρώτου επιπέδου. Αυτή η νέα μνήμη λειτουργεί ως παράγοντας ανάκτησης της απώλειας απόδοσης λόγω των απενεργοποιημένων ελαττωματικών μπλοκ της κρυφής μνήμης πρώτου επιπέδου (spare cache), ενώ παράλληλα αποθηκεύει τα μπλοκ που επιλέχθηκαν προς αντικατάσταση από την κρυφή μνήμη (victim-cache). Στο κεφάλαιο 6 περιγράφεται μια νέα μεθοδολογία, η οποία βασίζεται στη πρόβλεψη της χωρικής τοπικότητας των μπλοκ μνήμης που εισάγονται στις κρυφές μνήμες πρώτου επιπέδου. Γίνεται μια εκτενής αξιολόγηση των μηχανισμών πρόβλεψης της χωρικής τοπικότητας των αναφορών μνήμης και καταλήγουμε στη σχεδίαση ενός νέου μηχανισμού με ελάχιστες απαιτήσεις σε υλικό που διατηρεί παράλληλα την ορθότητα και την αξιοπιστία των προβλέψεων. Η μεθοδολογία αυτή αντλεί τα οφέλη της από την καλύτερη διαχείριση της κρυφής μνήμης που δεν περιέχει σφάλματα βελτιώνοντας τον αλγόριθμο εισαγωγής και αντικατάστασης των κρυφών μνημών λαμβάνοντας υπόψιν την χωρική τοπικότητα των αναφορών μνήμης. Στο Κεφάλαιο 7, παρουσιάζεται μια μεθοδολογία που αξιοποιεί επιπλέον υλικό και έχει τη δυνατότητα να προσαρμόζει στατικά το μέγεθος του μπλοκ της κρυφής μνήμης πρώτου επιπέδου με βάση τον αριθμό των σφαλμάτων. Το μέγεθος του μπλοκ αλλάζει σε συνδιασμό με τη μεταβολη της οργάνωσης του συνόλου συσχέτισης της κρυφής μνήμης. Αυτό διασφαλίζει ότι η δομή δεδομένων της κρυφής μνήμης παραμένει αμετάβλητη και οι απαιτούμενες τροποποιήσεις στην υποκείμενη αρχιτεκτονική της κρυφής μνήμης περιορίζονται στο ελάχιστο. Κλείνοντας το Κεφάλαιο 7, αναλύεται το ερώτημα του καταλληλότερου τύπου πλεονασμού σε επίπεδο υλικού για την αποθήκευση δεδομένων ή πληροφορίας ελέγχου (επιπλέον πεδία ετικέτας (tag) και ψηφίων κατάστησης (status bits). Στα κεφάλαια 8 και 9 περιγράφονται δύο επιπλέον μεθοδολογίες που βασίζονται στη διαφορετική συμπεριφορά των φάσεων του εκτελούμενου προγράμματος σε σχέση με την παρουσία σφαλμάτων στο υποσύστημα μνήμης. Ανάγουμε το πρόβλημα όχι μόνο σε επίπεδο πλήθους σφαλμάτων, αλλά μελετάμε την συμπεριφορά των διαφορετικών εφαρμογών και των διαφορετικών φάσεων της ίδιας εφαρμογής σε σχέση με την παρουσία σφαλμάτων. Οι δυο μεθοδολογίες που παρουσιάζονται έχουν κοινό στοιχείο τον ανά τακτά χρονικά διαστήματα έλεγχο και αναπροσαρμογή σε πραγματικό χρόνο της οργάνωσης της κρυφής μνήμης, ώστε οι νέες διαμορφώσεις να αυξάνουν την απόδοση του συστήματος. Παρουσιάζονται οι δύο προτεινόμενοι μηχανισμοί αξιολόγησης και αναδιαμόρφωσης, οι οποίοι βασίζονται στη διαμέριση του χρόνου σε παράθυρά. Επιπρόσθετα, γίνεται ανάλυση του τρόπου μείωσης τον κοστοβόρων (από άποψη απόδοσης αλλά και καταναλισκόμενης ενέργειας) ενεργειών που πρέπει να εκτελεστούν πριν την εκάστοτε αναδιαμόρφωση των κρυφών μνημών πρώτου επιπέδου. Στο κεφάλαιο 9 εξετάζουμε το πρόβλημα της προβλεψιμότητας του χρόνου εκτέλεσης ενός προγράμματος, όταν εκτελείται σε επεξεργαστικό σύστημα στο οποίο το υποσύστημα μνήμης έχει εσφαλμένα κελιά. Σε συστήματα που εκτελούν κρίσιμες εφαρμογές υπάρχουν αυστηρά ορισμένα χρονικά παράθυρα που πρέπει να ολοκληρωθούν από συγκεκριμένες διεργασίες. Όπως αποδεικνύεται, η παρουσία σφαλμάτων στις κρυφές μνήμες συμβάλει σημαντικά στην απροσδιοριστία του χρόνου που θα χρειαστεί για να ολοκληρωθεί μια εφαρμογή. Η μεθοδολογία που παρουσιάζεται στο συγκεκριμένο κεφάλαιο έχει στόχο την αύξηση της προβλεψιμότητας του χρόνου εκτέλεσης, αλλά ταυτόχρονα και στην μείωση της επίδρασης των σφαλμάτων στην απόδοση του συστήματος μνήμης. Ως αποτέλεσμα, αυτή η μεθοδολογία καταφέρνει να βελτιώσει με επιτυχία τη συνολική ποιότητα των υπηρεσιών που παρέχονται στον τελικό χρήστη. Τέλος, το κεφάλαιο 10 ολοκληρώνει την διατριβή µε την παράθεση γενικών συμπερασμάτων και κατευθύνσεων για μελλοντική έρευνα. Επίσης, παρατίθενται οι δημοσιευμένες εργασίες πάνω στα ερευνητικά αποτελέσματα της διατριβής, καθώς και μια λίστα δημοσιεύσεων άλλων ερευνητικών ομάδων, στις οποίες χρησιμοποιούνται ως αναφορές οι εργασίες αυτές.