in CO and Architecture retagged by
54 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
in CO and Architecture retagged by


Can anyone explain in simple terms what does inclusion between two caches means?

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.


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

edited by
Anyone please summarize this
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
upper level memory is FASTER (i.e. L1) than lower level (i.e L2)
inclusion says : lower level should be subset of upper level

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 



@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.  


i strongly think that B is the answer.

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.


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:

[email protected]:~$ sudo dmidecode -t cache -q
Cache Information
	Socket Designation: L1 Cache
	Configuration: Enabled, Not Socketed, Level 1
	Operational Mode: Write Through
	Location: Internal
	Installed Size: 32 kB
	Maximum Size: 32 kB
	Supported SRAM Types:
	Installed SRAM Type: Unknown
	Speed: Unknown
	Error Correction Type: Parity
	System Type: Data
	Associativity: 8-way Set-associative


Mine is $\mathbf{12-way}$.
This is cool stuff.


I got the same doubt after reading your comment. So I asked this in SO.

From the answer given there, write back is possible in L1. We can have dirty bit (set to 1) along with the tag in L1 to show that the line (corresponding to the same tag) from L2 is invalid and only L1 has the latest/modified copy.


$+1$ @rohith1001

Practical knowledge always brings smile to our faces :)

Mine $:)$

2 L1 Both W-B 8-Way

1 L2 W-B 8-Way

1 L3 W-B 12-way


If write-back cache isn't used then value inclusion won't hold. But inclusion can.

The only thing inclusion means is that whatever $L_i$ cache has, $L_{i+1}$ cache should have it, too. The difference in the values of operands is a logical property which can't violate inclusion (a physical property)


This is so cool. . . . . thanks

i can see it for myself

L1 32 kb 8-way set associative Write Through
L2 256 kb 8-way set associative Write Through
L3 3072 kb 12-way set associative Write Back

Windows users can see it by opening Task Manager->PerfomanceCPU

Think of it in this way , if you add to L1 then you add to L2 but if you remove from L2 then you remove from L1 . Does add/remove mean update ?? not necessarily . That can easily be achieved with write back using the modified bit . Imagine L1 has block X and L2 too has block X , now if i update X do i need to update L2 immediately ?? . Let’s say if i remove X from L1 then i can update L2 , this can be easily done without much hassle. On the other hand , If X is removed from L2 , then i have to remove X from L1 as well and then i can update it in main memory as there’s no point updating cache blocks. Point is , with write back we easily achieve our goals and it’s NOT NECESSARY.

3 Answers

51 votes
Best answer

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


@Marv could you give some reference for supporting ur reason for 1st statement?

because in many sites answer given is B.
see the reason is write back is used to optimise the performance but that doesn't mean it do not follow principle of inclusion...I guess the definition of principle of inclusion is that at some point of time the changes in cache should be propagated to lower level, not necessarily right away...I saw in some book I do not remember :(
edited by

Inclusion says that a block in a higher level of memory must be present in all lower levels.

But it doesn't say that they must have the same content at all times.

arjun sir according to inclusion block of lower level must present in all higher level of memory level but sir u r saying reverse of it..

What is correct definition of inclusion @Arjun sir?The one maahisingh  has written or the one you have given.If i go by memory hierarchy figure that yours version is correct i.e block in current level indicates its presence in lower level.

But some times i have read the one maahisingh has written?Please help here


@rahul sharma and @reena_kandari

Statement IV is only correct , which is Option A.

Why statement I is false ? 

Most architectures that have inclusive hierarchies use a "write-back" cache.

A "write-back" cache differs from the write-through cache in that it does not require modifications in the current level of cache to be eagerly propagated to the next level of cache .

Instead, write-through caches update only the current level of cache and make the data "dirty" by using Dirty blocks. 

To know more Read the 2nd answer here :

What is Dirty Block and how they work in Write Back system , read this slide slide #12 , #13

@rahul sharma

What Inclusion property says ?

To simplify evicting data blocks from a level, many memory systems maintain a property called inclusion, in which the presence of an address in a given level of the memory system guarantees that the address is present in all lower levels of the memory system

Reference :[1]


Both references strongly support statement IV .

so only option A is correct .

bikram sir can u plz explain definition of inclusion given by you  is this definition wrong that items or data that is in lower level must be in higher level of memory .is my interpretation wrong here?


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.

just think of write back cache. Are the contents of cache and main memory same all the time in write back cache ??

No right. So how can we say that data will be same.

@sushmita Please check top comments.

write through is required when there is cache coherence problem as the data must be immedeatly updated at the higher level
both write through and write back are strategy to maintain cache coherence problem cache may be write through or write back
In what cases , does write back policy becomes a neccessity?
@bikram sir, what does assosciativity means in third statement?
31 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


For 1, it can be useful when read operations are predominant.

Also, associativity cannot be small in upper levels for inclusion.

I was expecting this. But I choose to ignore that read can show dominance. Coz for Access Time we need to get what is the worst case of getting access to a cache, this imply $\max(T_{read},T_{write})$.

+ statement I is false coz, $L_1$ cache can also be a Write Back/Write Around cache than just and only be write back always. so its definitely False.

1 is anyway false. But we consider worst case for real time systems or in time constraint systems, In normal systems, average case is considered.

Average Access Time will be considered for a process(es) which is already under execution(or have executed), which will take in parameters such as fraction of time read/write performed by it. Using that avg. access time for it will be calculated.

but if we dissociate a cache from any process & taking up number of times read and write cycles executed then to calculate access time of cache we should consider equal fractions of read and write cycles. To get access time of that cache. and that time need not be prefixed with the word average.

@Arjun sir what is the final answer?
option A

IV th statement .
Associativity  here means the same thing like p-way associative in set associative?I mean how many lines a set can have or is it something diffferent?
@Arjun sir,

"Also, associativity cannot be small in upper levels for inclusion."

PLease explain this a bit
@Arjun sir please answer the above question.
@Rahul Did you get the reason?
I am not sure though but what i think is that the L1 cache cache should have more associative because it will be accessed more frequently as compared to L2.. But as we know parallel search in set associative is costly thats why we keep lower level cache L2 and so on with low associative but with more space..
In set associative, once we know the set number  we check the line within that set right ? So less the associativity, faster will be the search within the set. As L1 cache should be faster than L2 cache, it should have low associativity according to me.

What do you think?
But less associative means more conflict misses.If i have 2 way associative and on other side  i have 10 way assosiative.Both can give me same accesses time as search is done in parallel.But more associative will be more complex and costly to implement the parallel search.

 If L1 is made write through then it implies that on every write operation it will take the same time that L2 cache takes to write. so this will erase the difference between L1 and L2 and to use them at different levels will be implied as meaningless. 

please explain..why it will take same time..?

L1 is write through cache, so, whatever changes are made at this level should immediately reflect at L2 level. That is, if a write is made at L1 then immediately a write at L2 should be made. Now, when we calculate the time taken for the write operation, we must consider maximum of the two. Obviously, time to write at L2 level would be greater and would be considered in this case.

Now, this entire process becomes useless. Why did create 2 levels of cache when write operation takes same amount of time in both cases! According to me, this is the reason.

Please let me know if I missed out something!

@Arjun sir in your comment

Also, associativity cannot be small in upper levels for inclusion.

Suppose L1 cache is 2-way set associative with 4 sets and let's say L2 cache is direct mapped with 16 cache lines and assume that both caches have same block size. Then I think it will follow inclusion property even though L1(lower level) has higher associativity than L2 (upper level).

No. Because in a direct mapped one, on second unique access to the same index can cause a replacement but with 2-way set, this can happen only on 3rd unique access to an index.
edited by

Sir the above photo is the configuration in above comment. let memory be accessed in sequence 0, 1, 2 ... 8. Sir, I think it is following Inclusion, even though L1(lower level) has higher associativity than L2 (upper level).

Can you please explain how this is not showing Inclusion.

sir, what does the associativity means here?
associativity here is referring to number of lines in a set of a cache.

@Arjun Sir if read operations are dominant then there is no meaning to make L1 must be a write through cache... Because coherence happens when for the same address different data present at different locations and this will happen when any modification happens at lower level.. (Write operation not the read operation).. Correct me if I am wrong.


@kp1 Write through caches are used only when read operations are dominant. Write through means we simultaneously write to the main memory. This makes write operations in write through cache very expensive. If we use write through cache where write operations are dominant, then why to use cache? We can directly write to main memory each time without cache.

Can anyone explain @Vishal Rana's doubt. I have the same doubt.

As per my understanding, lower level cache can have higher associativity. This will only change the number of tag bits (as seen from physical address at each level), number of comparators and MUX to be used.



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: order for inclusion to,sets irrespective of L2 associativity.

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.

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.

1 comment

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.

Related questions