title: Set Associative Cache: Calculate size of tag?
body: <p>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:</p>
  
  <blockquote>
    <p>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?</p>
  </blockquote>
  
  <p>Here's what I have so far:</p>
  
  <p><code>4096/128 = num lines</code></p>
  
  <p><code>4096/128/4 = 8 = num sets</code> (each set is 4 lines in 4-way set assoiative)</p>
  
  <p>So, need 3 bits to choose set <code>(2^3=8)</code></p>
  
  <p>We have <code>16-3 = 13 bits</code> left for the tag and word.</p>
  
  <p>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 <code>16-3-8 = 5</code> bits long.</p>
  
  <p>Although I'm not quite sure about this. Does anyone have a solution to this problem?</p>