Πίσω

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

  Δίνεται μια σειρά από διευθύνσεις λέξεων κύριας μνήμης: 1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4,43, 5, 6, 9, 17. Θεωρώντας μια κρυφή μνήμη άμεσης αντιστοίχησης με μέγιστο μέγεθος 16 λέξεις και μέγεθος μπλοκ 4 λέξεις, δείξτε τις επιτυχίες και αποτυχίες κρυφής μνήμης, καθώς και την τελική κατάσταση της κρυφής μνήμης.

Aπάντηση

Ο γενικός τύπος υπολογισμού του μπλοκ της κρυφής μνήμης, στο οποίο θα τοποθετηθεί μια διεύθυνση είναι ο εξής :

Αφού η κρυφή έχει μέγεθος 16 λέξεις και τα μπλοκ είναι 4 λέξεων, τότε ο αριθμός των μπλοκ στην κρυφή μνήμη είναι 4.
Συνεπώς ο αριθμός του μπλοκ που θα τοποθετηθεί κάθε διεύθυνση είναι:

[1/4] mod 4 = 0 mod 4 = 0, δηλαδή το 00
[4/4] mod 4 = 1 mod 4 = 1, δηλαδή το 01
[8/4] mod 4 = 2 mod 4 = 2, δηλαδή το 10
[5/4] mod 4 = 1 mod 4 = 1, δηλαδή το 01
[20/4] mod 4 = 5 mod 4 = 1, δηλαδή το 01
[17/4] mod 4 = 4 mod 4 = 0, δηλαδή το 00
[19/4] mod 4 = 4 mod 4 = 0, δηλαδή το 00
[56/4] mod 4 = 14 mod 4 = 2, δηλαδή το 10
[11/4] mod 4 = 2 mod 4 = 2, δηλαδή το 10
[43/4] mod 4 = 10 mod 4 = 2, δηλαδή το 10
[6/4] mod 4 = 1 mod 4 = 1, δηλαδή το 01

Η διεύθυνση όμως του μπλοκ δεν προσδιορίζει και τη θέση της λέξης, στην οποία γίνεται αναφορά, μέσα στο μπλοκ.
Ένας πλήρης τρόπος υπολογισμού προκύπτει από την τμηματοποίηση της διεύθυνσης. Υπενθυμίζεται ότι επειδή η μεγαλύτερη αναφορά σε διεύθυνση λέξης είναι το 56 για την αναπαράσταση των διευθύνσεων απαιτούνται 6 bit. Επειδή η κρυφή μνήμη είναι τεσσάρων λέξεων, σε κάθε μπλοκ μπορούν να μπουν έως 4 διαφορετικά δεδομένα. Συνεπώς τα 2 δεξιότερα ψηφία της διεύθυνσης ορίζουν σε ποια από τις 4 θέσεις των λέξεων αναφέρεται η διεύθυνση (πεδίο μετατόπισης). Επειδή δεν γίνεται αναφορά σε bytes δεν υπολογίζεται πεδίο για byte offset. Τα επόμενα 2 ψηφία προς τα αριστερά δηλαδή το 4ο, 3ο από δεξιά αποτελούν το πεδίο δείκτη κάθε διεύθυνσης. Για παράδειγμα, η διεύθυνση 1010112 αναφέρεται στη θέση 4 (11) του δεύτερου μπλοκ (ή 102) της κρυφής μνήμης. Τα 2 αριστερότερα ψηφία της διεύθυνσης 10 αποτελούν το πεδίο ετικέτας.

Σύμφωνα με τη λίστα των διευθύνσεων, αρχικά γίνεται αναφορά στην διεύθυνση 1 (ή 0000012). Κατά την λειτουργία εντοπισμού αυτής της διεύθυνσης στην κρυφή μνήμη υπολογίζεται ότι θα πρέπει να ερευνηθεί το πρώτο μπλοκ (το 002). Στη διαδικασία αυτή ο εντοπισμός σημειώνει αποτυχία γιατί το πεδίο εγκυρότητας του πρώτου μπλοκ είναι 0. Η λέξη με διεύθυνση 1 θα τοποθετηθεί στο πρώτο μπλοκ (το 002) και στη θέση 01 της κρυφής μνήμης. Επειδή το μπλοκ είναι τεσσάρων λέξεων μαζί με αυτήν θα τοποθετηθούν και οι γειτονικές λέξεις με διευθύνσεις 0,2,3. Το πεδίο ετικέτας παίρνει την τιμή 00 και το ψηφίο εγκυρότητας γίνεται 1 (τίθεται).
Ακολουθεί η αναφορά στην διεύθυνση 4 (ή 0001002). Σύμφωνα με την παραπάνω περιγραφόμενη διαδικασία εντοπισμού σημειώνεται αποτυχία και ακολουθεί η τοποθέτηση της λέξης αυτή στο δεύτερο μπλοκ (το 012) στη θέση 00. Στο πεδίο ετικέτας τίθεται η τιμή 00 κα στο πεδίο εγκυρότητας το 1. Μαζί με αυτή τοποθετούνται και οι γειτονικές λέξεις της κύριας μνήμης με διευθύνσεις 5,6,7.
Ακολουθεί η αναφορά στην διεύθυνση 8 (ή 0010002). Σύμφωνα με την παραπάνω περιγραφόμενη διαδικασία υπάρχει αποτυχία και ακολουθεί η τοποθέτηση της λέξης στο τρίτο μπλοκ (το 102) στη θέση 00. Το πεδίο ετικέτας τίθεται 00 και το ψηφίο εγκυρότητας 1. Μαζί με τη λέξη αυτή τοποθετούνται και οι γειτονικές λέξεις της κύρας μνήμης με διευθύνσεις 9,10,11.
Κατά την αναφορά στην διεύθυνση 5 (ή 0001012) η λειτουργία εντοπισμού προκαλεί επιτυχία γιατί εντοπίζεται η ετικέτα 00 και το ψηφίο εγκυρότητας του δεύτερου (01) μπλοκ είναι 1. Συνεπώς τα περιεχόμενα της κρυφής μνήμης δεν μεταβάλλονται.
Η κατάσταση, λοιπόν, της κρυφής μνήμης, μετά την αναφορά στις τρεις αυτές διευθύνσεις είναι η εξής (πίνακας 1):

Δείκτης V ετικέτα Δεδ. 1 Δεδ. 2 Δεδ. 3 Δεδ. 4
00 1 00 Mem(0) Mem(1) Mem(2) Mem(3)
01 1 00 Mem(4) Mem(5) Mem(6) Mem(7)
10 1 00 Mem(8) Mem(9) Mem(10) Mem(11)
11 0 00        

Πίνακας 1

Ακολουθεί αναφορά στην διεύθυνση 20 (ή 0101002) και ο εντοπισμός σημειώνει αποτυχία επειδή στο δεύτερο μπλοκ δεν εντοπίζεται το πεδίο ετικέτας 01. Η λέξη θα πρέπει να τοποθετηθεί στο δεύτερο μπλοκ (το 01) στην πρώτη θέση (00) (μαζί με τις γειτονικές λέξεις με διευθύνσεις 21,22,23) και αυτό προκαλεί την αντικατάσταση του ήδη υπάρχοντος. Ταυτόχρονα ενημερώνεται το πεδίο ετικέτας με τη τιμή 01. Το ψηφίο εγκυρότητας παραμένει 1.
Ακολουθεί αναφορά στην διεύθυνση 17 (ή 0100012) και ο εντοπισμός σημειώνει αποτυχία επειδή στο δεύτερο μπλοκ δεν εντοπίζεται το πεδίο ετικέτας 01. Η λέξη θα πρέπει να τοποθετηθεί μαζί με τις γειτονικές λέξεις της κύριας μνήμης με διευθύνσεις 16,18,19 στο πρώτο μπλοκ (01) και αυτό προκαλεί την αντικατάσταση του ήδη υπάρχοντος. Ταυτόχρονα ενημερώνεται το πεδίο ετικέτας με την τιμή 01. Το ψηφίο εγκυρότητας παραμένει 1.
Κατά την αναφορά στην διεύθυνση 19 (ή 0100112) η λειτουργία εντοπισμού σημειώνει επιτυχία γιατί στο πρώτο μπλοκ (00) εντοπίζεται η ετικέτα 01 και το ψηφίο επικύρωσης είναι 1. Συνεπώς τα περιεχόμενα της κρυφής μνήμης δεν μεταβάλλονται.

Η κατάσταση, λοιπόν, της κρυφής μνήμης, μετά τις αναφορές 20, 17, 19 εμφανίζεται στον πίνακα 2:

Δείκτης V ετικέτα Δεδ. 1 Δεδ. 2 Δεδ. 3 Δεδ. 4
00 1 01 Mem(16) Mem(17) Mem(18) Mem(19)
01 1 01 Mem(20) Mem(21) Mem(22) Mem(23)
10 1 00 Mem(8) Mem(9) Mem(10) Mem(11)
11 0 00        

Πίνακας 2

Ακολουθεί αναφορά στην διεύθυνση 56 (ή 1110002) και ο εντοπισμός σημειώνει αποτυχία επειδή στο τρίτο μπλοκ δεν εντοπίζεται το πεδίο ετικέτας 11. Η λέξη θα πρέπει να τοποθετηθεί στο τρίτο μπλοκ (10) στη θέση 00 (μαζί με τις λέξεις με διευθύνσεις 57,58,59) και αυτό προκαλεί την αντικατάσταση του ήδη υπάρχοντος. Ταυτόχρονα ενημερώνεται το πεδίο ετικέτας με την τιμή 11. Το ψηφίο εγκυρότητας παραμένει 1.
Η κατάσταση της κρυφής μνήμης μετά την αναφορά στη διεύθυνση 56 εμφανίζεται στον πίνακα 3:

Δείκτης V ετικέτα Δεδ. 1 Δεδ. 2 Δεδ. 3 Δεδ. 4
00 1 01 Mem(16) Mem(17) Mem(18) Mem(19)
01 1 01 Mem(20) Mem(21) Mem(22) Mem(23)
10 1 11 Mem(56) Mem(57) Mem(58) Mem(59)
11 0 00        

Πίνακας 3

Κατά την αναφορά στη διεύθυνση 9 (ή 0010012) η διαδικασία εντοπισμού σημειώνει αποτυχία γιατί δεν εντοπίζει το σωστό πεδίο ετικέτας . Η λέξη θα πρέπει να τοποθετηθεί (μαζί με τις λέξεις με διευθύνσεις 8,10,11) στο τρίτο μπλοκ (10) και αυτό προκαλεί την αντικατάσταση του ήδη υπάρχοντος (λειτουργία αντικατάστασης). Ταυτόχρονα ενημερώνεται το πεδίο ετικέτας με την τιμή 00. Το ψηφίο εγκυρότητας παραμένει 1.
Ακολουθεί αναφορά στη διεύθυνση 11 (ή 0010112) και ο εντοπισμός σημειώνει επιτυχία αφού εντοπίζει στο τρίτο μπλοκ την ετικέτα 00 και το πεδίο επικύρωσης του μπλοκ είναι 1.
Κατά την αναφορά στην διεύθυνση 4 (ή 0001002) η διαδικασία εντοπισμού σημειώνει αποτυχία γιατί στο δεύτερο μπλοκ δεν εντοπίζει το σωστό πεδίο ετικέτας 00. Ακολουθεί η διαδικασία της τοποθέτησης κατά την οποία τοποθετείται η λέξη με διεύθυνση 4 στο μπλοκ δύο (01) θέση 00. Μαζί με αυτή τοποθετούνται και οι λέξεις με διευθύνσεις 5,6,7 και ταυτόχρονα ενημερώνεται το πεδίο ετικέτας με την τιμή 00. Το ψηφίο εγκυρότητας παραμένει 1. Η τοποθέτηση προκαλεί την αντικατάσταση του ήδη υπάρχοντος.
Η κατάσταση της κρυφής μνήμης, μετά τις αναφορές στις διευθύνσεις 9, 11 και 4 εμφανίζεται στον πίνακα 4:

Δείκτης V ετικέτα Δεδ. 1 Δεδ. 2 Δεδ. 3 Δεδ. 4
00 1 01 Mem(16) Mem(17) Mem(18) Mem(19)
01 1 00 Mem(4) Mem(5) Mem(6) Mem(7)
10 1 00 Mem(8) Mem(9) Mem(10) Mem(11)
11 0 00        

Πίνακας 4

Κατά την αναφορά στη διεύθυνση 43 (ή 1010112) η διαδικασία εντοπισμού σημειώνει αποτυχία γιατί δεν εντοπίζει το σωστό πεδίο ετικέτας 10. Η λέξη θα πρέπει να τοποθετηθεί (μαζί με τις λέξεις με διευθύνσεις 40,41,42) στο τρίτο μπλοκ (10) στη θέση 4 (11) και αυτό προκαλεί την αντικατάσταση του ήδη υπάρχοντος. Ταυτόχρονα ενημερώνεται το πεδίο ετικέτας με την τιμή 10. Το ψηφίο εγκυρότητας παραμένει 1.
Ακολουθεί αναφορά στη διεύθυνση 5 (ή 0001012) με επιτυχία αφού η λέξη εντοπίζεται στο δεύτερο μπλοκ (01) του οποίου το πεδίο ετικέτας είναι 00 και το ψηφίο εγκυρότητας είναι 1. Όμοια η αναφορά στη διεύθυνση 6 (ή 0001102) είναι επιτυχής.
Η κατάσταση της κρυφής μνήμης μετά τις αναφορές στις διευθύνσεις 43, 5, 6 εμφανίζεται στον πίνακα 5:

Δείκτης V ετικέτα Δεδ. 1 Δεδ. 2 Δεδ. 3 Δεδ. 4
00 1 01 Mem(16) Mem(17) Mem(18) Mem(19)
01 1 00 Mem(4) Mem(5) Mem(6) Mem(7)
10 1 10 Mem(40) Mem(41) Mem(42) Mem(43)
11 0 00        

Πίνακας 5

Ακολουθεί ξανά αναφορά στη λέξη με διεύθυνση 9 (ή 0010012) και η λειτουργία εντοπισμού σημειώνει αποτυχία γιατί στο τρίτο μπλοκ δεν εντοπίζεται η ετικέτα 00. Η λέξη θα πρέπει να τοποθετηθεί στο τρίτο μπλοκ (10) στη θέση 2 (01) (μαζί με τις λέξεις με διευθύνσεις 8,10,11) και αυτό προκαλεί την αντικατάσταση του ήδη υπάρχοντος. Ταυτόχρονα ενημερώνεται το πεδίο ετικέτας με την τιμή 00. Το ψηφίο εγκυρότητας παραμένει 1.
Η τελευταία αναφορά γίνεται στη λέξη με διεύθυνση 17. H λειτουργία εντοπισμού σημειώνει επιτυχία γιατί στο πρώτο μπλοκ εντοπίζεται η ετικέτα 01 και το ψηφίο εγκυρότητας είναι 1. Τα περιεχόμενα της κρυφής μνήμης δεν μεταβάλλονται. Συνεπώς τελική κατάσταση της κρυφής μνήμης είναι αυτή που παρουσιάζει ο πίνακας 6:

Δείκτης V ετικέτα Δεδ. 1 Δεδ. 2 Δεδ. 3 Δεδ. 4
00 1 01 Mem(16) Mem(17) Mem(18) Mem(19)
01 1 00 Mem(4) Mem(5) Mem(6) Mem(7)
10 1 00 Mem(8) Mem(9) Mem(10) Mem(11)
11            

Πίνακας 6 - Τελική κατάσταση της κρυφής μνήμης.

Το ακόλουθο σχήμα υλοποιεί την πορεία επίλυσης του παραδείγματος για μια κύρια μνήμη με διευθύνσεις των 32 bits και κρυφή μνήμη Άμεσης αντιστοίχησης με 212 μπλοκ και μέγεθος μπλοκ 4 λέξεων (16 bytes).

  Ένδειξη τέλους Παραδείγματος στον Εντοπισμό