GATE CSE 2008 | Question: 35

Question

For inclusion to hold between two cache levels $L_1$ and $L_2$ in a multi-level cache hierarchy, which of the following are necessary?

1. $L_1$ must be write-through cache

2. $L_2$ must be a write-through cache

3. The associativity of $L_2$ must be greater than that of $L_1$

4. The $L_2$ cache must be at least as large as the $L_1$ cache

• A. IV only
• B. I and IV only
• C. I, II and IV only
• D. I, II, III and IV

Comments

Reference : 1)https://en.wikipedia.org/wiki/Cache_inclusion_policy. 2) https://www.csc2.ncsu.edu/faculty/efg/courses/506/s23/www/homework/tests/t2_notes.pdf

---

for fun :For check mac OS checking associativity use this command :

sysctl -a | grep -i cache

---

Only Option A is correct

 

Answer 1

1$^{\text{st}}$ is not correct as data need not to be exactly same at the same point of time and so write back policy can be used in this.

2$^{\text{nd}}$ is not needed when talking only about $L1$ and $L2$.

For 3$^{\text{rd}}$, associativity can be equal.

So, only 4$^{\text{th}}$ statement is Necessarily true - (A) choice.

Comments

@Setika Mehra Direct Mapped (1-way associative), set associative or Fully associative, simply Associativity = number of blocks per set

In the context of Statement III:

"Associativity of L2 must be greater than that of L1"

This is asking: Does L2 need more blocks per set than L1?

Answer is no.

Because IV is necessary - L2 must be at least as large as L1,
So when L2 is larger, it has more sets, so conflicts in L1 spread out across different L2 sets. L2 can have same or even fewer blocks per set and still hold everything L1 has.

---

@Gopika_G here statement 3 is wrong because of > , if it had >= then it would be true 

---

statement 3  is sufficient condition but not necessary

Answer 2

Cache levels differs only because their access times are different. If $L_1$ is made write through then it implies that on every write operation it will take the same time that $L_2$ cache takes to write. so this will erase the difference between $L_1$ and $L_2$ and to use them at different levels will be implied as meaningless. So, statement I cannot be true always.

statement II asks that $L_2$ is always write through, this is not true for every case we can have a Write Back cache in many cases. So, this is also false.

statement III talks nothing meaningful. as assoc. has nothing to do here.

statement IV : for Inclusion property to hold it is required that $L_1$ is a subset of $L_2$ cache. 

Hence, answer = option A

Comments

@Arjun

I think associativity has nothing to do with cache levels.

Lower level cache can have higher associativity from answers given here in StackOverflow.

(Actually I was not able to completely understand those answers :P)

---

In order for inclusion to hold, certain conditions need to be satisfied. L2 associativity must be greater than or equal to L1 associativity irrespective of the number of sets. The number of L2 sets must be greater than or equal to the number of L1 sets irrespective of L2 associativity. All reference information from L1 is passed to L2 so that it can update its replacement bits.

Reference: https://en.wikipedia.org/wiki/Cache_inclusion_policy#:~:text=In order for inclusion to,sets irrespective of L2 associativity.

---

OK so first we have to know what is Inclusion 

Inclusion means every cache line present in L1 must also be present in L2

Now lets dive into options,

• If L2 is not large enough to hold all lines that can be resident in L1, inclusion is impossible. So IV is a necessary condition. 

• I and II (write-through requirements) are not strictly necessary — inclusion can be maintained with write-back caches if the controller handles writebacks correctly (e.g., writeback from L1 into L2 on eviction).

• III (L2 associativity > L1 associativity) is helpful to avoid conflict-induced violations, but it's not strictly necessary — inclusion can be enforced through eviction/invalidations or other design mechanisms.

Answer 3

Inclusion in a multi level hierarchy refers to a property where all the dara Stored in a higher level (smaller, faster) cache like L1 iis present in the lower level (larger, smaller) cache line L2.Essentially if a data block exist in the L1 cache, the same data block exists in the L2 cache.This ensures that when an eviction happens in L2. the corresponding data is also evicted from L1 to maintain consistency

Option I: L1 must be write Through: This is not necessary for inclusion to hold

• Inclusion can also hold in a write back cache. 
• Write Thaough cache ensures that whenever data is written to L1 ,it is immediately written to L2 as well, but inclusion can still hold even if L1 is a write-back cache (which only writes to L2 when data is evicted from L2)

So L1 must be write through is not necessary.

Option II::L2 must be write Through

. Same reasoning  as above.

Option C:The associativity of 12 must be greater than that of Li

• .Not neccessarly True
• Generally desirable for performance issues
• Greater associativity in L2 helps avoid conflict that might evict lines prematurely improving cache performance through inclusion can hold without  this.

This option is not necessarily true

Option IV:The L2 cache must be at least as large as the L1 cache

• This is necessary for inclusion to hold
• If L2 i smaller than L1,there wouldnot be enough space in L2 to store all the data from L1,breaking inclusion property.

 

 

Answer 4

Why option 1 and 2 are correct

If the the caches are not write through, we can have a imbalance between the LRU counter in the L1 and L2 caches. leading to a situation where the inclusion property will fail eventually. Hence every HIT in L1, must propogate to L2 also, in order to maintain consistency in the LRU counter.

The video given below displays a good example of this problem, when write through cache are not used.

https://www.youtube.com/watch?v=J8DQG9Pvp3U

Why option 4 is also correct

The size of L1 and L2 caches can be equal, or L2 can be greater. 

case 1 (If they are equal or L2 is greater): This part is quiet self explanatory, in this case we are sure to have atleast as many entries in L1 as L2, also L2 can have extra lines which does not affect our inclusion property.

case 2 (If L1 is greater than L2): Lets say L1=10 lines and L2=2 lines, if block 0, 1 are accessed, they lead to compulsary misses and are now available in L1 as well as L2.

Now lets say we access 3, 

in L2 cache, we must have it replace atleast one out of 0, 1, and due to greater size of L1 we may not necessarily map 3 to existing position, when this occurs we will have violated our inclusion property.

Hence I believe the answer to be (c)

Hello Everyone, this is my very first post, so i'm sorry If my explanation is not explained as well as it should be.

Comments

The video which is shown is for set associative cache but in direct mapped cache we don't use any replacement algo. The block to be replaced is fixed.

So inclusion property can be followed if L1 , L2 is direct mapped cache and writeback policy is used.

Hence L1 must be a writethrough cache is not a necessary condition for inclusion.

Answer 5

OK so first we have to know what is Inclusion 

Inclusion means every cache line present in L1 must also be present in L2

Now lets dive into options,

• If L2 is not large enough to hold all lines that can be resident in L1, inclusion is impossible. So IV is a necessary condition. 

• I and II (write-through requirements) are not strictly necessary — inclusion can be maintained with write-back caches if the controller handles writebacks correctly (e.g., writeback from L1 into L2 on eviction).

• III (L2 associativity > L1 associativity) is helpful to avoid conflict-induced violations, but it's not strictly necessary — inclusion can be enforced through eviction/invalidations or other design mechanisms.

Answer 6

Ans