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!