# GATE2008-35

9.8k views

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
6
Can anyone explain in simple terms what does inclusion between two caches means?
34

Inclusion between 2 cache means : All information items are originally stored in level Mn , during the processing subsets of Mn are copied into Mn-1 , similarly subsets of Mn-1 are copied into Mn-2 and so on..

This makes statement IV correct.

Write back policy mostly used in different levels of cache due to Dirty Bit policy used by write back .That makes statement I wrong.

Reference:

Read This PPT about Inclusive and exclusive Cache Hierarchy , where in case of Inclusive cache Last level is superset of previous level .

2
1
4
I was solving this question in GEEKSFORGEEKS the solution that was given there was different , soltion:

Answer is (B), i.e., (i) and (iv) are true. Because inclusion says the L2 cache should be Superset of L1 cache. If "Write Through update" is not used (and "Write Back update" is used ) at L1 cache, then the modified data in L1 cache will not be present in L2 cache for some time unless the block in L1 cache is replaced by some other block. Hence "Write Through Update " should be used. Associativity doesn't matter. L2 cache must be at least as large as L1 cache, since all the words in L1 are also is L2

Now i am confuse which one is right geeksforgeeks or GO both seems to be correct
0
upper level memory is FASTER (i.e. L1) than lower level (i.e L2)
inclusion says : lower level should be subset of upper level
3

This one ...

0

From wiki

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

Value Inclusion: It is not necessary for a block to have same data values when it is cached in both higher and lower level caches even though inclusion is maintained. But, if the data values are the same, value inclusion is maintained.[1] This depends on the write policy in use, as write back policy does not notify the lower level cache of the changes made to the block in higher level cache. However, in case of write-through cache there is no such

8

@Moin Mukhtar Write through / Write back policies are between cache and main memory and not between two caches. If you have to update other caches simultaneously Write update policy is used and to invalidate data in other caches write invalidate is used.

0

i strongly think that B is the answer. https://en.wikipedia.org/wiki/Cache_inclusion_policy

as per the argument given in the best answer for option A, that argument is wrong. because, yes it is necessary that at any particular instant of time, lower level cache is proper subset of the higher level cache.. that is why whenever a block is replaced from the higher level cache, corresponding block is also invalidated from the lower level cache. and hence other way round, whenever a block is written in the lower level cache, it has to be written immediately in the higher level cache, which can be carried out only by using write through policy.

10

Some fun exercise :P

Type the below command in your linux terminal.

sudo dmidecode -t cache -q

You will be able to see the cache arrangement of your system. (I could see that I have two L1 cache, one L2 cache and one L3 cache in my system)

The output will be something like this: