Παράδειγμα 3o
Έστω ότι υπάρχουν τρεις μικρές κρυφές μνήμες, η κάθε μια από τις οποίες αποτελείται από τέσσερα μπλοκ μιας λέξης. Η πρώτη κρυφή μνήμη είναι πλήρως συσχετιστική, η δεύτερη είναι 2-δρόμων συνολο-συσχετιστική, ενώ η τρίτη είναι άμεσης αντιστοίχησης. Αν θεωρήσουμε ότι η τεχνική αντικατάστασης που χρησιμοποιείται είναι η LRU, υπολογίστε τον αριθμό των αποτυχιών σε κάθε οργάνωση της κρυφής μνήμης, αν δοθούν οι ακόλουθες διευθύνσεις μπλοκ: 0,8,0,6,8.
AπάντησηΗ ευκολότερη περίπτωση είναι εκείνη της κρυφής μνήμης άμεσης αντιστοίχησης. Πρώτα από όλα πρέπει να υπολογίσουμε ποιο μπλοκ της κρυφής μνήμης θα αντιπροσωπέυσει καθένα από τα δοθέντα μπλοκ της κύριας μνήμης. To μπλοκ της κρυφής μνήμης υπολογίζεται συνήθως από τον τύπο: (διεύθυνση του μπλοκ) mod (αριθμός των μπλοκ της κρυφής μνήμης)
Διεύθυνση μπλοκ
| Μπλοκ κρυφής
|
|---|---|
0
| (0 mod 4)=0
|
8
| (8 mod 4)=0
|
6
| (6 mod 4)=2
|
8
| (8 mod 4)=0
|
Τώρα μπορούμε να συμπληρώσουμε την κατάσταση της κρυφής μνήμης μετά από κάθε αναφορά στη μνήμη. Αρχικά ζητάμε να επεξεργαστούν τα δεδομένα που βρίσκονται στη διεύθυνση της μνήμης. Επειδή η κρυφή μνήμη είναι κενή έχουμε μια αποτυχία. Έτσι δημιουργούμε τον παρακάτω πίνακα:
Η κρυφή μνήμη άμεσης αντιστοίχησης παράγει πέντε αποτυχίες. Οι περισσότερες αποτυχίες συμβαίνουν γιατί θεωρούμε ότι είναι αρχικά κενή. Στην περίπτωση όμως των δεδομένων που βρίσκονται στη διεύθυνση 8 της κύριας μνήμης, η δεύτερη αναφορά οδηγεί και πάλι σε αποτυχία γιατί αυτά έχουν απομακρυνθεί από την κρυφή μνήμη με την εφαρμογή του αλγόριθμου LRU.
Στη δεύτερη περίπτωση η σύνολο-συσχετιστική κρυφή μνήμη έχει δύο σύνολα, κάθε ένα από τα οποία έχει δύο στοιχεία.Υπολογίζουμε και πάλι το μπλοκ της κρυφής μνήμης, που θα καταλάβει κάθε μπλοκ της κύριας μνήμης στο οποίο αναφερόμαστε.
Διεύθυνση μπλοκ
| Μπλοκ κρυφής
|
|---|---|
0
| (0 mod 4)=0
|
8
| (8 mod 4)=0
|
6
| (6 mod 4)=2
|
8
| (8 mod 4)=0
|
Το σύνολο επιλέγεται με την αντιστοίχηση:
(διεύθυνση του μπλοκ)mod(πλήθος συνόλων στη κρυφή μνήμη).
Επειδή πρέπει να αποφασίσουμε ποια εγγραφή μέσα σε ένα σύνολο θα αντικατασταθεί σε μια αποτυχία, χρειαζόμαστε κάποιους κανόνες αντικατάστασης. Οι σύνολο–συσχετιστικές κρυφές μνήμες χρησιμοποιούν συνήθως LRU αλγόριθμο αντικατάστασης. Έτσι δημιουργείται ο παρακάτω πίνακας:
Η 2-δρόμων σύνολο-συσχετιστική κρυφή μνήμη έχει συνολικά τέσσερις αποτυχίες, μία λιγότερη από την κρυφή μνήμη άμεσης αντιστοίχησης.
Η πλήρως συσχετιστική κρυφή μνήμη έχει 4 μπλοκ σε ένα υποτιθέμενο σύνολο και κάθε μπλοκ της μνήμης μπορεί να τοποθετηθεί σε οποιοδήποτε μπλοκ κρυφής μνήμης. Έτσι δημιουργούμε τον παρακάτω πίνακα που δείχνει την κατάσταση της κρυφής μνήμης.
Η πλήρως συσχετιστική κρυφή μνήμη έχει φανερά την καλύτερη απόδοση, με μόνο τρεις αποτυχίες. Παρατηρούμε ότι αν είχαμε οκτώ μπλοκ στην κρυφή μνήμη, τότε δεν θα χρειαζόταν αντικατάσταση στην 2-δρόμων συνολο-συσχετιστική κρυφή μνήμη και θα είχαμε τον ίδιο αριθμό αποτυχιών με την πλήρως συσχετιστική κρυφή μνήμη. Ομοίως , αν είχαμε 16 μπλοκ και οι τρεις κρυφές μνήμες θα είχαν τον ίδιο αριθμό αποτυχιών.
Το ακόλουθο σχήμα είναι μία συνολο-συσχετιστική κρυφή μνήμη 4-δρόμων που αποτελείται από 4 συγκριτές και 1 πολυπλέκτη. Οι συγκριτές καθορίζουν ποιο από τις 4 ετικέτες ταιριάζουν με την ετικέτα της διεύθυνσης. Η έξοδος των συγκριτών χρησιμοποιείται για την επιλογή των δεδομένων από ενός εκ των 4 δεικτοδοτημένων συνόλων, μέσω ενός πολυπλέκτη.
