Θεωρητικη ερωτηση Αρχ. Υπολογιστων

[kraken]

Μπορει κανεις να μου απαντησει σε αυτην την ερωτηση;

Εστω οτι εχετε ενα υπολογιστικο συστημα με κρυφη μνημη οπου: εχετε

100 blocks κυριας μνημης και

8 θεσεις στην κρυφη μνημη για προσωρινη αποθηκευση των blocks τα οποια κρατα

Θεωρηστε οτι ερχονται αιτησεις για προσβαση στα παρακατω blocks της κύριας μνημης και με τη σειρα που σας διδεται: 18, 18, 23, 18, 14, 26, 24, 26, 18, 56, 88, 98, 66, 15, 34

a. Σε περιπτωση που ειχατε οργανωση της cache με τεχνικη αμεσης απεικονισης (direct mapping) τοτε ποτε θα δημιουργηθει η αναγκη για αντικατασταση των περιεχομενων της cache για πρωτη φορα;

b. Ποιο ειναι το cache hit ratio; (λογος επιτυχιας)

[Tsoureki]

a. Όταν κληθεί το block 66

b. 4/15

EDITED: Δες παρακάτω

[kraken]

Πρωτον, ευχαριστω!Δευτερον μπορεις να μου πεις πως το βρισκεις το δευτερο;

[kazabubu]

a. Όταν κληθεί το block 66

b. 4/15

Οταν κληθει το block 26 δε θα αντικατασταθει το block 18? Εμένα μου βγαίνει 3/15 αλλά μπορεί και να μη τα θυμάμαι καλά..

[Tsoureki]

Αναφέρει 8 θέσεις στην cache.

[kazabubu]

Ναι και αναφέρει και τεχνική direct mapping οπότε αν το καταλαβαίνω καλά το 18 και το 26 θα πάνε και τα δυο στη θέση 1 (αν οι θέσεις της cache αριθμηθούν 0,1,2,3,4,5,6,7) και η αρίθμηση των 100 blocks ξεκινά από το 1.(ή στη θέση 2 αν η αρίθμηση των 100 ξεκινάει από το 0)

[Tsoureki]

Ναι σωστό! Πρώτη αντικατάστασn είναι με το 26!

[kraken]

Υπαρχει καπου καποιο tutorial στο internet;Δεν εχω βρει τιποτα ουτε στα Αγγλικα.

[Tsoureki]

Υπάρχουν αρκετά tutorials στο internet μαζί με παραδείγματα. Η λογική είναι η εξής:

-Βλέπεις πόσες θέσεις cache έχεις και ανάλογα με το πλήθος τους τις χωρίζεις σε όσο το δυνατόν περισσότερα Least Significant Bits. Επειδή εδώ έχεις μόνο 8, θα την χωρίσεις με βάση τα τελευταία 3 LSBs. (000,001,010,011,100,101,110,111)

-Κατανέμεις μετά τα blocks στην cache ανάλογα με τα 3 LBSs τους. Για αυτό και το 26 αντικαθιστά το 18. Ανήκουν στα 010 - όπως και τα 98 και 66.

Αν είχες 16 θέσεις cache δηλαδή 2^4, θα μπορούσες να τους διαχωρίσεις με βάση τα 4 LSBs.

[kazabubu]

Συγκεκριμένα για το direct mapping που είναι απλή περίπτωση, το να κρατήσεις τα 3 LSB που λέει και ο τσουρέκι είναι σαν να κάνεις ακέραια διαίρεση με το 8 (2^3) και να κρατάς το υπόλοιπο της διαίρεσης.

Οπότε 18 modulo 8 = 2 (010)

26 modulo 8 = 2 (010)

Άρα πάνε στην ίδια θέση.

[kraken]

Ευχαριστω, το πρωτο ερωτημα κατανοητο!To hit ratio πως βγαινει ομως;

[nucleus]

Hit ratio βγαίνει αν διαιρέσεις τα hits (δηλαδή πόσες φορές βρήκε το item που ζητήθηκε στην cache,χωρίς να χρειαστεί να το φέρει από την κύρια μνήμη) με το σύνολο των αιτήσεων που έγινε στην cache.

H σειρά σου είναι 18, 18, 23, 18, 14, 26, 24, 26, 18, 56, 88, 98, 66, 15, 34

Συνολικά δηλαδή 15 requests όσα και τα blocks.

Πρώτο request 18.Δεν υπάρχει στην cache οπότε μετράει σαν miss (πρέπει να το φέρει από την κύρια μνήμη και να το γράψει σε μια θέση στην cache)

Δεύτερο request:18.Υπάρχει στην cache άρα είναι hit.

Τρίτο request: 23 Δεν υπάρχει στην cache.

Τέταρτο request:18 Υπάρχει στην cache άρα είναι hit.

Κάνεις το παραπάνω για όλα τα requests λαμβάνοντας υπόψη και το πρώτο ερώτημα.Μόλις βρεις όλα τα hits διαιρείς με το 15.

[kraken]

Τεραστιος!Ευχαριστω πολυ.