Test Series

Question

Consider a 4-way set associative cache that has 8-lines, with perfect LRU cache replacement and supports a block size of 16-bytes. For the following memory access pattern (shown as byte addresses), find the hit ratio?
3, 5, 6, 21, 32, 14, 5, 10, 11, 12

Answer 1

**Edit :

Cache block size is 16 byte i.e. in one access cache is fetching 15 more addresses next to that request.

1st request is 3. Miss !  cache will fecth from 0 to 15 in one access.

now addresses 5,6 are hit.

request 21 is again miss. So it will fetch from 16 to 31.

again miss for 32.

Next all requests will be in cache so all are hit.

 

Hit ratio = 7/10 =0.70

Comments

3(Miss), 5, 6, 21(Miss),32(Miss),14,5,10,11,12

hit ratio= 7/10

is it correct now?

---

^yes..

---

Thanks. This is exactly what I got, but the solution indicated that the second access to 5 is the only hit. I just wanted to confirm I am not missing something.

Answer 2

Each address is divided as: [TAG bits] [SET bits] [BLOCK OFFSET bits]

Here, BLOCK OFFSET = 16 bytes => 4 bits

SET = 8 lines / 4 = 2 sets => 1 bit

Remaining => TAG bits

Replacement happens in the SET :

So, address having 5th bit from right which is SET bit as 0 goes to 1st SET, otherwise 2nd SET.

Eg: 3 = 000011 => SET0  and 21 = 010101 => SET1

 

SET0

3 => 14 => 12

5 (hit)

6 => 10

32 => 11

 

SET1

21

 

HIT ratio = 1/10 = 0.1