Cache

Set Associative Cache

Associative caches are designed to reduce the rate of conflict misses. See this video: https://www.youtube.com/watch?v=quZe1ehz-EQ&ab_channel=MatthewWatkins

Set associative cache is the middle range of designs between direct mapped and fully associative cache.

• In a set-associative cache, there are a fixed number of locations where each block can be placed.
• $n$-way set-associative cache = $n$ locations for a block
  • lol unrelated but this is like the philosophy of naming K-Way N-Shot Learning
• An $n$-way set-associative cache = each sets consists of $n$ blocks
  • Each block in the memory maps to a unique set in the cache given by the index field, and a block can be placed in any element of that set. Thus, a set-associative placement combines direct-mapped placement and fully associative placement: a block is directly mapped into a set, and then all the blocks in the set are searched for a match. For example, $\text{Cache address mapped}=\text{(Block address)}\mathrm{mod}(\#\text{ sets }\text{in cache})$

Example of Implementation

Personal notes

So when you have the same index, but a different tag, you still have a miss, but instead of overwriting the data, you put it in a new set. If all the sets are occupied, then you overwrite the oldest piece of data.

In the image below, you have a 3-way set-associative cache.

Example

Consider a 4-way set associative cache with cache size of 4096 blocks, 4 word block size, with byte-addressable memory, and 64-bit address.

4-way set associative uses 4 blocks per set, so we have 4096 blocks / 4 blocks per set = 1024 total sets (10-bit index field)

• 4 words per block so thats 2 bits we need to index the word
• (64 - 2) - 10 - 2 = 50-bit tag index
  • I subtract 2 remember, because of the Alignment Restriction

total number of tag bits = 50 X 4blocks/set X 1024 sets = 204.8K tag bits

Related

• Direct Mapped Cache
• Fully Associative Cache