A digital computer has a memory unit of 64K X 16 and a cache memory of 1K words. The cache uses direct mapping with a block size of four words. I. How many bits are there in the tag, index, block, and word fields of the address format? II. How many bits are there in each word of cache, and how they

Main memory is $64\text{K} \times 16$. Since $64\text{K} = 2^{16}$, the memory address has 16 bits and each word is 16 bits wide. The cache has 1K words, so it has $1\text{K} = 2^{10}$ words. A block holds 4 words.

In direct mapping, the address is split into a tag, an index and a word field. The index selects the cache location. The tag is stored with the data and is compared to find a hit.

I. Address fields

The word field selects one of 4 words in a block, so it has $\log_2 4 = 2$ bits. The cache has $1024 / 4 = 256$ blocks, so the block field has $\log_2 256 = 8$ bits. Together the word and block fields form the index of 10 bits, as the cache has 1K words. The tag takes the remaining bits:

$$\text{tag} = 16 - 10 = 6 \text{ bits}$$

So the address format is

The total is $6 + 8 + 2 = 16$ bits.

II. Bits in each cache word

Each cache word stores the 16-bit data, the 6-bit tag of the block it belongs to, and 1 valid bit. The valid bit tells whether the word holds real data or is still empty after power on. So

$$16 + 6 + 1 = 23 \text{ bits}$$

The 16 bits are the data, 6 bits are the tag used for the hit check, and 1 bit is the valid flag. The whole cache is therefore $1\text{K} \times 23$ bits.

III. Number of blocks

$$\text{blocks} = \frac{1024 \text{ words}}{4 \text{ words per block}} = 256$$

The cache can hold 256 blocks. Main memory has $65536 / 4 = 16384$ blocks, so every cache block is shared by $16384/256 = 64$ memory blocks. These 64 blocks differ only in their tag value.

The tag is stored along with the data so that the cache can tell which of the 64 memory blocks is now present at an index. Without the tag, two different memory blocks with the same index could not be told apart. A new block replaces the old one directly, because direct mapping gives only one possible place.

Working example

Take the address $\text{0x1234}$. Its upper 6 bits give tag $= 4$. The next 8 bits give block number $= 141$, and the last 2 bits give word $= 0$. The cache looks at index $564$ (block 141, word 0). If the valid bit is 1 and the stored tag is 4, it is a hit and the word is sent to the CPU. Otherwise it is a miss. The whole 4-word block is then read from main memory, and the tag is updated to 4.