Let's say, I have a cache with:

  • 2^32 bytes of memory
  • 2048 blocks (of 16 bytes each)

Now I'm trying to figure out how much bits each field will contain.

Direct mapped:

One block is 16 bytes (16 * 8 = 128 bits). The block also contains 1 dirty bit and 1 valid bit. I know that since there are 2048 (=2^11) blocks, and the whole block contains 16 bytes (=2^4) the tag-field will be 4 + 11 + 1 (valid) + 1 (dirty) = 17 bits. So the whole size of 1 block will be 17 + 128 bits. Is this right?

And if so, where do I need the given 2^32 bytes of memory, and what is the difference with the direct-mapped cache in comparison to counting the 4-way-set-associative cache fields?

I hope someone can help me, thanks in advance!


Maybe it is easier to look at addresses :

  • address range : A[31:0]
  • block address : A[3:0]
  • cache line index : A[14:4] : 2048 = 11bits

Each tag contains :

  • addresses A[31:15] : 17bits
  • valid bit
  • dirty bit, if it is a write-back cache

So 18bits (write-thu) or 19bits (write-back) per tag.

128+18 per block (or 128+19), 2048*(128+18) bits for the whole cache. (excluding EDC, sub-blocking...)

The tags contains the part of the address bits not indexed by the cache (not the contrary).

Way associative caches need replicating both tags and data. Additional bits are also needed in that case for the replacement information (LRU, PLRU...) : Selecting which cache way should be replaced when a cache miss occurs.

  • $\begingroup$ Thanks!!! I only can't seem to figure out how to calculate it for the 4-way. On wikipedia it says I have to divide the number of blocks by 4 (4-way). 2048 / 4 = 512 (=2^9). So 32 - 9 - 3 = 20 bits (21 bits with wb), for the tag field? $\endgroup$ – Steven Raaijmakers Jan 3 '15 at 12:17
  • $\begingroup$ Yes, 20 bits for 4-ways set-asssociative, if the size of the cache remains the same (2048 lines). If you want to store history bits in tags, a true LRU history for 4 ways can be stored in 5 bits (there are 24 possible combinations), so add 2 bits per tag. Alternatively, a less efficient random replacement algorithm can be used, it does not need additional tag bits. $\endgroup$ – TEMLIB Jan 3 '15 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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