Set Associative Cache: Calculate size of tag?

11
votes

I'm struggling to solve this question, I've looked around but all of the similar questions are more advanced than mine, making use of logs, it's more advanced than we've done in our class. Here's the question:

Suppose you have a 4-way set associative cache which has in total 4096 bytes of cache memory and each cache line is 128 bytes. How many sets are there is this cache? If memory is byte addressable and addresses are 16 bits then how many bytes are used for the tag?

Here's what I have so far:

4096/128 = num lines

4096/128/4 = 8 = num sets (each set is 4 lines in 4-way set assoiative)

So, need 3 bits to choose set (2^3=8)

We have 16-3 = 13 bits left for the tag and word.

Because the question says that memory is byte addressable, I think that this means that the word is 8 bits (= 1 byte) long, and thus the tag is 16-3-8 = 5 bits long.

Although I'm not quite sure about this. Does anyone have a solution to this problem?

2
cachingcpu-cache

2 Answers

14
votes

If memory is byte addressable

This statement just tell us that the main memory is byte addressable ie., architectures where data can be accessed 8 bits at a time, irrespective of the width of the data and address buses.

This doesn't affect the number of bit the tag has.

Solution:

4-way set associative

Total cache memory = 4096 bytes

Block size(cache line) = 128 byte

Number of cache line = 4096 / 128 = 32 lines

Number of sets in cache = 32 / 4 = 8 sets

╔════════════════════════════╗
║       16 bit address       ║
╠══════════╤════════╤════════╣
║ tag bit? │ 3 bits │ 7 bits ║
╚══════════╧════════╧════════╝

Word offset = log28 = 3 bits

Set offset = log2128 = 7 bits

Answer:

Tag bit = 16 - ( 3 + 7 ) = 6 bits

╔══════════════════════════╗
║      16 bit address      ║
╠════════╤════════╤════════╣
║ 6 bits │ 3 bits │ 7 bits ║
╚════════╧════════╧════════╝
0
votes

  • cache capacity is 4096 bytes means (2^12) bytes .

  • Each Block/line in cache contains (2^7) bytes

-therefore number of lines or blocks in cache is:(2^12)/(2^7)=2^5 blocks or lines in a cache

  • As it is 4 way set associative, each set contains 4 blocks, number of sets in a cache is : (2^5)/2^2 = 2^3 sets are there. so from these we got to know that 3 bits are required for adressing set offset.

  • As it is byte addressable , to address a byte offset we require 7 bits as we have 128(2^7) bytes in each block.

  • Remaining 6 bits will be allocated for tag.