The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
89 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?
asked in CO & Architecture by Junior (663 points) | 89 views

2 Answers

+1 vote
Best answer

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)

 

answered by Active (3.8k points)
selected by
0
It's a Direct mapped cache.

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

Ox80018, Ox30010 these block are different due  to Tag bit 

answered by Junior (557 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,927 questions
47,580 answers
146,429 comments
62,311 users