Περίληψη
Η πρόοδος στις τεχνολογίες ολοκλήρωσης έχει συμβάλει καθοριστικά στην εξέλιξη των ολοκληρωμένων κυκλωμάτων τα οποία αποτελούνται από ένα μεγάλο και ολοένα αυξανόμενο αριθμό τρανζίστορ. Ωστόσο όσο προχωράμε σε μικρότερες τεχνολογίες ολοκλήρωσης αυξάνεται σημαντικά ο αριθμός των ελλαττωματικών στοιχείων που απαρτίζουν τα ολοκληρωμένα κυκλώματα, δηλαδή των τρανζίστορ, τα οποία δεν λειτουργούν σύμφωνα με τις αρχικές τους προδιαγραφές. Σύγχρονες μελέτες έχουν δείξει πως η πιθανότητα ύπαρξης ελαττωματικών τρανζίστορ αυξάνεται σημαντικά καθώς η τεχνολογία ολοκλήρωσης αγγίζει τα όρια των νόμων της φυσικής για την κατασκευή ηλεκτρονικών στοιχείων με τη χρήση πυριτίου. Αυτή η διατριβή προτείνει μεθοδολογίες για τoν περιορισμό της υποβάθμισης της απόδοσης καθώς επίσης και της διακύμανσης της απόδοσης που προκαλούνται από ελαττώματα στις κρυφές μνήμες ενός επεξεργαστή. Έμφαση δίνεται στα στοιχεία μνήμης για δύο κύριους λόγους. Αρχικά οι δομές μνήμης καταλαμβάνουν ένα πολύ μεγάλο μέρος της επιφάνει ...
Η πρόοδος στις τεχνολογίες ολοκλήρωσης έχει συμβάλει καθοριστικά στην εξέλιξη των ολοκληρωμένων κυκλωμάτων τα οποία αποτελούνται από ένα μεγάλο και ολοένα αυξανόμενο αριθμό τρανζίστορ. Ωστόσο όσο προχωράμε σε μικρότερες τεχνολογίες ολοκλήρωσης αυξάνεται σημαντικά ο αριθμός των ελλαττωματικών στοιχείων που απαρτίζουν τα ολοκληρωμένα κυκλώματα, δηλαδή των τρανζίστορ, τα οποία δεν λειτουργούν σύμφωνα με τις αρχικές τους προδιαγραφές. Σύγχρονες μελέτες έχουν δείξει πως η πιθανότητα ύπαρξης ελαττωματικών τρανζίστορ αυξάνεται σημαντικά καθώς η τεχνολογία ολοκλήρωσης αγγίζει τα όρια των νόμων της φυσικής για την κατασκευή ηλεκτρονικών στοιχείων με τη χρήση πυριτίου. Αυτή η διατριβή προτείνει μεθοδολογίες για τoν περιορισμό της υποβάθμισης της απόδοσης καθώς επίσης και της διακύμανσης της απόδοσης που προκαλούνται από ελαττώματα στις κρυφές μνήμες ενός επεξεργαστή. Έμφαση δίνεται στα στοιχεία μνήμης για δύο κύριους λόγους. Αρχικά οι δομές μνήμης καταλαμβάνουν ένα πολύ μεγάλο μέρος της επιφάνειας του ολοκληρωμένου του επεξεργαστή (μάλιστα το συγκεκριμένο ποσοστό αυξάνεται καθώς μεταβαίνουμε σε πολυπύρηνα επεξεργαστικά συστήματα). Ο δεύτερος λόγος είναι ότι οι δομές μνήμης υλοποιούνται με τρανζίστορ ελάχιστου μεγέθους, τα οποία έχουν ως αποτέλεσμα την αύξηση της ευαισθησίας της λειτουργίας των ολοκληρωμένων κυκλωμάτων στις διακυμάνσεις των χαρακτηριστικών κατασκευής τους, της τάσης τροφοδοσίας και της θερμοκρασίας. Οι αυξανόμενες απαιτήσεις για μείωση της κατανάλωσης ισχύος των ολοκληρωμένων κυκλωμάτων οδηγούν ολοένα και περισσότερο στην ανάγκη για μείωση της τάσης τροφοδοσίας σε συνδυασμό με την μείωση της συχνότητας λειτουργίας. Η τάση τροφοδοσίας έχει σημαντικό αντίκτυπο στην μείωση της δυναμικής ισχύος, εξαιτίας του τετραγώνου στην σχέση που τις συνδέει. Η πτώση της τάσης όμως κάτω από τα όρια "ασφαλούς λειτουργίας" συμβάλει σημαντικά στην εμφάνιση σφαλμάτων. Επιπρόσθετα, ακόμα δύο παράγοντες οι οποίοι συμβάλουν αθροιστικά στην κακή λειτουργία των κυκλωμάτων είναι η γήρανση του ολοκληρωμένου κυκλώματος, αλλά και εξωγενείς παράγοντες, όπως είναι η κοσμική ακτινοβολία. Στο πρώτο μέρος της διατριβής γίνεται μια επισκόπηση της κρισιμότητας της ανοχής σφαλμάτων στο υποσύστημα κρυφής μνήμης ενός επεξεργαστικού συστήματος και παρουσιάζονται οι βασικές μεθοδολογίες αντιμετώπισης του προβλήματος. Πιο συγκεκριμένα, στο κεφάλαιο 1, δίνεται μια σύντομη περιγραφή των χαρακτηριστικών των δομών κρυφής μνήμης και παρουσιάζεται το πρόβλημα αξιοπιστίας του. Στη συνέχεια παρουσιάζουμε τις μεθοδολογίες που έχουν προταθεί στη βιβλιογραφία και έχουν σκοπό την αντιμετώπιση του προβλήματος της αξιοπιστίας των κρυφών μνημών και τις κατατάσσουμε σε δύο βασικές κατηγορίες. Τέλος, γίνεται αναγωγή του προβλήματος της παρουσίας σφαλμάτων στις δομές μνήμης, στο πρόβλημα της μείωσης της απόδοσης, αλλά και το πρόβλημα της διακύμανσης (μη-προβλεψιμότητας) της απόδοσης. Τα δύο προβλήματα αυτά είναι ο κύριος λόγος για τον οποίο καθίσταται επιτακτική η ανάγκη μεθοδολογιών αντιμετώπισής τους και αποτελούν το κίνητρο της διδακτορικής διατριβής. Στο κεφάλαιο 2 συγκεκριμενοποιούμε το πρόβλημα στην παρουσία στοιχείων μνήμης που δεν λειτουργούν σύμφωνα με τις προδιαγραφές τους. Γίνεται μια παρουσίαση των μοντέλων σφαλμάτων, τα οποία χρησιμοποιούνται για να περιγράψουν τα χαρακτηριστικά και τη φύση των σφαλμάτων στα ολοκληρωμένα κυκλώματα. Στη συνέχεια, γίνεται μια αναφορά στον αριθμό, αλλά και στην διασπορά των στοιχείων μνήμης που πιθανοτικά δεν θα λειτουργούν βάση των αρχικών προδιαγραφών καθώς μεταβάλλονται οι τεχνολογίες ολοκλήρωσης, αλλά και το επίπεδο της τάσης τροφοδοσίας (κοντά στο κατώφλι δυναμικού των τρανζίστορ). Τέλος, στην ενότητα αυτή παρουσιάζονται οι βασικές έννοιες που θα χρησιμοποιηθούν στην συνέχεια της διατριβής. Το κεφάλαιο 3 παρουσιάζει το περιβάλλον εξομοίωσης καθώς και τις επεκτάσεις που ήταν απαραίτητες για να μπορέσουμε να αξιολογήσουμε τις προτεινόμενες μεθοδολογίες που αναπτύχτηκαν στα πλαίσια της διατριβής. Παρουσιάζουμε τα εργαλεία και τις τεχνικές που χρησιμοποιήθηκαν για την υλοποίηση και την αποτίμηση της απόδοσης των προτεινόμενων μεθοδολογιών καθώς επίσης και της αξιοπιστίας των αποτελεσμάτων. Παρουσιάζουμε τα δυο περιβάλλοντα εξομοίωσης που χρησιμοποιήσαμε και αξιολογούμε τα πλεονεκτήματα και τα μειονεκτήματα του καθενός. Το πρώτο βασίζεται πάνω σε έναν ευρέως διαδεδομένο αρχιτεκτονικό εξομοιωτή, ο οποίος επεκτάθηκε έτσι ώστε να υποστηρίζει την εξομοίωση δομών μνήμης που περιέχουν σφάλματα. Το δεύτερο αναπτύχθηκε εξολοκλήρου για τους σκοπούς της διατριβής αυτής και βασίζεται στην ανάγνωση από αρχείο των προσπελάσεων του συστήματος μνήμης που θέλουμε να μελετήσουμε. Κλείνοντας το κεφάλαιο αυτό παρουσιάζουμε τις οικογένειες μετροπρογραμμάτων (benchmarks suites) που χρησιμοποιήθηκαν για την αξιολόγηση των προτεινόμενων μεθοδολογιών. Στη συνέχεια της διατριβής παρουσιάζουμε τις προτεινόμενες μεθοδολογίες που αναπτύχθηκαν στα πλαίσια του διδακτορικού. Στο κεφάλαιο 4 παρουσιάζουμε μια μεθοδολογία ανοχής σφαλμάτων που βασίζεται στη χρήση κωδίκων ανίχνευσης και διόρθωσης σφαλμάτων. Πιο συγκεκριμένα, αναλύεται πως το πρόβλημα της χρήσης κωδίκων ανίχνευσης και διόρθωσης λαθών στις κρυφές μνήμες πρώτου επιπέδου, είναι η μεγάλη καθυστέρηση που εισάγουν κατά τη διόρθωση των λαθών. Η καθυστέρηση αυτή είναι ανάλογη του αριθμού των λαθών που μπορούν να διορθωθούν από τον εκάστοτε κώδικα. Η προτεινόμενη μεθοδολογία προσπαθεί να προβλέψει την κρισιμότητα της προς εκτέλεση εντολής. Η πληροφορία της πρόβλεψης έχει διπλή σημασία. Στην περίπτωση που υπάρχει αστοχία εύρεσης του ζητούμενου δεδομένου στην κρυφή μνήμη πρώτου επιπέδου, η πρόβλεψη αυτή επηρεάζει τον αλγόριθμό αντικατάστασης. Ενώ στην περίπτωση που το δεδομένο βρέθηκε στην κρυφή μνήμη τότε η πρόβλεψη της κρισιμότητας της εντολής καθορίζει τον κώδικα ανίχνευσης και διόρθωσης σφαλμάτων που θα εφαρμοστεί. Στο κεφάλαιο 5 περιγράφεται μια μεθοδολογία που βασίζεται στη χρήση μιας επιπλέον πολύ μικρής μνήμης που λειτουργεί συνεργατικά με την κρυφή μνήμη πρώτου επιπέδου. Αυτή η νέα μνήμη λειτουργεί ως παράγοντας ανάκτησης της απώλειας απόδοσης λόγω των απενεργοποιημένων ελαττωματικών μπλοκ της κρυφής μνήμης πρώτου επιπέδου (spare cache), ενώ παράλληλα αποθηκεύει τα μπλοκ που επιλέχθηκαν προς αντικατάσταση από την κρυφή μνήμη (victim-cache). Στο κεφάλαιο 6 περιγράφεται μια νέα μεθοδολογία, η οποία βασίζεται στη πρόβλεψη της χωρικής τοπικότητας των μπλοκ μνήμης που εισάγονται στις κρυφές μνήμες πρώτου επιπέδου. Γίνεται μια εκτενής αξιολόγηση των μηχανισμών πρόβλεψης της χωρικής τοπικότητας των αναφορών μνήμης και καταλήγουμε στη σχεδίαση ενός νέου μηχανισμού με ελάχιστες απαιτήσεις σε υλικό που διατηρεί παράλληλα την ορθότητα και την αξιοπιστία των προβλέψεων. Η μεθοδολογία αυτή αντλεί τα οφέλη της από την καλύτερη διαχείριση της κρυφής μνήμης που δεν περιέχει σφάλματα βελτιώνοντας τον αλγόριθμο εισαγωγής και αντικατάστασης των κρυφών μνημών λαμβάνοντας υπόψιν την χωρική τοπικότητα των αναφορών μνήμης. Στο Κεφάλαιο 7, παρουσιάζεται μια μεθοδολογία που αξιοποιεί επιπλέον υλικό και έχει τη δυνατότητα να προσαρμόζει στατικά το μέγεθος του μπλοκ της κρυφής μνήμης πρώτου επιπέδου με βάση τον αριθμό των σφαλμάτων. Το μέγεθος του μπλοκ αλλάζει σε συνδιασμό με τη μεταβολη της οργάνωσης του συνόλου συσχέτισης της κρυφής μνήμης. Αυτό διασφαλίζει ότι η δομή δεδομένων της κρυφής μνήμης παραμένει αμετάβλητη και οι απαιτούμενες τροποποιήσεις στην υποκείμενη αρχιτεκτονική της κρυφής μνήμης περιορίζονται στο ελάχιστο. Κλείνοντας το Κεφάλαιο 7, αναλύεται το ερώτημα του καταλληλότερου τύπου πλεονασμού σε επίπεδο υλικού για την αποθήκευση δεδομένων ή πληροφορίας ελέγχου (επιπλέον πεδία ετικέτας (tag) και ψηφίων κατάστησης (status bits). Στα κεφάλαια 8 και 9 περιγράφονται δύο επιπλέον μεθοδολογίες που βασίζονται στη διαφορετική συμπεριφορά των φάσεων του εκτελούμενου προγράμματος σε σχέση με την παρουσία σφαλμάτων στο υποσύστημα μνήμης. Ανάγουμε το πρόβλημα όχι μόνο σε επίπεδο πλήθους σφαλμάτων, αλλά μελετάμε την συμπεριφορά των διαφορετικών εφαρμογών και των διαφορετικών φάσεων της ίδιας εφαρμογής σε σχέση με την παρουσία σφαλμάτων. Οι δυο μεθοδολογίες που παρουσιάζονται έχουν κοινό στοιχείο τον ανά τακτά χρονικά διαστήματα έλεγχο και αναπροσαρμογή σε πραγματικό χρόνο της οργάνωσης της κρυφής μνήμης, ώστε οι νέες διαμορφώσεις να αυξάνουν την απόδοση του συστήματος. Παρουσιάζονται οι δύο προτεινόμενοι μηχανισμοί αξιολόγησης και αναδιαμόρφωσης, οι οποίοι βασίζονται στη διαμέριση του χρόνου σε παράθυρά. Επιπρόσθετα, γίνεται ανάλυση του τρόπου μείωσης τον κοστοβόρων (από άποψη απόδοσης αλλά και καταναλισκόμενης ενέργειας) ενεργειών που πρέπει να εκτελεστούν πριν την εκάστοτε αναδιαμόρφωση των κρυφών μνημών πρώτου επιπέδου. Στο κεφάλαιο 9 εξετάζουμε το πρόβλημα της προβλεψιμότητας του χρόνου εκτέλεσης ενός προγράμματος, όταν εκτελείται σε επεξεργαστικό σύστημα στο οποίο το υποσύστημα μνήμης έχει εσφαλμένα κελιά. Σε συστήματα που εκτελούν κρίσιμες εφαρμογές υπάρχουν αυστηρά ορισμένα χρονικά παράθυρα που πρέπει να ολοκληρωθούν από συγκεκριμένες διεργασίες. Όπως αποδεικνύεται, η παρουσία σφαλμάτων στις κρυφές μνήμες συμβάλει σημαντικά στην απροσδιοριστία του χρόνου που θα χρειαστεί για να ολοκληρωθεί μια εφαρμογή. Η μεθοδολογία που παρουσιάζεται στο συγκεκριμένο κεφάλαιο έχει στόχο την αύξηση της προβλεψιμότητας του χρόνου εκτέλεσης, αλλά ταυτόχρονα και στην μείωση της επίδρασης των σφαλμάτων στην απόδοση του συστήματος μνήμης. Ως αποτέλεσμα, αυτή η μεθοδολογία καταφέρνει να βελτιώσει με επιτυχία τη συνολική ποιότητα των υπηρεσιών που παρέχονται στον τελικό χρήστη. Τέλος, το κεφάλαιο 10 ολοκληρώνει την διατριβή µε την παράθεση γενικών συμπερασμάτων και κατευθύνσεων για μελλοντική έρευνα. Επίσης, παρατίθενται οι δημοσιευμένες εργασίες πάνω στα ερευνητικά αποτελέσματα της διατριβής, καθώς και μια λίστα δημοσιεύσεων άλλων ερευνητικών ομάδων, στις οποίες χρησιμοποιούνται ως αναφορές οι εργασίες αυτές.
περισσότερα
Περίληψη σε άλλη γλώσσα
Progress in integration technologies has played a crucial role in the evolution of integrated circuits, which consist of a large and increasingly growing number of transistors. On the other hand, as we progress towards smaller integration technologies, the number of defective elements significantly increases. These defective elements include transistors or memory structures that do not operate according to the initial specifications. Modern studies have shown that the probability of having defective transistors increases significantly as integration technology approaches the limits of the laws of physics for the construction of electronic components using silicon. This dissertation proposes methodologies for the reduction of the performance degradation and performance variance caused by faults in the memory structures of CPU caches. The focus is on memory elements for two main reasons. Firstly, memory structures occupy a very large portion of the processor (this percentage increases as ...
Progress in integration technologies has played a crucial role in the evolution of integrated circuits, which consist of a large and increasingly growing number of transistors. On the other hand, as we progress towards smaller integration technologies, the number of defective elements significantly increases. These defective elements include transistors or memory structures that do not operate according to the initial specifications. Modern studies have shown that the probability of having defective transistors increases significantly as integration technology approaches the limits of the laws of physics for the construction of electronic components using silicon. This dissertation proposes methodologies for the reduction of the performance degradation and performance variance caused by faults in the memory structures of CPU caches. The focus is on memory elements for two main reasons. Firstly, memory structures occupy a very large portion of the processor (this percentage increases as we move towards multi-core processing systems). The second reason is memory structures are implemented with minimal-sized transistors, which are more sensitive to process variations. Increasing demands for reducing power consumption of integrated circuits lead to a growing need to reduce the supply voltage in combination with a decrease in operating frequency. The supply voltage has a significant impact on reducing dynamic power due to the square term in the relationship that connects them. However, a drop in voltage below the "safe operating" limits significantly contributes to the occurrence of faults. Additionally, two factors that cumulatively contribute to the number of malfunctioning circuits are their aging and external factors, such as cosmic radiation. In the first part of the dissertation, an overview of the importance of fault tolerance in the cache memory subsystem of a processing system is provided, and the basic methodologies for addressing the problem are presented. More specifically, in Chapter 1, a brief description of the characteristics of cache memory structures is given, and the reliability issue is introduced. Then, we present the methodologies that have been proposed in the literature aimed at addressing the problem of reliability of cache memories and classify them into two main categories. Finally, the problem of the presence of faults in cache memory structures is reduced to the problem of performance degradation, as well as the problem of performance variance (unpredictability). These two problems are the main reason for the imperative need for methodologies to address them and constitute the motivation for the doctoral dissertation. In Chapter 2, we specify the problem in the presence of memory elements that do not operate according to their specifications. A presentation of fault models is made, which are used to describe the characteristics and the nature of faults in integrated circuits. Following that, a reference is made to the number, as well as to the dispersion of the malfunctioning memory elements as the technology scaling continues, as well as the level of supply voltage reduces (near to the threshold voltage of transistors). Finally, this section presents the basic concepts that will be used in the continuation of the dissertation. Chapter 3 presents the simulation environment and the necessary extensions developed to evaluate the proposed methodologies. The tools and techniques used for the implementation and performance evaluation of the proposed methodologies, as well as the reliability of the results, are introduced. Two simulation environments are presented, and the advantages and disadvantages of each are evaluated. The first environment is based on a widely used architectural simulator, expanded to support the simulation of memory structures containing faulty elements. The second environment was developed entirely for the purposes of this dissertation and is based on reading memory system accesses from a file for study. Closing this chapter, the benchmark suites used for evaluating the proposed methodologies are presented. In the following sections of the dissertation, we present the proposed methodologies developed as part of the doctoral research. In Chapter 4, we introduce a fault tolerance methodology based on the use of error detection and correction codes. Specifically, it analyzes how the problem of using error detection and correction codes introduces significant delays during error correction, rendering them not suitable for time-sensitive first-level caches. This delay is proportional to the number of errors that the code needs to correct. The proposed methodology attempts to predict the criticality of the instruction to be executed. The prediction information has dual significance: in the case of a cache miss in the first-level cache memory, this prediction affects the replacement algorithm, while in the case where the data is found in the cache memory, the prediction of the instruction's criticality determines the error detection and correction code to be applied. Chapter 5, a methodology is described that relies on the use of an additional very small memory that operates collaboratively with the first-level cache memory. This new memory serves as an agent recovering the performance loss due to disabled faulty blocks of cache memory (spare cache) and also captures the evicted blocks in order to reduce conflict misses of the cache memory (victim-cache).Chapter 6 describes a new methodology based on predicting the spatial locality of the memory blocks introduced into the first-level cache memories. A comprehensive evaluation of memory reference spatial locality prediction mechanisms is performed, leading to the design of a new mechanism with minimal hardware requirements that maintains the correctness and reliability of predictions. This methodology benefits from improved management of the fault-free cache memory utilization, enhancing the input and replacement algorithm of cache memories by considering the spatial locality of memory references. In Chapter 7, a methodology is presented that utilizes additional hardware and has the ability to statically adapt the size of the first-level cache memory block based on the number of faults. The block size changes in coordination with the cache associativity. This ensures that the cache's data structure remains unchanged, and the necessary modifications to the underlying cache architecture are minimized. Closing Chapter 7, the question of the most appropriate type of redundancy (additional storage area) for storing data or control based information (extra tag and status bits) is analyzed. In Chapters 8 and 9, two additional methodologies are described, based on the different behavior of the phases of the executed program concerning the presence of faults in the memory subsystem. The problem is elevated not only to the level of the number of faults but also studies the behavior of different applications and different program phases of the same application concerning the presence of faults. The two presented methodologies share the element of periodic real-time control and adaptation of the organization of the cache memory to increase the system's performance. The two proposed evaluation and reconfiguration mechanisms, based on time window division, are presented. Additionally, an analysis is conducted on how to reduce costly (in terms of performance and consumed energy) actions that need to be performed before each reconfiguration of the first-level cache memories. In Chapter 9, the problem of predicting the execution time of a program is examined when running on a processing system in which the memory subsystem has faulty cells. In systems executing critical applications, there are strictly defined time constraints that must be met by specific processes. As demonstrated, the presence of faults in cache memories significantly contributes to the uncertainty of the time needed to complete an application. The methodology presented in this chapter aims to increase the predictability of execution time while simultaneously reducing the impact of faults on the performance of the memory subsystem. As a result, this methodology manages to improve the overall quality of service delivered to the end user. Finally, Chapter 10 concludes the dissertation by providing general conclusions and directions for future research. It also includes the publications based on the research results of the dissertation and the citations.
περισσότερα