ΗΥ 255: ΛΥΣΕΙΣ 7ης ΣΕΙΡΑΣ ΑΣΚΗΣΕΩΝ


Ερώτηση (1)

 

Cache Α:

16 blocks, 1 λέξη / block

Cache Β:

4 blocks, 4 λέξεις/block

Διεύθυνση

Θέση (Set)

Hit/Miss

Θέση (Set)

Hit/Miss

5

5

Μ

1

M

2

2

Μ

0

M

6

6

Μ

1

HIT

9

9

Μ

2

M

21

5

Μ

1

M

18

2

Μ

0

M

20

4

Μ

1

HIT

57

9

Μ

2

M

10

10

Μ

2

M

12

12

Μ

3

M

5

5

Μ

1

M

44

12

Μ

3

M

7

7

Μ

1

HIT

6

6

ΗΙΤ

1

HIT

10

10

ΗΙΤ

2

HIT

18

2

ΗΙΤ

0

HIT

Περιεχόμενα των cache:

(A)

Block 2 Λέξη 18
Block 4 Λέξη 20
Block 5 Λέξη 5
Block 6 Λέξη 6
Block 7 Λέξη 7
Block 9 Λέξη 57
Block 10 Λέξη 10
Block 12 Λέξη 44

Τα υπόλοιπα blocks της cache είναι κενά (invalid)

(Β)

Block 0 Λέξεις 16-19
Block 1 Λέξεις 4-7
Block 2 Λέξεις 8-11
Block 3 Λέξεις 44-47

 


Ερώτηση (2)

Μέσος χρόνος πρόσβασης = 1 + miss_ratio * miss_penalty

Για την cache Α έχουμε: 1 + 13/16 * 8 = 1 + 6,5 = 7,5

Για την cache Β έχουμε: 1 + 10/16 * 11 = 1 + 6,87 = 7,87


Ερώτηση (3)

Πόσα bytes είναι ένα block; 4 λέξεις * 4byte/λέξη = 16 bytes/block

Πόσα blocks έχει η cache; 32Kbytes/16 bytes/block = 2K blocks

Πόσα sets έχει η cache; 2K blocks / 2 blocks/set = 1K sets

Δηλαδή το πεδίο set-index χρειάζεται να έχει 10 bits. Το πεδίο block-offset έχει 2 bits αφού έχουμε 4 λέξεις σε ένα block. Επίσης έχουμε και τα 2 bits λόγω διευθύνσεων bytes, οπότε στο πεδίο tag μένουν (32-10-2-2) = 18 bits.

Συνοπτικά:

Κάθε "direct mapped" κομμάτι της cache έχει τα εξής πεδία:

      1. Valid (1 bit)
      2. Dirty (1 bit) (λόγω απαίτησης write-back)
      3. Tag (18 bits)
      4. Data (128 bits δηλαδή 4 λέξεις)

Δηλαδή η κάθε καταχώρηση αποτελείται από 148 bits, και έχουμε 1Κ τέτοιες καταχωρήσεις, οπότε το κάθε "direct-mapped" κομμάτι της cache απαιτεί 148Kbits αποθηκευτικού χώρου. Αφού η cache είναι 2-way associative, έχω δύο τέτοια κομμάτια δηλαδή απαιτούνται 296Kbits = 37KBytes αποθηκευτικού χώρου. Εάν ο αλγόριθμος αντικατάστασης είναι LRU χρειαζόμαστε ένα bit ανά set για την υλοποίηση του, οπότε έχουμε συνολικά 306Kbits = 378.25 Kbytes αποθηκευτικού χώρου.

Για την σχεδίαση συνδιάστε το σχήμα 7.10 με το μισό σχήμα 7.19 (επειδή αναφέρεται σε 4-way associative cache).