1
$\begingroup$

When it comes to defining the memory address structure given the RAM size, cache size, and other parameters such as the cache block size..., we can have the following generalization: $$Address = TAG|Index|offset$$ We then have: $size(offset) = log_2(word \ count \ per \ block)$

For the index, we will have: $$size(index) = log_2(number \ of \ sets \ in \ cache)$$ which gets reduced to the following: $$size(index) = log_2(\frac{cache \ size}{block \ size \ \times \ degree \ of \ associativity})$$

And finally, for the tag, we find: $$size(TAG) = log_2(\frac{RAM \ size \times degree \ of \ associativity}{cache \ size})$$

My question is related to the case where the degree of associativity is not a power 2, there are many CPUs that have a non power of 2 degree of associativity such as the Intel i7-4700HQ.

My question is related to how the target set is identified in the cache given a certain word address. What complexities are aligning in this case, and how they are handled?

$\endgroup$

1 Answer 1

1
$\begingroup$

6-time associativity means one cache line can be stored in six different locations. So the hardware identifies six locations where the data might be stored and checks all six.

The description assumes associativity is a power of two, there is no need for that. Just assume you had six caches with no associativity and tried all six in parallel. The only change you need: You only have a cache miss if all six caches miss. And you need LRU information per line so you know which cache to use when there is a miss.

In each non-associative cache, the hardware needs to identify the cache line for an address very, very fast. With a power of two size that is very easy.

In theory, if you had a power-of-2 design and you thought about either doubling the size or say increasing the size by 50%: Take the highest 3 bits of the address that you use to calculate the cache line index and take two more bits. That’s 32 values that you currently map to 8 by dropping the highest two bits. You can map them to 16 values by dropping one bit. Or you can map them to 11 values (by subtracting 11 if >= 11 and subtracting 22 if >= 22). So the number of cache lines increases by 3/8ths. I think that would work, but nobody does it. Because you get the same effect with associativity (change 4-way to 5-way to increase cache size by 5) much easier, and you want high associativity anyway.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer, I just got it, what about the number of sets in the cache, does it necessarily need to be a power of 2? $\endgroup$ Mar 8, 2023 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.