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.

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                                 

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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