L1 and Ln cache: when are they written?Why can L3 caches hold only shared blocks?Multi-level cache for which inclusion holdsMESI Protocol Invalid cache line is attempted to be stored?Back invalidation to maintain inclusion in inclusive cacheComputer Architecture, cache hit and missesWhat if block sizes are not equal among caches?Pros and Cons of Average Memory Access Time When Increasing Cache Block SizeDirect-mapping cache questionCalculate Miss rate of L2 cache given global and L1 miss ratesSet Associative Cache Exercises

Is it possible to have a strip of cold climate in the middle of a planet?

Does a 'pending' US visa application constitute a denial?

What if a revenant (monster) gains fire resistance?

Loading commands from file

Does Doodling or Improvising on the Piano Have Any Benefits?

Infinite dials to reset ever?

How should I respond when I lied about my education and the company finds out through background check?

What should you do if you miss a job interview (deliberately)?

How to indicate a cut out for a product window

When were female captains banned from Starfleet?

Multiplicative persistence

Are Captain Marvel's powers affected by Thanos' actions in Avengers: Infinity War?

Store Credit Card Information in Password Manager?

Closed-form expression for certain product

Why did the EU agree to delay the Brexit deadline?

Lowest total scrabble score

On a tidally locked planet, would time be quantized?

Aragorn's "guise" in the Orthanc Stone

How to explain what's wrong with this application of the chain rule?

Is (0,1] a closed or open set?

Find the Primitive Roots Mod 31

Does the Location of Line-Dash-Wedge Notations Matter?

Dealing with a rejection from a journal

Problem with TransformedDistribution



L1 and Ln cache: when are they written?


Why can L3 caches hold only shared blocks?Multi-level cache for which inclusion holdsMESI Protocol Invalid cache line is attempted to be stored?Back invalidation to maintain inclusion in inclusive cacheComputer Architecture, cache hit and missesWhat if block sizes are not equal among caches?Pros and Cons of Average Memory Access Time When Increasing Cache Block SizeDirect-mapping cache questionCalculate Miss rate of L2 cache given global and L1 miss ratesSet Associative Cache Exercises













1












$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?










share|cite|improve this question









New contributor




Wad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$
















    1












    $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?










    share|cite|improve this question









    New contributor




    Wad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$














      1












      1








      1





      $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?










      share|cite|improve this question









      New contributor




      Wad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      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?







      cpu-cache






      share|cite|improve this question









      New contributor




      Wad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|cite|improve this question









      New contributor




      Wad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|cite|improve this question




      share|cite|improve this question








      edited 44 mins ago







      Wad













      New contributor




      Wad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 4 hours ago









      WadWad

      1063




      1063




      New contributor




      Wad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Wad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Wad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.




















          1 Answer
          1






          active

          oldest

          votes


















          2












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






          share|cite|improve this answer











          $endgroup$












          • $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
            44 mins ago










          • $begingroup$
            @Wad done......
            $endgroup$
            – Bulat
            30 mins ago










          • $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
            10 mins ago










          Your Answer





          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "419"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );






          Wad is a new contributor. Be nice, and check out our Code of Conduct.









          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105949%2fl1-and-ln-cache-when-are-they-written%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          2












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






          share|cite|improve this answer











          $endgroup$












          • $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
            44 mins ago










          • $begingroup$
            @Wad done......
            $endgroup$
            – Bulat
            30 mins ago










          • $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
            10 mins ago















          2












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






          share|cite|improve this answer











          $endgroup$












          • $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
            44 mins ago










          • $begingroup$
            @Wad done......
            $endgroup$
            – Bulat
            30 mins ago










          • $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
            10 mins ago













          2












          2








          2





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






          share|cite|improve this answer











          $endgroup$



          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.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited 16 mins ago

























          answered 3 hours ago









          BulatBulat

          796410




          796410











          • $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
            44 mins ago










          • $begingroup$
            @Wad done......
            $endgroup$
            – Bulat
            30 mins ago










          • $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
            10 mins ago
















          • $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
            44 mins ago










          • $begingroup$
            @Wad done......
            $endgroup$
            – Bulat
            30 mins ago










          • $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
            10 mins ago















          $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
          44 mins ago




          $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
          44 mins ago












          $begingroup$
          @Wad done......
          $endgroup$
          – Bulat
          30 mins ago




          $begingroup$
          @Wad done......
          $endgroup$
          – Bulat
          30 mins ago












          $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
          10 mins ago




          $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
          10 mins ago










          Wad is a new contributor. Be nice, and check out our Code of Conduct.









          draft saved

          draft discarded


















          Wad is a new contributor. Be nice, and check out our Code of Conduct.












          Wad is a new contributor. Be nice, and check out our Code of Conduct.











          Wad is a new contributor. Be nice, and check out our Code of Conduct.














          Thanks for contributing an answer to Computer Science Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid


          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.

          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105949%2fl1-and-ln-cache-when-are-they-written%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          acmart: Multiple authors: all with same affiliation, one author an additional affiliationHow to Write Names of Multiple Authors with Shared Affiliation in ACM 2017 Template?Multiple authors with different primary affiliation, but same additional affiliationSame affiliation for all authors without extra packagesIOS-Book-Article.cls: one author with multiple affiliationacmart: Shared Author AffiliationMultiple authors with different primary affiliation, but same additional affiliationAuthor affiliation with only 1 authorAdding Multiple Authors with Different Affiliation in LaTeX ArticleLaTeX: Multiple authors stays on same lineHow to Label Multiple Authors with Same DescriptionHow to make two authors use the same affiliationTwo authors with same affiliation on finished front page

          How to write “ä” and other umlauts and accented letters in bibliography?Accents in BibTeXSorting references with special characters alphabeticallyUse ae ligature in bibliographyEastern European nameInverted circumflex in BibTexBibTex, non-ascii initials and nameptr fproblems with accent in LatexHow to add a Ø to my bibliography from Jabref?References without accentsTroubles when trying to cite St“omer-Verlet in ”title" field of a bib entryComprehensive list of accented charactersHow to type the letter “i” with two dots (diaeresis) in math mode?Problem with glossary text and accented lettersSpecial character in bibliographyAccented letters, Unicode and LaTeX accentsHow to stop natbib from modifying bibliography styleCitation of a paper with non-standard characters by BibtexWrite accented characters to file using writeHow to group the bibliography alphabetically, if some surnames start with “accented” characters?How can I automatically capitalize significant words in my bibliography?

          How to force a table into page width?How to make table spanning textwidthMaking table width fit into text widthTable with tabular, column type p grabbing available spaceMaking widths of tables equal to width of textblocklatex tabular width the same as the textwidthMake tabular span textwidth exactlySet width of table to be the whole line or a given portion of itIs the tabu package obsolete?What is the difference between tabular, tabular* and tabularx environments?How can i set the width of a table?Making table width fit into text widthTabular and grid typesettingMake table use page widthTable exceeds page widthtable width automatically to page widthHow to shrink table to page widthForce table column to be zero widthTable width exceeds the page widthTable extending beyond the page widthforce longtable to text width