2
$\begingroup$

I have a homework assignment dealing with caches. We are asked to compute the total number of bits of storage required for the cache, including tags and valid bits. Then compute the overhead for the cache incurred by the tags and valid bits.

Info given: Consider a direct-mapped cache with 16KBytes of storage and a block size of 16 bytes. Assume that the address size is 32 bits.

So I've done the calculation and get a total number of 32 bits required. We were given the following formula:

(bits/tag) + (bits/index) + (bits/block offset) = total number of bits

I am unsure about my number of sets. I did this by:

  • 16 byte blocks is 2^4, so 4 bits for block offset
  • 2^32 / 16 bytes per frame gives us 2^28 blocks
  • 2^28 blocks / 65536 sets gives us 2^12 blocks/set, so we need 2^12 unique tags
  • Add them together: 12 (bits/tag) + 16 (bits/index) + 4 (bits/block offset), which gives us 32 bits

I got my number of sets from 2^size, which is 2^16.

The second issue I'm running into is now calculating the overhead, given those numbers.

We were provided the formula

(Address size - bit offset - bit block offset) * number of frames = kbits of tags

When doing this, I get the following:

(32 - 16 - 4) * 65536 = 12 * 65536 = 786432bits
= 786432bits / 1024 = 768 KBits
= 768 * 0.125 = 96 Kbytes
= (96KBytes / 16KBytes)
= 600% overhead

Which obviously does not make sense.

I believe my issue is the number of sets, but from what I can gather from online and our lecture notes, the number of sets (in a direct-mapped cache) is equal to the size of the cache, so that would be 2^16, so 65536.

We have lecture notes that describe how to do this, but they were with 8byte blocks and we were told the number of sets (in the case of the notes, the size was 256, which is 2^8, which I can only presume is 2^block size).

Any insight will be of help!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

I'll give these hints without actually solving it for you

1) You do not need to provide tags for all memory, only for the memory that is in the cache.

2) As the block (cache line) is 16 bytes, you only need one tag for each of these.

3) The valid bit are also only for the cached I guess.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for the input. However, the way I described above is how my professor wants it, and I guess I should refine my question to: Am I right on the number of sets/frames being 65536? $\endgroup$
    – Carousser
    Commented Dec 3, 2016 at 23:05
  • $\begingroup$ In the cache these can only be 16K / 16 bytes sets ie. cache lines. $\endgroup$
    – Surt
    Commented Dec 3, 2016 at 23:41
  • $\begingroup$ As for my understanding of a direct mapped cache, a frame/set consists of: 1 block of data, 1 valid bit, and a tag. Since the cache is 16kb, using 16byte block sizes, wouldn't that mean there are 65536 blocks of data, giving us 65536 frames/sets? $\endgroup$
    – Carousser
    Commented Dec 3, 2016 at 23:49
  • $\begingroup$ Or would it be 16kb/16b, giving us 1024 sets? $\endgroup$
    – Carousser
    Commented Dec 3, 2016 at 23:55
  • $\begingroup$ The 1024 sets (cache lines, set-associativity is not the same) can be in the cache at a time, that there are more different sets that could be loaded at some time doesn't impact what is in the cache, but the tag needs to cover it. $\endgroup$
    – Surt
    Commented Dec 4, 2016 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.