In addition to different miss rates depending on whether we're looking
globally or locally at the cache in a multi-level cache,
we have what is called an inclusion property.
The inclusion property has to do with assuming
that the block is in level one cache.
Is it that it may or may not be in the level two cache, or,
it has to be in the L2 cache?
And it is also possible to make a system in which if a block is in L1,
it cannot also be in L2.
This is often called exclusion.
This is what we usually call inclusion and this doesn't have a name.
It's neither exclusion nor inclusion.
So if we just have a normal cache hierarchy where
processor accesses go to level one cache and then the misses from that go
to a larger level two cache cash, the question is what will we get?
And the answer is, unless we explicitly try to force inclusion or
exclusion, we will get this.
Most of the stuff that is in L1 will also be found in L2, but
there is no guarantee for that.
So there could be blocks in L1 that have been replaced from L2.
Let's look at the simple example, when the L1 cache has two blocks and
is fully associative, and the larger level two cache has four blocks and
is fully associative.
And both of them use LRU policy.
Now let's suppose that the processor accesses block A.
It's going to be a miss here, and a miss here.
It's brought from memory.
Placed here and then that is fed to the L1 cache so
it places it here, so so far we have inclusion.
Let's now access block B,
it gets brought from memory here and here.
We still have inclusion. If we now access block C,
it will be here and here and we still have inclusion, but let's
suppose that when we have the blocks A and B brought in, we reaccess A.
That is going to be a level one hit.
So know the areal count is in level one of this,
but because there has been no access when A was reaccessed to level two,
because it was a level one hit, so we don't go to L2.
Here we still have that B is the most recently accessed,
A is the next most recently accessed, and let's say these two are like this.
Now let's say we access C.
What's going to happen is we have a miss in the L1 cache,
we have a miss in the L2 cache.
We bring in C and replace the least recently used block which is this.
The counters now get updated to be three, two, one, and zero.
And then C is brought into this level one cache and
replaces B, because that's the least recently used block.
And the counters become one and zero here.
So now let's say A's accessed again.
That changes the counters back to this and
there is no axis to the level two cache.
Let's say now we access block D, it's going to be fetched here.
The counters are updated to three two, and zero.
And D is also brought into the level one cache and placed here.
Of course that updates the counters this way.
Now, let's say A's accessed again.
Now, we have the counters again, one, zero.
Let's say, now, E is now accessed.
It's a miss in both caches.
We bring E in and now in the L2 cache,
it replaces the least recently used block, which is A.
However, in the L1 cache, it will replace the least recently used block,
which is D.
So at this point, we no longer have inclusion.
Because A is in the L1 cache but is no longer found in the L2 cache.
So inclusion does not necessarily hold when you have a cache hierarchy,
because things that are frequently accessed in the L1 cache,
will not be frequently may be accessed in L2, because all of the accesses to
that block are going to L1, and the L2 never sees them.
So eventually that block gets replaced from L2.
To maintain inclusion properly, we have to have a so
called inclusion bit added to L2, which is one.
If that block is also in L1 and when we replace things from
L2 we prevent blocks whose inclusion bit is one from being replaced.
That ensures that we never replace something that is is still in L1.
So we can maintain inclusion, but again, that requires an additional bit.