ISRO2007-46

Question

Consider a small $2$-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently (LRU) scheme. The number of cache misses for the following sequence of block addresses is $8, 12, 0, 12, 8$

• A. $2$
• B. $3$
• C. $4$
• D. $5$

Answer 1

We have 4 blocks and 2 blocks in a set . there are 2 sets.

 

since the lowest bit of block address is used for indexing into the set. 

So, 8, 12 and 0 first miss in cache with 0 replacing 8 and then 12 will be hit in cache and 8 again miss. So totally 4 misses. 

Comments

no. of sets are 2. so, answer should me 5 miss.

@arjun sir..plz answer....

---

8 will go in first set---1st miss

12 will go in first set--2nd miss

0 will go  in first set and replace 8 --3rd miss

12 will be in 2nd block of 1st set so no miss

8 will go in 1st block 1st set and will replace 0-- 4rth miss.

---

why 0 will go in 1st set. Why dont it go to second set.?

---

if the result of the modulus is 0 then it will go to 0th set if the result of the modulus is 1 then it will go to 1st set.

---

If k is the block address, 4 is no of blocks

k%4 == 0, map to set0

k%4 == 1, map to set1

Here, all block addresses map to set0 as address%4 = 0 for all addresses.

---

1) The lowest bit of block address is used for indexing into the set

2) block address % number of sets is used for indexing into the set

Can someone explain if these both are same or not?

Answer 2

hope it might help.......

Comments

Ans should be 3.no of sets= 4/2=2

Apply LRU u will get no of misses =3