Αρχιτεκτονική Υπολογιστών - Κεφάλαιο 4

Mείωση της ποινής αποτυχίας της κρυφής μνήμης

Ο τύπος απόδοσης της κρυφής μνήμης μας επιβεβαιώνει ότι οι βελτιώσεις στις ποινές αποτυχίας μπορούν να είναι το ίδιο ωφέλιμες όπως οι βελτιώσεις στο ρυθμό αποτυχίας. Συνολικά διαθέτουμε 5 τεχνικές βάση των οποίων μεθοδεύουμε την μείωση της ποινής αποτυχίας. Επιγραμματικά είναι οι ακόλουθες:

Προτεραιότητα στις αποτυχίες ανάγνωσης έναντι των αποτυχιών εγγραφής
Τοποθέτηση υπο-μπλοκ για μειωμένη ποινή αποτυχίας
Αποστολή πρώτα της αρχικής κρίσιμης λέξης στη ΚΜΕ
Υλοποίηση κρυφής μνήμης χωρίς μπλοκ για μείωση των καθυστερήσεων κατά τις αποτυχίες κρυφής μνήμης.
Κρυφές μνήμες 2^ου επιπέδου

Aπό τις παραπάνω τεχνικές μόνο η 5^η επικεντρώνεται στη διεπαφή μεταξύ της κρυφής μνήμης και της κύριας μνήμης, ενώ οι πρώτες τέσσερεις μετατοπίζουν τη βαρύτητα στην ΚΜΕ, προκειμένου να μειώσουν την ποινή αποτυχίας. Για το λόγο αυτό θα αναφερθούμε στην 5^η τεχνική, η οποία είναι και η πιο σημαντική, ενώ από τις υπόλοιπες θα μελετήσουμε την 1^η και 2^η ως τις πιο ενδιαφέρουσες.

Προτεραιότητα στις αποτυχίες ανάγνωσης έναντι των αποτυχιών εγγραφής

Μια τεχνική μείωσης της ποινής αποτυχίας είναι να δοθεί προτεραιότητα στις αποτυχίες ανάγνωσης έναντι των αποτυχιών εγγραφής.

ΔΡΑΣΤΗΡΙΟΤΗΤΑ 5

Θυμάστε τον τρόπο με τον οποίο συνδέεται ο καταχωρητής εγγραφής με την ΚΜΕ και την κρυφή μνήμη; Να σχεδιάσετε την υλοποίηση της διεγγραφής με χρήση ενός καταχωρητή εγγραφής. Να συγκρίνετε το σχήμα σας με το σχήμα 4.3.3 που ακολουθεί. Για περισσότερες λεπτομέρειες να ανατρέξετε στην 2^η ενότητα αυτού του κεφαλαίου και συγκεκριμένα στην υποενότητα: «Η λειτουργία της Ανάγνωσης και της Εγγραφής».

Σχήμα 4.3.3 - H θέση ενός καταχωρητή εγγραφής

Σε μία κρυφή μνήμη που υλοποιείται η τεχνική της διεγγραφής για τις εγγραφές, η πιο σημαντική βελτίωση είναι η χρήση ενός καταχωρητή εγγραφής. Οι καταχωρητές εγγραφής ωστόσο περιπλέκουν τις προσπελάσεις στη μνήμη, επειδή μπορεί να καθυστερήσουν την ενημέρωση κάποιου μπλοκ της κύριας μνήμης με διεύθυνση αναγκαία σε μία αποτυχία ανάγνωσης της κρυφής μνήμης. Στο σχήμα 4.3.3 υπενθυμίζουμε την υλοποίηση της διεγγραφής με χρήση ενός καταχωρητή εγγραφής.

Για να μην υπάρχει αυτό το πρόβλημα, η αποτυχία ανάγνωσης πρέπει να περιμένει μέχρι να αδειάσει καταχωρητής εγγραφής. Η εναλλακτική λύση είναι να ελέγχουμε τα περιεχόμενα καταχωρητή εγγραφής σε μια αποτυχία ανάγνωσης και εάν δεν υπάρχουν συγκρούσεις και το σύστημα μνήμης είναι διαθέσιμο, να επιτρέπεται να συνεχίσει η αποτυχία ανάγνωσης.

Παράδειγμα 1^o

Τοποθέτηση υπο-μπλοκ για μειωμένη ποινή αποτυχίας

Τα μεγάλου μεγέθους μπλοκ περιορίζουν το πεδίο ετκέτας χωρίς να μειώνουν την πληροφορία που μπορεί να αποθηκευτεί στη κρυφή μνήμη. Επιπρόσθετα βελτιώνεται ο ρυθμός αποτυχίας με τίμημα την αύξηση της ποινή αποτυχίας. Η λύση δίνεται με την τοποθέτηση υπο-μπλοκ. Ένα bit εγκυρότητας, προστίθεται σε μονάδες πληροφορίας μικρότερες του μπλοκ που ονομάζονται υπο-μπλοκ. Μόνο ένα υπο-μπλοκ διαβάζεται σε μία αποτυχία μνήμης. Το bit εγκυρότητας χαρακτηρίζει κάποια τμήματα του μπλοκ ως έγκυρα και τα υπόλοιπα ως μη έγκυρα. Το γεγονός ότι η ετικέτα ταιριάζει δεν αποτελεί τη μοναδική εγγύηση ότι η λέξη ανήκει στην κρυφή μνήμη. Επιπλέον θα πρέπει να έχει τεθεί τo bit εγκυρότητας. Η διαφορά στην ποινή αποτυχίας για τα υπο-μπλοκ και τα μπλοκ είναι φανερή. Το σχήμα 4.3.4 παρουσιάζει την αποθήκευση της ετικέτας. Εάν τα bit εγκυρότητας αντικατασταθούν από τις πλήρεις ετικέτες, απαιτείται περισσότερη μνήμη.

Σχήμα 4.3.4 - H κρυφή μνήμη άμεσης αντιστοίχησης με 4 υπο-μπλοκ ανά μπλοκ.Τα υπο-μπλοκ μπορούν να θεωρηθούν ως ένα επιπλέον επίπεδο διευθυνσιοδότησης εκτός από την ετικέτα της διεύθυνσης. Στο 1^ο μπλοκ (κορυφή) έχουν τεθεί όλα τα μπλοκ εγκυρότητας, ισοδύναμα έχουν τεθεί τα bit εγκυρότητας για ένα μπλοκ της κρυφής μνήμης. Στο τελευταίο μπλοκ (τελευταία γραμμή) δεν έχει τεθεί κανένα από τα bit. Στο 2^ο μπλοκ στις διευθύνσεις 300, 301 έχουμε επιτυχία ενώ στις 302, 303 αποτυχία. Στο 3^ο μπλοκ στις διευθύνσεις 201, 203 έχουμε επιτυχία . Εάν διαθέταμε 16 μπλοκ με μέγεθος υπο-μπλοκ, θα χρειαζόμασταν 16 αντί 4 ετικέτες. Σε κρυφές μνήμες που υλοποιείται τοποθέτηση υπο-μπλοκ, το μπλοκ δεν λογαριάζεται πλέον ως η ελάχιστη μονάδα πληροφορίας διακινήσιμη μεταξύ κρυφής και κύριας μνήμης, αλλά ως η μονάδα πληροφορίας που σχετίζεται με την ετικέτα διεύθυνσης.

Κρυφές μνήμες 2ου επιπέδου

Με την προσθήκη ενός ακόμη επιπέδου της κρυφής μνήμης μεταξύ της αρχικής κρυφής μνήμης και της κύριας μνήμης, η κρυφή μνήμη 1^ου επιπέδου μπορεί να είναι αρκετά μικρή, τόση ώστε να ταιριάζει με το κύκλο ρολογιού της γρήγορης ΚΜΕ, ενώ η κρυφή μνήμη 2^ουεπιπέδου μπορεί να είναι αρκετά μεγάλη, ώστε να δεσμεύσει πολλές προσπελάσεις που προορίζονται για την κύρια μνήμη. Με αυτόν τον τρόπο μειώνεται η ισχύς της ποινής αποτυχίας.

Αν και η γενική ιδέα της προσθήκης ενός επιπλέον επιπέδου στην ιεραρχία μνήμης είναι ξεκάθαρη, περιπλέκει την ανάλυση της απόδοσης. Οι ορισμοί για μια κρυφή μνήμη δευτέρου επιπέδου δεν είναι πάντα ξεκάθαροι. Ας αρχίσουμε με τον ορισμό του μέσου χρόνου πρόσβασης στην κύρια μνήμη για μια κρυφή μνήμη δύο επιπέδων. Χρησιμοποιώντας τους συμβολισμούς L1 και L2 για να αναφερθούμε στο 1ο και 2ο επίπεδο αντίστοιχα της κρυφής μνήμης ισχύουν τα εξής:

Μέσος χρόνος πρόσβασης στη μνήμη =Χρόνος επιτυχίας_L1+Ρυθμός αποτυχίας_L1x (Ποινή αποτυχίας _L1
Ποινή αποτυχίας _L1=Χρόνος επιτυχίας_L2+Ρυθμός αποτυχίας _L2xΠοινή αποτυχίας_L2
Οπότε
Μέσος χρόνος πρόσβασης στη μνήμη =Χρόνος επιτυχίας _L1+Ρυθμός αποτυχίας _L1 x ( Χρόνος επιτυχίας_L2+ Ρυθμός αποτυχίας_L2x Ποινή αποτυχίας _L2 )

Σε αυτόν τον τύπο ο ρυθμός αποτυχίας 2^ουεπιπέδου υπολογίζεται απο τα κατάλοιπα της κρυφής μνήμης 1^ου επιπέδου. Προς αποφυγή αμφιβολιών αυτοί οι ακόλουθοι όροι υιοθετούνται για ένα σύστημα κρυφής μνήμης δύο επιπέδων

Τοπικός ρυθμός αποτυχίας: Είναι ο αριθμός των αποτυχιών στην κρυφή μνήμη δια του συνολικού αριθμού των προσβάσεων στην κρυφή μνήμη. Αυτό είναι ο ρυθμός αποτυχίας_L2 του παραπάνω τύπου για την κρυφή μνήμη 2^ου επιπέδου.
Καθολικός ρυθμός αποτυχίας: Είναι ο αριθμός των αποτυχιών στην κρυφή μνήμη δια του συνολικού αριθμού των προσβάσεων στην μνήμη που παράγονται από τη ΚΜΕ. Χρησιμοποιώντας τους όρους των παραπάνω τύπων ο καθολικός ρυθμός αποτυχίας του 2^ου επιπέδου κρυφής μνήμης είναι:
Ρυθμός αποτυχίας _L1x Ρυθμός αποτυχίας _L2

ΔΡΑΣΤΗΡΙΟΤΗΤΑ 6

Υποθέτουμε ότι σε 1000 αναφορές στην μνήμη υπάρχουν 40 αποτυχίες σε μια κρυφή μνήμη 1ου επιπέδου και 20 αποτυχίες σε μία κρυφή μνήμη 2ου επιπέδου. Ποιοι είναι οι διάφοροι ρυθμοί αποτυχίας;

ΑΠΑΝΤΗΣΗ ΔΡΑΣΤΗΡΙΟΤΗΤΑΣ 6

Παράδειγμα 2^o

Προκειμένου να μειώσουμε την ποινή αποτυχίας μειώνουμε το ρυθμό αποτυχίας της κρυφής μνήμης 2^ου επιπέδου χρησιμοποιώντας τις τεχνικές που αναφέρθηκαν στην 2^η ενότητα του κεφαλαίου που μελετάμε. Αναφέρουμε ότι η υψηλή συσχετιστικότητα ή ψευδοσυσχετιστικότητα αποτελούν λύσεις γιατί έχουν μικρή επιρροή στον χρόνο επιτυχίας 2^ου επιπέδου και γιατί μέρος του χρόνου πρόσβασης οφείλεται στις αποτυχίες στην κρυφή μνήμη 2^ου επιπέδου. Tο μεγαλύτερο μέγεθος του 2^ου επιπέδου κρυφής μνήμης εξαλοίφει τις συγκρούσεις αποτυχιών διανέμοντας δεδομένα σε περισσότερα μπλοκ, αλλά και τις περισσότερες από τις ικανές αποτυχίες. Παρόλα αυτά, το ποσοστό των αποτυχημένων συγκρούσεων είναι ακόμη σημαντικό στην άμεση αντιστοίχηση 2^ου επιπέδου κρυφής μνήμης.

Μια άλλη προσέγγιση στη μείωση αποτυχιών είναι η αύξηση του μεγέθους μπλοκ στις κρυφές μνήμες 2^ου επιπέδου. Αυξάνοντας το μέγεθος των μπλοκ μπορούμε να αυξήσουμε τις αποτυχίες σύγκρουσης που πραγματοποιούνται σε μικρές κρυφές μνήμες αφού μπορεί να μην υπάρχει αρκετός χώρος για τοποθέτηση δεδομένων και γι 'αυτόν το λόγο αυξάνεται ο ρυθμός αποτυχίας. Επειδή αυτό δεν αποτελεί πρόβλημα για τις κρυφές μνήμες 2^ου επιπέδου και επειδή η πρόσβαση στην μνήμη είναι σχετικά μεγάλη, μεγέθη μπλοκ των 64bytes, 128 bytes και ακόμη και των 256 bytes είναι δημοφιλή.

Μια άλλη σκέψη αναφέρεται στο εάν όλα τα δεδομένα στην κρυφή μνήμη 1^ου επιπέδου είναι πάντα στο 2^ο επιπέδο κρυφής μνήμης. Εάν ναι, το 2^ο επιπέδο κρυφής μνήμης λέγεται ότι έχει την πολυεπίπεδη έγκλειστη ιδιοκτησία. Ο εγκλεισμός είναι σκόπιμος γιατί είναι συνέπεια μεταξύ I/O και κρυφών μνημών (ή μεταξύ κρυφών μνημών σε έναν πολυεπεξεργαστή) και μπορεί να επιτευχθεί με τον έλεγχο του 2^ου επιπέδου κρυφής μνήμης. Το μειονέκτημα σ 'αυτόν τον φυσικό εγκλεισμό είναι ότι ο χαμηλός μέσος χρόνος πρόσβασης στη μνήμη προτείνει μικρότερα μπλοκ για το μικρότερο 1^ο επιπέδο κρυφής μνήμης και μεγαλύτερα μπλοκ για το μεγαλύτερο 2^ο επιπέδο κρυφής μνήμης. Το 2^ο επιπέδο κρυφής μνήμης ακόμη θα πρέπει να ακυρώσει όλα τα 1^ου επιπέδου μπλοκ τα οποία ταιριάζουν στο 2^ου επιπέδου μπλοκ αντικαθιστώντας τα και προκαλώντας έτσι έναν λίγο υψηλότερο ρυθμό αποτυχίας 1^ου επιπέδου. Μπορεί επίσης να προκαλέσει αχρείαστες ακυρώσεις στην κρυφή μνήμη. Ο εγκλεισμός αυξάνει την πολυπλοκότητα όταν συνδέεται με την εκτέλεση βελτιστοποίησης, όπως μια δευτερεύουσα κρυφή μνήμη χωρίς μπλοκ.

Συμπερασματικά η ουσία του σχεδιασμού κρυφής μνήμης 2^ου επιπέδου εξισσοροπεί γρήγορες επιτυχίες και λίγες αποτυχίες. Περισσότερες βελτιστοποιήσεις που βοηθούν το ένα βλάπτουν το άλλο. Για τις κρυφές μνήμες 2^ου επιπέδου υπάρχουν πολύ λιγότερες επιτυχίες από τις κρυφές μνήμες 1^ου επιπέδου. Έτσι η έμφαση μετατοπίζεται στις λιγότερες αποτυχίες. Αυτή η θεώρηση οδηγεί σε μεγαλύτερες κρυφές μνήμες με υψηλή συσχετιστικότητα και μεγαλύτερα μπλοκ.

ΔΡΑΣΤΗΡΙΟΤΗΤΑ 7

Να απαριθμήσετε τις τεχνικές που χρησιμοποιούνται για τη μείωση της ποινής αποτυχίας της κρυφής μνήμης. Ποια από τις τεχνικές αυτές θεωρείται η πιο σημαντική και με ποιον τρόπο αυτή εφαρμόζεται; Να συγκρίνετε την απάντησή σας με την υποενότητα που διαβάσατε: «Μείωση της ποινής αποτυχίας της κρυφής μνήμης».