166 views
Consider a direct mapped cache with 16 blocks with block size of 16 bytes. Initially the cache is empty. The following sequence of access of memory blocks:
Ox80000, Ox80008, Ox80010, Ox80018, Ox30010
is repeated 10 times. Which of the following represents number of compulsory and conflict misses?

+1 vote

16 block => $2^{4}$ = 4 bits are used for the index

block size = 16 bytes => 4 bits are used for the byte offset

Memory address size = 5*4 = 20 bits

No. of Tag bits= 20-4-4 = 12 bits

Lets understand with example-

Ox80010 => $\overset{Tag}{1000 0000 0000}$  $\overset{Index}{0001}$    $\overset{Offset}{0000}$

Now consider access sequence from the question-

Ox80000, Ox80008, Ox80010, Ox80018, Ox30010

First Pass-

​​​​​​​First Ox80000 will come and will go in index 0 with tag 800 (Compulsory Miss)

Second Ox80008 will come and will be a hit because at index 0 already 800 is present (Hit)

Third Ox80010 will come and will go in index 1 with tag 800 (Compulsory Miss)

Fourth Ox80018 will come and will be a hit. (Hit)

Fifth Ox30010 will come and will go to index 1 but at index 1 already 800 is present so 300 will replace 800 and it will be a compulsory miss because 300 is coming as first time.(Compulsory Miss)

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

Second Pass-

Ox80000 (Hit)

Ox80008 (Hit)

Ox80010, Now 800 will go to index 1 but at index 1 already 300 is present so 800 will replace 300 but 800 is not coming first time, it already came in first pass so now this will be a conflict miss (Conflict miss)

Ox80018(Hit)

Ox30010 (Conflict miss)

At the end of Second pass table will look like below. And this will now go same for further passes.

Index Tag
0 800 Compulsory Miss
1 800  300 800 300         Compulsory Miss , Compulsory Miss, Conflict Miss, Conflict Miss
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Total Misses-

Compulsory Misses- 3 (In First Pass)

Conflict Misses - 9*2 =18 (In Further 9 Passes)

selected
0
It's a Direct mapped cache.

why  Ox80008 is not accessing 8th block(7) and trying 1st block ?
+1
0

Memory address size = 5*4 = 20 bits

how u got this??

by seeing the addresses since they are of 5 bits like 80000,80008??

0

@Gate Fever, Since each address is given in hexadecimal so 4 bits for each digit that's why address size is 20 bits.

Ox80018, Ox30010 these block are different due  to Tag bit

2