Direct Mapped Cache

Question

A direct mapped cache consists of 16 blocks. main memory contains 16K blocks of 8 bytes each. What is the main memory address format (meaning the size of each field).

I know the fields are Tag|Block|Offset . I just don't know how to get the sizes of each.

Answer 1

Is this homework?

In order to solve this problem, you'd need to know the address size of the architecture in question. General solution:

Let C be the size of the cache in bits.
Let A be the size of an address in bits.
Let B be the size of a cache block in bits.
Let S be the associativity of the cache (in ways, direct-mapped being S=1 and fully associative being S=C/B)

L, the number of lines in the cache, is equal to C/B. That's the number of cache bits divided by the number of bits per line. Q, the number of sets in the cache, is equal to L/S. That's the number of lines divided by the associativity. The reasons for this line and the above should be obvious; if they aren't, hit the textbook again before reading below.

Now, let's work out three things: the displacement bits, the block bits, and the tag bits.

The displacement bits are to find a particular item within a cache line. Assuming byte-addressable memory, D, the number of displacement bits, is ceil(log2(ceil(B/8))). That's the log base two of the number of bytes in a cache line, rounded up at each step. If memory is two-byte addressable, the inner portion there would be B/16, etc.

The block bits are to find the cache set we want within the cache. Thus, O, the number of block bits, is ceil(log2(Q)). That's the log base two of the number of sets in the cache.

The tag bits are whatever is left. So, T, the number of tag bits, is A-D-O. In English, the number of bits in an address minus the number of bits used for the other two portions. We don't have to consider associativity here because we already handled it above in using Q instead of L.

In summary:

• The displacement bits are as many as you need to specify a particular byte within a line
• The block bits are as many as you need to specify a particular set in the cache
• The tag bits are any bits left over

Calculate the tag length last. This is definitely easier.

P.S. - Note that in reality, the cache will also store a dirty bit and some other metadata with each line. However, these questions usually ignore things like that, so I did too.