1,196 views
1 votes
1 votes
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?

3 Answers

Best answer
3 votes
3 votes

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 by
0 votes
0 votes

Ox80018, Ox30010 these block are different due  to Tag bit 

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
2
rahuldb asked Nov 10, 2016
721 views
, if the sequence of blocks refered by cpu is given as 1,3,5,6,7,1,5,4.
0 votes
0 votes
1 answer
4
nirupama thakur asked Mar 17, 2018
1,977 views
In some problems we multiply only with the second part of the equation with (1-H1) component and leave the first part. Whereas in other cases we multiply with cache hit a...