Consider the following reference string given as WORD addresses: 1, 4, 8, 5, 20,

Question

Consider the following reference

string given as WORD addresses:

1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17.

1. Assume a Direct-Mapped cache with 16 one-word block frames that is initially empty. When this reference string is processed, label

each reference as a Hit or Miss, and pictorially show the state of the cache as each word address is processed. The state of the cache

at the end should be the final state after the last word is processed.

2. Using the same reference string as in Problem 1, indicate the Hits and Misses and show the state of the cache after

each address including the final contents for a Set Associative cache with a total size of 16 words, a Block frame size of

one-word and a Set size of 2 (that is, 2 block frames per set). Within a Set, assume an LRU (Least Recently Used) policy for block

replacement. Assume the cache is initially empty.

Explanation / Answer

Ans:

a)

Final State of the cache:

b)

Final State of the cache with LRU:

Reference Hit or Miss Comments 1 Miss Hence fetch words 0,1,2,3(Cache block 0). 4 Miss Hence fetch words 4,5,6,7(Cache block 1). 8 Miss Hence fetch words 8,9,10,11(Cache block 2). 5 Hit Already in cache: word 5(in cache block 1) 20 Miss Hence fetch words 20, 21, 22, 23 (cache block 1), replaces
words 4, 5, 6, 7. 17 Miss Hence fetch words 16, 17, 18, 19 (cache block 0), replaces
words 0, 1, 2, 3. 19 Hit Word 19 already exists in cache block 0 56 Miss Hence fetch words 56, 57, 58, 59 (cache block 2), replaces
words 8, 9, 10, 11. 9 Miss Hence fetch words 8, 9, 10, 11 (cache block 2), replaces
words 56, 57, 58, 59. 11 Hit Word 11 already exists in cache block 2. 4 Miss Hence fetch words 4, 5, 6, 7 (cache block 1). 43 Miss Hence fetch words 40, 41, 42, 43 (cache block 2) replaces
words 8, 9, 10, 11. 5 Hit Word 5 already exists in cache block 1. 6 Hit Word 6 already exists in cache block 1. 9 Miss Hence fetch words 8, 9, 10, 11 (block 2). 17 Hit Word 17 already exists in cache block 0.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.