direct mapping and types of misses

Question

Consider a cache as follows:

• Direct mapped
• 8 words total cache data size
• 2 words block size

A sequence of eight memory read is performed in the order shown from the following  addresses:

0 , 11 , 4 , 14 , 9 , 1 , 8 , 0

Calculate

1. No. of misses
2. No of compulsory misses
3. No. of conflict misses
4. No. of capacity misses

Comments

What about the last  4  and 0 ?

Will it not be a cache hit ?

Answer 1

Total cache size is 4 blocks.

Memory accesses are as follows: 0 , 11 , 4 , 14 , 9 , 1 , 8 , 0

So, the corresponding block numbers will be: 0, 5, 2, 7, 4, 0, 4, 0 (000, 101, 010, 111, 100, 000, 100, 000)

0, 5, 2, 7 and 4 causes compulsory misses as they are first accesses to blocks.

Next 0 is a capacity miss as after the previous access to 0, we have 4 unique block accesses and we have capacity only for $4-1=3$ more. Being a capacitive miss it cannot be a conflict miss (Conflict miss is a miss which won't happen in a fully associative cache with LRU policy)

Next 4 is a conflict miss due to 0 replacing 4 but not a capacity miss.

Similarly final 0 is also a conflict miss but not capacity miss.

No. of misses = 8

No. of compulsory misses = 5

No. of conflict misses = 2

No. of capacity misses = 1

More Explanation: https://gateoverflow.in/20086/page-replacement

Comments

Hello Sir,
How the No. of compulsory misses is 5 since only 4 lines are there in the cache?

---

what would be the case to get one more capacity miss??

---

@sandeep

Compulsory miss - in other words when any block is brought into cache for the first time then tht block or memory loc. Is compulsory miss..

For eg. Blocks 0 ,5 ,2 ,7 are compulsory miss... 

But block 4 has also been brought into cache for the first time.so its also compulsory miss....

---

sir,please tell me how do you calculate the corresponding block numbers..For set associative we just use the mod result ((given no) mod (n way)) and allocate them,but here what is the method has been used..I thought here divide is used instead of mod isnt it??

---

and also cant understand how did you calculate capacity and conflict miss :/

---

@khush any sequence of accesses x - a - b - c - d - x, causes a capacity miss where a,b,c,d are distinct block addresses- these might repeat and more addresses might come also.

@Sayantan Each block has 2 words. So, simply divide by 2. Set size here is 1.

For more info:

https://gateoverflow.in/20086/page-replacement

---

to determine where to allocate next block in this ques we divide by 4 bcz no of blocks is 4?
Is this division of bits  right??
 

tag	index	offset
?	2 bit	1 bit

Can we determine no. of tag bits?

---

yes, thats correct. whatever remaining goes to tag bits- here the address has 4 bits- so 2 tag bits.

---

@arjun sir,in direct mapped cache,for finding the line number to which the block number will be mappes is given by (block number) mod (no. of lines) ,so why are you doing here

"So, the corresponding block numbers will be: 0, 5, 2, 7, 4, 0, 4, 0 (000, 101, 010, 111, 100, 000, 100, 000) "

how do you know that block number needs 3 bits to represent ,??we are not given the size of physical memory here.Are you assuming that physical memory is 4 bits in size,and hence 1 bit for offset and rest for block number??

---

@arjun sir, for getting line number,i am doing (block no )mod 4

000 will be mapped to line number 00(compulsory miss)

 101 will be mapped to line number 01(complusory)

, 010 to line number 10(compulsory)

, 111 to line number 10(so compulsory miss),

100 t0 line number 00(compulsory miss)

now request 000 should be mapped to 00 line number but 100 is already there ,hence it is a miss ,it is a conflict miss but how is it a capacity miss because still line number 11 is empty,cache is not full yet.

 

please explain

---

SOMEONE CLARIFY this doubt
1..if 0,2,5,7,4 is compulsory miss..its okay,but the that 4 also replacing 0..so it should be a conflict miss simulataneously na?

---

@Udiipto. You are right. Even the access to word number  9 must be conflict miss

---

@Arjun. Even the compulsory misses must be 4.

Compulsory misses are cold start misses

e.g when you reboot your computer and for the first time you refer all the blocks of cache, then that would be compulsory misses.

---

exactly arjun sir how have u calculated block no without knowing physical address??

---

same doubt i am also having. have u got to know the explanation?? If yes plz share?

---

@Uddipto No, conflict miss occurs when a block is accessed and

1. It is not in cache
2. It was in cache before
3. It is not a capacity miss

i.e., conflict miss would not happen on a fully associative cache.

@sushmita 2 words per block, so the least significant bit is taken as offset and rest all as block number.

---

Sir why third point- It is not a capacity miss.

In the solution of this question itself we have capacity and conflict miss both.??

---

Arjun sir's answer is correct. Check out this lecture-https://youtu.be/9WFKezNvNuQ

---

U mean to say this solution is correct na?? The numerical answer??

---

Yes.

---

.......

---

in the video they have considered capacity and conflict misses as exclusive?? Means they have explained that capacity and conflict misses cannot occur together?? what do u say?

---

@ arjun sir, is it sure that capacity miss and conflict miss can occur together?

---

@sushmita. See this:

http://stackoverflow.com/questions/33314115/whats-the-difference-between-conflict-miss-and-capacity-miss

I will try to find a reference.

---

@sushmita. No one has given concrete example. What I understood from Arjun's explanation is if the previous 'n' references(n=no of blocks in cache) doesnt  contain the next reference, its a capacity miss.

I doubt about the no of conflict misses answered above because  from Reducing Compulsory and Capacity misses by Norman P. Jouppi:

Conflict misses are misses that would not occur if the cache were fully associative with LRU replacement.

which means if you were to implement LRU algo in fully associative cache and if you dont get fault in LRU but you get fault in direct-mapped methodology, then its conflict miss.

http://stackoverflow.com/questions/33314115/whats-the-difference-between-conflict-miss-and-capacity-miss

https://books.google.co.in/books?id=PcRqdsibS9UC&pg=SA9-PA16&lpg=SA9-PA16&dq=capacity+and+conflict+miss+can+occur+together&source=bl&ots=oqixcBUIL8&sig=0cQTL2hF4QxF6FMkUpsh44rghc0&hl=en&sa=X&ved=0ahUKEwjY593TsvjQAhWGvY8KHZ-ZDuEQ6AEIRjAH

---

From the book link u mentioned the concept has become clearer. Well explained. what do u think?

---

@sushmita yes, my answer was wrong here- have corrected now. Conflict miss and capacity miss won't happen together.

---

Thanx a lot arjun sir. Now its completely sorted.

---

@arjun sir,just clear one doubt--

here it is given that total cache is 8 bytes in size and block offset is 2 bytes.

so we need 1 bit for block and (3-1)=2 bit for line number in cache.

line number	line size
2	1

so,why you wrote that cache is 4 bytes in size?or main mmeory is 4 bytes in size??

pls explain

---

I didnt even tell "bytes" rt?

---

oo yes.i am so sorry..i did nt se "blocks"

but sir,how then u coverted the addresses into blocks??

as 11 memory accesses is 1011 ,so why you took first 3 bits for block number as block number is 2 bits in size?

---

Because offset is one bit as block size is two words and remaining(4-1)=3 bits will go inside block number.

---

but cache size is 3 bits long,not 4 bits.cache data size of 8 bytes include the offset size.

---

Consider a cache as follows:

• Direct mapped
• 8 words total cache data size
• 2 words block size

So cache is 8 words in size. Since block size is 2 words so number of blocks in cache =4. so cache will have 2 bits line/block number, 1 bit offset and 1 bit tag. so cache address will be 4 bits long na..

---

@Arjun Sir, Conflict Miss occurs when that miss is not capacitive. 

But, in the link of different answer provided by you https://gateoverflow.in/20086/page-replacement

011 is having both conflict and capacity miss.

---

Yes, that was wrong- I corrected now.

---

Hello guys, this was the toughest question for me today and after watching too many videos and reading too many posts/theories I come up with this solution plz Arjun sir and all other ppl check out my solution and tell me if I am going right or not! My way of thinking and solution is right or not! Correct me,plz!

---

@smartmeet here 0 ---> 0(00)0

                           1----->0(00)1

           here according ur method why not conflict miss.......why capacity

---

I have a  doubt related to this statement of yours

Next 0 is a capacity miss as after the previous access to 0, we have 4 unique block accesses and we have capacity only for 4−1=3 more.

but there are 5 unique block accesses till the 0, not 4 as I can see   (0, 5, 2, 7, 4)

---

@arjun sir @bikram sir @ayush sir

here the 3rd access to block 0 i.e. the last block, should also be capacity miss ?

because from 1st access to zero , we have 5,2,7,4   i.e. 4 unique references so cache size< 4 , so it should be capacity miss? rt? 

Answer 2

As Per me, i solved in this way
If im wrong Please someone explain where im missing

#cache line= 8/2 = 2 lines

each line can hold 2 words

to find which line the block can be stored
x mod n is used 
where x is block number
n is number of lines

0 --- 0 mod 4 = 0  
11 --- 11 mod 4 = 3  
4 --- 4 mod 4 = 0  
14 --- 14 mod 4 = 2  
9 --- 9 mod 4 = 1  
1 --- 1 mod 4 = 1  
8 --- 8 mod 4 = 0  
0 --- 0 mod 4 = 0  

As each line can hold 2 words 0,4 are placed in 0 later 0 is replaced with 8 and 4 is replaced with 0

No.of misses =8

compulsory miss =6 (0,11,4,14,9,1)

conflict misses =2 (8,0)

capacity miss =0

Comments

Words are not replaced by words. Blocks are replaced by blocks.

Moreover, we take the mod of Block number, not word number.

Answer 3

8+4+4

 

is it correct reply