4
$\begingroup$

I have been following the "High Performance Computer Architecture" course from Georgia Tech (also on YouTube), and unless I've missed something, I cannot see where the following has been explained:

If I have a multilevel cache, L1/L2/L3/Ln:

1) what decides what level of this hierarchy a block fetched from memory initially gets put in?

2) If I evict a block from L1, does that mean it gets moved to L2 (replacing a block from L2 depending on the replacement policy), and so forth for L2 to L3, and L3 to Ln, until the block evicted from the last level cache gets written to memory?

PS And yes, I have searched for this, so don't downvote assuming I haven't :)

Update

After the answer given below, I went back to the video course and found this. It seems to suggest that data is initially fetched into the L2 cache, then "fed" to the L1 cache. This also shows how, without the inclusion bit set, L1 and L2 can become "out of sync".

3) Is this generally what happens in all caches? IE if I have a 7 layer cache, will the block be fetched into L7, then fed L7->L6, L6->L5 ... and finally L2->L1? This seems like a lot of work...

4) Except in the situation shown in the linked video (if the caches get "out of sync" then certain data will only be available in one cache even though it started out in both caches), it seems that having the same data in multiple levels of the cache all the time (i.e. when the inclusion bit is set) is a waste; we have to copy it amongst all the levels. This can't be the case though, so what am I missing?

Improve this question
$\endgroup$
5
$\begingroup$

1) Usually any accessed data are saved into L1, independent whether they were previously available in L1, L2... or memory only.

For exclusive cache, data are stored ONLY in L1, for inclusive one, in the entire hierarchy. There are also mixed strategies. Also, some CPUs have "victim cache", which is extra cache level which gets ONLY data moved out of LLC (last level cache).

2) Yes, for write-back exclusive cache.

3) You misunderstood his explanation. He said that data are fetched and placed to both caches. Inclusion, btw, isn't the "bit set", but entire cache policy. The policy is built right into the hardware.

4) Exclusive cache better use precious space, but each time you have to bring new block into L1, you have to displace some block to L2, then some one to L3... and finally some one to memory. This means a lot of work. With inclusive cache, you just drop data from L1 cache, or replace older copy in L2 with newer copy displaced from L1.

As result, exclusive strategy is more optimal when adjacent cache levels has closer sizes (f.e. <=4x) and inclusive is better when sizes are very different.

More info at en.wikipedia.org/wiki/Cache_inclusion_policy

Improve this answer
$\endgroup$
10
  • $\begingroup$ Thanks for responding. I have updated the original question after reviewing your comment and using it to search the course I linked to: could you please check my update and update your answer? Thanks! $\endgroup$ – Wad Mar 23 '19 at 20:12
  • $\begingroup$ @Wad done...... $\endgroup$ – Bulat Mar 23 '19 at 20:27
  • $\begingroup$ Thank you for taking the time to edit your answer. I don't understand 3) and 4) however, sorry. 3) So in an N level cache, what level is written to first when we have a miss? Is it N? And if so, is that same block copied to all higher levels? 4) Regarding exclusive, why do you need to displace from L1 to L2? Is this what I questioned in 2) above that you answered? Inclusion: surely this involves the most work, copying a block across all N caches?? $\endgroup$ – Wad Mar 23 '19 at 20:46
  • $\begingroup$ @Wad 3) Data are written into all cache levels simultaneously. It can be done since all hardware in the CPU can work simultaneously. Physically, it can be done earlier or later. What is really important for us is that data become available for following operations so next access to A will be done at L1 speed. (Of course, in exclusive cache data are written only into L1) $\endgroup$ – Bulat Mar 23 '19 at 21:05
  • 1
    $\begingroup$ 1) in inclusive cache, L(n-1) info should present in L(n) too, but not vice versa (exactly because L(n) is larger than L(n-1)). 2) Yes. Inclusive cache immediately writes new data to all levels, in exclusive cache new data starts at L1 and then swapped out to higher levels until it finally swapped out to memory. More info at en.wikipedia.org/wiki/Cache_inclusion_policy $\endgroup$ – Bulat Mar 24 '19 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.