retagged by
24,271 views
61 votes
61 votes

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

  1. IV only
  2. I and IV only
  3. I, II and IV only
  4. I, II, III and IV
retagged by

3 Answers

Best answer
57 votes
57 votes

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.

edited by
37 votes
37 votes

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

edited by
2 votes
2 votes

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.

Answer:

Related questions