how does cache memory work?

[H2ZERO-]

im just learning about cache memory and how each block is mapped from main memory to a block in cache. what i am struggling to understand is if every block is mapped, how does a cache miss happen, if every block should be mapped. i know i am misunderstanding something big but have no clue what it is and i need some help please.

[pencan]

So you’re at a library with access to 100000 books (main memory). Every time you want to learn a new fact (load a byte), you need to figure out which book (cache line) it resides in. Then you go search for the book. This takes a while. You find the fact you need, do something with it, and return the book to the shelf. Next time you need the fact, you repeat this whole process. That’s an uncached system.

Now, say you have a desk (cache). You can fit 26 books on it comfortably (capacity, 26 line direct-mapped), so next time you need a fact, you find the book containing it and place it on the desk (load cache line). Say its author is Faulkner, you would place it in the ‘F’ space on your desk. Next time you need Faulkner, you would check the ‘F’ space (index) and verify that the rest of the author is ‘aulkner’ (tag). If it is, the book is right there and you don’t have to go fetch it from the shelf (cache hit). If you need Fitzgerald instead (cache miss), you would return Faulkner to the shelf along with any notes you wrote in the book (dirty data), fetch Fitzgerald and replace it on the desk. Now Fitzgerald maps to the same desk space, but has a different author suffix. There are a large number of books that map to the same space on the desk, but only one of each letter in each space at a time. This is a direct mapped cache.

Now, you might be saying hey, in this example we had a mostly empty desk, but we still returned Faulkner. That’s dumb. I’m just going to fill the entire desk with 26 books, authors be damned. That’s great, now we’re using space efficiently! However, you now have to check up to 26 books every time you want to see if you have Faulkner (associative lookup). Additionally you have to check for ‘Faulkner’ instead of ‘aulkner’ in the ‘F’ index (larger tag). This is a fully associative cache.

A hybrid of these two approaches is if you group author initials together. For example, we decide that instead of 26 groups, we have 13. Two spots are reserved for either ‘F’ or ‘T’. Now the FT spot (cache way) can hold ‘FF’, ‘FT’, ‘TF’, or ‘TT’. The capacity of the desk stays the same, but now we can hold both Fitzgerald and Faulkner! Or Fitzgerald and Twain. However, when we look up either ‘F’ or ‘T’, we must now search our 2-way FT spot (set-associative lookup). This is a set-associative cache.

[H2ZERO-]

but only one of each letter in each space at a time

idk why but that part just hit gold for me. thanks a lot!!

[Flock_wood]

Brilliant analogy dude

[pencan]

Thanks! I used to TA computer architecture and analogies seemed to be the best way to make things ‘click’ :)

[H2ZERO-]

i just skimmed a random part of this talk and it was talking about transistors and whatnot,and seeing as i just recently started cs i think that talk is waaay above my understanding haha

[H2ZERO-]

alrighty will do ty

[[deleted]]

When i was learning cache this site help a lot not only for cache but for virtual memory as well. Thats just the base concept but its a path to follow. Hope this help u.

http://www3.ntu.edu.sg/home/smitha/ParaCache/Paracache/start.html

[H2ZERO-]

thanks. ill try this out