# Number of bits for tag, index, and block in a direct-mapped cache

Suppose you have a 64-byte cache on a system with 16-bit memory addresses. If the cache is direct-mapped and it has 10 bytes of tag overhead in total, how many bits are used for the tag, index, and block offset within the 16-bit memory address?

I found this in the textbook Computer Organization and Design by Patterson and Hennessy, and I was hoping someone could work through it for me. In particular, I'm curious as to what "10 bytes of tag overhead" is and how it effects what the solution is. How are the tag, index, and block offset generally found given some cache design?

I suggest you explore this link and try all possible combinations. I found this interesting when I was initially trying to learn about cache mapping techniques.

http://www.ecs.umass.edu/ece/koren/architecture/Cache/default.htm

"10 bytes of tag overhead" is the amount of memory that you are using to store the cache tags.

Typically you would divide the address up like:

tag-bits | index-bits | block-offset-bits

The block-offset-bits need to be enough bits to index each byte in a cache-line (block). (So log-base-2 of the block-size.) The index-bits are used to decide which cache-line to look at (so needs to be log-base-2 of the number of cache lines.) The tag-bits are whatever is left over, and need to be compared to the tag on the cache line.

Hint for solving the problem: in a direct mapped cache the index-bits + block-offset-bits always need to be exactly enough to uniquely address every byte in the cache (so log-base-2 of 64 in your case.)

So then you know that the tag-bits need to be the _ bits remaining. And you have to divide up your 10 bytes = 80 bits of tag overhead between the tags. So that tells you how many tags you can have. Which tells you how many lines you can have, which tells you how many index-bits you need.