About N-Shaped Sets of Associative Cache Stacks
Several resources I have visited on the Internet disagree on how associative caching works .
For example, hardware secrets seem to believe that it works like this:
The main RAM is then divided by the same number of blocks available in the cache memory. Saving 512KB 4-way associative example, main RAM will be divided into 2,048 blocks, the same number of blocks available inside the memory cache. Each block of memory is associated with a set of rows within the cache, just like in a direct-mapped cache.
http://www.hardwaresecrets.com/printpage/481/8
They seem to be saying that each cache block (4 cache lines) is mapped to a specific contiguous RAM block. They say that non-contiguous blocks of system memory (RAM) cannot map to the same cache block.
This is an image of how hardwaresecrets thinks it works http://www.hardwaresecrets.com/fullimage.php?image=7864
Compare this to the wikipedia image of the associative cache set http://upload.wikimedia.org/wikipedia/commons/9/93/Cache%2Cassociative-fill-both.png .
Brown disagrees with hardware secrets
Consider what might happen if each cache line had two sets of fields: two valid bits, two dirty bits, two field tags, and two data fields. One set of fields can cache data for one area of main memory, and another for another area that has the same cache line.
http://www.spsu.edu/cs/faculty/bbrown/web_lectures/cache/
That is, non-contiguous blocks of system memory can map to the same cache block.
How the relationship is created between discontinuous blocks in system memory and cache blocks. I read somewhere that this relationship is based on cache steps, but I cannot find any information about the cache steps other than that they exist.
Who is right? If reel is actually used, how does the step process work and do I have the correct technical name? How do I find a step for a specific system? is it based on a paging system? Can anyone point me to a URL that explains the N-shaped set of associative cache in great detail?
also see http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Memory/set.html
source to share
When I study the cache memory architecture for my students, I start with direct cache. Once this is understood, you can think of N-way set associative caches as parallel direct cache chunks. To understand that both numbers might be correct, you need to first understand the purpose of the set-assoc caches.
They are intended to address the "flattening" problem in direct cache mapping, where multiple memory locations can be mapped to a specific cache entry. This is shown in the figure on Wikipedia. So, instead of pushing out a cache entry, we can use the N-way cache to store other "aliases" in memory locations.
Basically, the hardware secrets diagram would be correct if the replacement order was such that the first chunk of main memory was mapped to Way-1, then the second chunk to Way-2, and so on. However, it is equally possible to have the first chunk of main memory distributed over multiple paths.
Hope this explanation helps!
PS: Contiguous memory locations are only needed for a single cache line using spatial locality. As for the last part of your question, I believe you can be confusing with several different concepts.
source to share
The replacement policy decides where in the cache a copy will occur for a particular main memory input. If the replacement policy is free to select any entry in the cache to store a copy, the cache is called fully associative. On the other hand, if each entry in the main memory can only reside in one location in the cache, the cache is directly mapped. Many caches implement a tradeoff in which each entry in the main memory can go to any of N locations in the cache and are described as an associative N-shaped set
source to share