# 2-way set associative cache exercise

In the exercise I have a 32 bit processor with a 2-way set associative cache. I have 32 bit addresses: 31-14 tag, 13-5 index, 4-0 offset.
Calculate:
1) Cache line size in number of words (1 word = 4 bytes)
2) Total cache size in bits

In the presence of the following sequence of accesses in memory, considering the initially empty cache, indicate for each access if it is hit, miss, or replace:
17920 17948 149024 83488 17952 148998 149012 17964 148648 17848

I think answer at the first part should be:
1) 2^5 = 32byte --> 32/4 = 8words
2) 32byte = 256bit --> size = 256 * (4096 + 18 + 1)

Is it correct? And I'm not sure on how to complete the second part of the exercise

You have 5 bits for the offset. Assuming byte addressed memory, you'll need four memory addresses to construct a word. So take two bits from the offset. Now you are left with 3 bits in the offset, hence a cache line would have 8 words.

9 bits for have been used for the index, therefore 2^9 cache blocks are present. Since its a two way assoc, each block contains 2 cache lines.

data storage =
(2^9 cache blocks
* 2 cache lines in a block
* 8 words per cache line
* 32 bits in a word) bits
= 262,144 bits


Now the rest is bit tricky as the question does not provide what other bits are available. Assuming there is a valid bit present,

per cache line we need 1 bit for valid bit + 18 bits of tag data = 19 bits of "meta" data

512 cache blocks * 2 lines per block * 19 bits = 19,456
So the total size in bits = 262,144+ 19,456 = 281,600


If there is also a dirty bit present, equations changes to

 per cacheline,
1 bit for valid bit + 1 bit for dirty bit + 18 bits of tag data = 20 bits of "meta"data


For the second part, get the binary representation of the address. Break it into tag, index and the offset. Fill up the cache based on the tag and the index. See what happens.

• First of all thanks for your answer. I still have a few questions about the second part. I read somewhere that to find the block belonging to the address you have to look at the 2 least significant bits of the index, is that correct? – beautifulmount Feb 7 '18 at 19:39
• My sincere apologies for the grave mistake in the earlier answer.Please check the updated version, – Isu Feb 8 '18 at 9:40
• ok so now I have to check if there are addresses with the same index and tags (excluding the first access) and in that case I will have a hit, otherwise a miss. Once there has been access for each block I can have replace, right? – beautifulmount Feb 8 '18 at 13:15
• Yes, remember to allocate two cache lines per block as its a 2 way assoc. cache. Bottom line, if you have two accesses with the same index bits, you don't need to replace the older one. – Isu Feb 8 '18 at 15:49
• ok just to be sure, in my case I have these INDEX-TAG addresses (expressed in decimal for convenience): 48-1, 48-1, 49-9, 49-3, 49-1, 48-9, 48-9, 49-1, 37-5, 45-1. And then I get: MISS, HIT, MISS, MISS, REPLACE, MISS, HIT, HIT, MISS, MISS. – beautifulmount Feb 8 '18 at 16:08