Finding Hit Ratio when memory references are given in Hex

Question

A byte addressable computer has a small data cache capable of holding eight 32 bit words. Each cache block consist of two 32 bit words. For the following sequence of addresses (in hexa decimal ). Find the hit ratio if two way set associative LRU cache is used.

                200, 204, 208, 20C, 2F4, 2F0, 2F4, 2F0, 21C, 218, 24C

Also find the number of...  i) Misses   ii) Compulsory Misses    iii) Conflict   iv) Capacity Misses.

--------------------------------------------------------------------------------------------------------------------------------

What bothers me is the answer given in Madeeasy Test Series. Here is my try.

A block consists of two 4B words. So, a block consists of 8B and as memory is byte addressable, 3 bits are used for offset. As well as 4 blocks are possible with above scenario and 2 sets, as a result, 1 bit is used for set.

------                  | Set | Offset

200 = 0010 0000 | 0 | 000   => Compulsory Miss

204 = 0010 0000 | 0 | 100   => Hit

208 = 0010 0000 | 1 | 000   => Compulsory Miss

20C = 0010 0000 | 1 | 100  => Hit

2F4 = 0010 1111 | 0 | 100  => Compulsory Miss

2F0 = 0010 1111 | 0 | 000  => Hit

2F4 = 0010 1111 | 0 | 100  => Hit

2F0 = 0010 1111 | 0 | 000  => Hit

21C = 0010 0001 | 1 | 100  => Compulsory Miss

218 = 0010 0001 | 1 | 000  => Hit

24C = 0010 0100 | 1 | 100  => Compulsory Miss

(Other capacity and conflict misses are 0)

So, the hit ratio should be 6/11 = 0.54.

But, the answer given was 0.2

Where am I going wrong???

[P.S. - There is same qstn asked by someone previously, but I guess, that explaination is conflicting. You can check it here - https://gateoverflow.in/29182/cache-miss-in-two-way-set-associative ]

Comments

@Arjun sir this solution seems correct and i am also getting the same. Why is Bikram saying that after 200, 204 will be a miss?? Its creating confusions. please check this too  https://gateoverflow.in/140679/cache-misses-lru

---

@sushmita I am also getting the same doubt,

since 204 is already in memory why isn't it a hit?

---

it is hit only. I checked it 100 times but couldn't get how 204 is a miss.

Answer 1

the ans is precisely 0.18..your aproach is right but in your xplanation you have done one mistake,the bit u choosed for set determines in which set the address will go,that is either 0 or 1.that's it,but instead of determinning only that,u also considered hit,miss by the set bit,there is only 2 hit .

2F4 = 0010 1111 | 0 | 100  => Hit

2F0 = 0010 1111 | 0 | 000  => Hit

these 2,

set bit only determines in which set the address will go,

hit,miss will be decided by total address..

these 2 are hit cause set no 1 is already contain 2F4 and 2F0...

i think now you will understand your mstk..

other than u r aproach is very good,and this approach will help you determine capacity and conflict misses.  

Comments

yes, the answer is 2/11 = 0.18 ~ 0.2

there only 2 hits :

2F4 = 0010 1111 | 0 | 100  => Hit

2F0 = 0010 1111 | 0 | 000  => Hit

and rest all are compulsory misses .

hit,miss will be decided by total address( like 2F4 etc).

---

@Bikram Sir, I am not able to understand why you are considering 204 a miss. Doesn't 200 will bring all the words from 200 to 207?

---

yes 204 is a hit. It is not a miss