Cache Misses

Question

Most people have trouble with Cache Misses. You can go through this:

https://gatecse.in/cache-misses/

Comments

Sir, if in exam conflict misses are asked then shall we count all misses or only conflict misses??. A question was asked in some paper and the answer was only conflict misses, got confused with a made easy ques. there they count all misses while in question they asked conflict misses.

---

You can assume most of the ME answers are wrong in COA. Last year GATE ME people were creating a ruckus here when GO key didn't match their answer. In Pragys app we found that only about 50/3000+ got that answer correct. Popularity of ME despite being so wrong :)

---

So we have to count only conflict misses.

And also in many questions, they give insufficient information and in solution, they assume whatever they want to justify their answers.

---

Sir, thanks for taking the time to do this, appreciate it.

The last question asks, "why there are no compulsory misses?" I think it should be capacity instead of compulsory. The answer to that question says "A compulsory miss is one which can never happen in a fully associative cache".  Shouldn't it be conflict instead of compulsory?

Also I have a question-

I know a definition that says - conflict misses are those misses that would not have occurred if the cache were fully associative with LRU policy.

Why is it necessary that, for no conflict misses, the fully associative cache use LRU replacement policy? Does it mean that a fully associative cache with FIFO replacement policy can have conflict misses?

---

Thanks for that. Corrected now.

For the conflict miss definition -- for the sake of definition they have to chose one replacement policy and LRU was chosen. Even if it is some other policy, we can get conflict miss. But if no policy is mentioned we have to use LRU as per definition.

---

Thank you very much for clearing that up!

(I'm assuming you intended to say "Even if it is some other policy, we cannot get conflict miss"?)

 

---

No. I mean we can get. i.e., in a question they may override the conflict miss definition. Even if they specify a replacement mechanism you have to use that to count the conflict misses.

---

Sir, I don't get it. Even if they modify the definition and say that the replacement algorithm was FIFO (or anything else), wouldn't a miss still be a capacity miss (as there won't be any conflicts for any block?) - how does the changing of the replacement policy from LRU to some other policy allow conflict misses in fully associative cache?

---

@Arjun Can you please clarify more on when there will be a capacity miss, the last paragraph says that "We have 256 cache blocks and in the access sequence we accessed only 6 unique memory blocks. A capacity miss is one which is caused due to the shortage in cache size. This is the miss which will happen even if we assume the cache to be fully associative." So we will have a capacity miss when the number of distinct blocks accessed is greater than the number of blocks in the cache memory?

Can you explain more on the last sentence "This is the miss which will happen even if we assume the cache to be fully associative"? What I understand from this is that if the taken example would have been fully associative cache in that case also we will have a capacity miss when the number of distinct block excess > 256. Am I right?

And If the cache in the example would have been fully associative then we would have had 6 compulsory misses and 2 hits in place of conflict miss, Am I correct?

---

@Arjun sir

can you please check this if my understanding right,

Let Direct Mapped cache #blocks = 4

Mem block address generated by CPU

0 , 4 , 2 , 6 , 2 ,4

all maps to Cache B0

0 ==> compulsory miss

4 ==> compulsory miss

2 ==> compulsory miss

6 ==> compulsory miss

2 ==> conflict miss ( As 2 was in cache earlier but due to conflict got replaced and now referenced again result in miss hence conflict miss)

4 ==> conflict miss same 

 

​​​

---

@Arjun Sir, from the link I deduce that 

Direct Map Cache can suffer from Compulsory miss, conflict miss but not from capacity miss.

Fully Associative Cache suffers from Compulsory miss, capacity miss but not from conflict miss.

Set associative cache suffered from Compulsory and Conflict miss but not from capacity miss.

please confirm thus sir.

---

@shubhanshu

capacity miss, means due to lack of storage, then in any cache mapping mechanism, after the cache full, it should be capacity miss !

But i am doubted on

Fully Associative Cache suffers from Compulsory miss, capacity miss but not from conflict miss.

as per me, this statement is right !

But sir replied to prince07 query as, " if replacement algorithm changes then it may cause conflict miss ! "

i mean to say, if we use FIFO, after all cache blocks full, now any cache block( assume it is not compulsory miss ), then it will conflict with the first one in the FIFO list --- can we say is this miss is conflict miss ?

as per me NO.. due to if there is sufficient cache size this miss not occurred ==> it is capacity miss.

hope sir will clear this doubt :)

---

^Yes, no conflict miss in fully associative cache. Because thats the definition of it.

---

Direct and set-associative can suffer from all 3 types.

---

@Arjun Sir why direct Map Cache suffers from capacity miss? I am cleared with conflict and compulsory miss on direct Map Cache. But unable to generate a example which shows all three misses occurs in direct mapped cache. Please sir give us an example which shows all three misses.

---

For identifying capacity miss in direct mapped cache, you have to assume it as a fully associative one and see if that miss can be avoided. This can happen only if total number of unique block accesses exceed the blocks available on cache -- hard to give in a problem unless cache size is too small.