I have been reading about set-associative caches. As far as I have read, in case of n-way set-associative cache each way stores, a block (let's say 16 bytes) and therefore each set will be of size 16n bytes. But what if I have to load a whole page into the cache. Since the size of a page is much larger than a block, how is that distributed over the cache? Another question is what would be the distribution in case of a shared NUCA cache design? Assume that a single tile has a private L1 cache and shared L2 cache.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
There are few things to be cleared first.
Lets assume a away set associative cache with bwide cache-lines and c number of cache lines. In this configuration, size of the cache is a X b X c. Number of bits needed to represent the number of cachelines, is called index bits. (ex: 1024 cachelines will need 10 bits). When we need to load data, the index bits of the memory address tells us in which cache line this data will be stored. Since our cache is away, there are a number of cachelines, all indexed by this index bits, this data can be stored. If there are empty lines, we will use them, otherwise we have to replace and entry and store the newly fetched data.
Now coming back to your original question,
Think of "loading the page to cache" as reading the entire page in cacheline quantities. Assuming all the cache entries are invalid, first n reads will be stored in the first entry in each block of cachelines, the second n reads will be stored in the second entry in each block.
In a 2-way set assoc cache with 4 cachelines, this is how it would look like.
cacheline 1 set0 - addr 0
cacheline 1 set1 - addr 4
cacheline 2 set0 - addr 1
cacheline 2 set1 - addr 5
cacheline 3 set0 - addr 2
cacheline 3 set1 - addr 5
cacheline 4 set0 - addr 3
cacheline 4 set1 - addr 7
$\begingroup$
$\endgroup$
But what if I have to load a whole page into the cache.
There is generally no operation to load a whole page into the cache.
In fact, there is generally no mechanism to request the loading of even a single cache line.
Instead there are CPU instructions that request memory contents (reads/writes or loads/stores) — these CPU instructions that operate in terms of bytes, 16-bit half words, 32-bit long words, 64-bit words, ...) but usually the maximum is less than a whole cache line.
(The cache line size is typically chosen such that it is larger than the largest read (or write) request a processor instruction can make; this is so that a miss will at least somewhat "read ahead". (Modulo vector instructions, which can have very large operand sizes..))
What will happen is that the program (section) that we say is accessing the whole page will actually decompose into individually executed CPU instructions (often in loops) that access individual memory locations (e.g. as bytes, longs, quads).
(Ideally, such a program section accessing memory from some page or pages will do so sequentially, which will capitalize on the a read-ahead effect to the cache. A read for a 64-bit word that misses will cause a whole line to be read in, and then a read for the next sequential 64-bit word will already be in the cache.)
The state of the cache upon completion of the program (section) will be how it is left after its last instruction. There is no guarantee that the whole page still remains in the cache, though it is possible that this happens.
The point is that the processor simply executes and handles each instruction in sequence and those cause occasional cache misses and the end state of the cache is the result of cumulative effect of the individual instructions rather than some more global "load this page into the cache".
Since the size of a page is much larger than a block, how is that distributed over the cache?
Each individual cache miss is handled separately, and may evict other cache lines, in accordance with the associativity, meaning that only lines with at the same index (in the associativity set at that index) are eligible for eviction on a miss.
The total result is a combination of the overall cache construction & hardware algorithm, and the sequence of CPU instructions executed in any given software algorithm, and is arrived at by the compounding cache misses and the resulting evictions and lines loaded. (Cache hits may also modify priorities of subsequent evictions, of course).
