Consider the following reference String given as WORD addresses: 1, 4, 8, 5, 20,
ID: 3691792 • Letter: C
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.
Using the same reference string above, 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 a FIFO (First In First Out) policy for block
replacement. Assume the cache is initially empty.
Explanation / Answer
Answer for Question:
This below table will solve the given probelm statement with neat comments and step by step
Step 1:
Reference Hit or miss Comments
1 Miss Hence fetch word 1 to set 1.
4 Miss Hence fetch word 4 to set 4.
8 Miss Hence fetch word 8 to set 0.
5 Miss Hence fetch word 5 to set 5.
20 Miss Hence fetch word 20 to set 4 (no need to replace word 4).
17 Miss Hence fetch word 17 to set 1 (no need to replace word 1).
19 Miss Hence fetch word 19 to set 3.
56 Miss Hence fetch word 56 to set 0, (no need to replace word 8).
9 Miss Hence fetch word 9 to set 1 (set 1 already contains two words, 1
& 17, hence word 1 is replaced by word 19 due to LRU).
11 Miss Hence fetch word 11 to set 3 (no need to replace word 19).
4 Hit Word 4 already exists in set 4.
43 Miss Hence fetch word 43 to set 3 (set 3 already contains two words,
11 & 19, hence word 19 is replaced by word 43 due to LRU).
5 Hit Word 5 already exists in set 5.
6 Miss Hence fetch word 6 to set 6.
9 Hit Word 9 already exists in set 1.
17 Hit Word 17 already exists in set 1.
Step 2:
Hence the final state of the cache with LRU order shown right to left:
Set # Block Block
0 56 8
1 17 9
2
3 43 11
4 4 20
5 5
6 6
7