Electronic – Cache memory calculation

cache

I'm learning the logic of cache memories. I wonder if you can verify that I understood correctly. If a cache memory in the tag field has 16 bits, the set field has 10 bits and the byte in block field is 6 bits, then I can deduce from only that information that the capacity is 128 kbyte and it is 2-way set associative with block size 64 byte because 2⁶ = 64 byte from the byte in block field. 2¹⁰ = 1024 but could some other capacity with some other associativity number satisfy the requirements?

I learn that the formulas are

number of blocks = capacity / blocksize

number of sets = number of blocks / #associativity

Therefore I could double both the associativity to 4-way but I could not satisfy the requirements with a 4-way cache because it would require another number of bits in the set field.

Did I understand correctly?

Best Answer

Does this picture help you to understand how associative caches work structurally?

enter image description here borrowed from here

In a nutshell the block offset bits determine your block size (how many bytes are in a cache row, how many columns if you will). The index bits determine how many rows are in each set. The capacity of the cache is therefor 2^(blockoffsetbits + indexbits) * #sets. In this case that is 2^(4+4) * 4 = 256*4 = 1 kilobyte.

For the same size cache (capacity), if you were to go from 4-way to two-way set associative, it two way associative, you could do so by either doubling the rows in each set or by doubling the columns in each set, which is to say doubling the number of cache lines or doubling the block size.

If you were to choose to double the number of rows, you would end up with your 12-bit address being broken into a 5-bit index and a 4-bit block offset, leaving a 3-bit tag.

If you were to choose to double the block size, you would end up with your 12-bit address being broken into a 4-bit index, a 5-bit block offset, leaving a 3-bit tag.

So to re-iterate, I think the governing formulas for associative caches are:

Cache Capacity = (Block Size in Bytes) * (Blocks per Set) * (Number of Sets)
Index Bits = LOG2(Blocks per Set)
Block Offset Bits = LOG2(Block Size in Bytes)
Tag Bits = (Address Bits) - (Index Bits) - (Block Offset Bits)

In your originally stated example, I don't think you can deduce the size of the cache based on the size of your respective address bit fields without making an assumption about the associativity. If it is 2-way associative, then you could say:

Cache Capacity = (2^6) * (2^10) * (2) = 2^18 = 2^8 kilobytes = 256 kilobytes. I'm not sure how you came up with 128 kilobytes. That would be the case if it were 1-way associative (direct mapped).

For a 128kB (2^17 bytes) cache capacity, you could make a 4-way associative cache with a 64 byte block size by saying:

2^17 = 2^6 * (Blocks per Set) * 4
Blocks per Set = 2^17 / 2^6 / 2^2 = 2^9 = 512

... and therefore allocating 9 index bits, 4 block offset bits, and the rest (19) tag bits.

Related Topic