How many bits are needed needed for 2 way associative cache addressing?

0
votes

The question below is confusing me, as it is not similar to other examples that I have seen.

For a 128 byte memory and 32 bytes 2-way set associate write-back, write-allocate data cache with 4 byte blocks and LRU (Least Recently Used) replacement policy, show the memory address breakdown for block offset, set index, and tag fields. How many bits are needed for each field?

I came up with 7 bits needed for the addressing in total. Of those 7 bits, 2 bits are needed for the block offset, 2 bits for the set index, and 3 bits for the tag. Is this correct?

1
cachingmipscpu-architecturecpu-cache

1 Answers

3
votes

First let's do some maths:

  • You need 7 bits to address 128 bytes of memory.
  • The cache has 32 bytes and every block has 4 bytes. Therefore your cache can hold 32 bytes / 4 bytes_per_line lines yielding 8 lines. As the cache is 2-way set associative each block can use any of the two lines of each set. So you have 4 sets of 2 lines each.

Thus:

  • You need 2 bits to address a given offset within the block
  • You need 2 bits to address a given set
  • The remaining 3 bits are for the tag

The encoding of each address is therfore:

  tag(3 bits) | set(2 bits) | offset(2 bits)