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.
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

  • $\begingroup$ You've given a complete answer to the first part but you don't ask any question about this answer. "Is it correct?" allows only "yes/no" answers which aren't really helpful to you or anyone else. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. For the second part, what did you try? Where did you get stuck? $\endgroup$ Feb 7 '18 at 21:01

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.

  • $\begingroup$ 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? $\endgroup$ Feb 7 '18 at 19:39
  • $\begingroup$ My sincere apologies for the grave mistake in the earlier answer.Please check the updated version, $\endgroup$
    – Isu
    Feb 8 '18 at 9:40
  • $\begingroup$ 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? $\endgroup$ Feb 8 '18 at 13:15
  • $\begingroup$ 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. $\endgroup$
    – Isu
    Feb 8 '18 at 15:49
  • $\begingroup$ 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. $\endgroup$ Feb 8 '18 at 16:08

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.