Explain the direct mapping technique. Consider a digital computer has a memory unit of 64k*16 and cache memory of 1k words. The cache uses direct mapping with 4 block size of four words. (i) How many bits are there in the tag, block and word fields of the address format? (ii) How many blocks can the

Direct mapping

In direct mapping, each block of main memory can be placed in only one fixed line of the cache. The line number is given by

$$\text{line} = (\text{block number}) \bmod (\text{number of cache lines})$$

The main memory address is divided into three fields: tag, index (block or line) and word. The word field selects a word inside the block. The block field selects the cache line. The tag is the remaining high bits. It is stored with each cache line. It tells which of the many memory blocks that share the line is now present.

On a memory reference, the line field selects the line. The stored tag is compared with the tag of the address. If they are equal and the valid bit is 1, it is a hit, and the word is taken. Otherwise it is a miss. The whole block is read from main memory into that line, and the old block is overwritten. No replacement algorithm is needed.

Merits: simple, cheap, and fast, as only one tag comparison is needed. Demerit: if two active blocks map to the same line, they replace each other again and again (thrashing), though other lines are free.

Numerical

Main memory is $64\text{K} \times 16$, so the address has $\log_2 65536 = 16$ bits. The cache has 1K words, so the index has $\log_2 1024 = 10$ bits. A block has 4 words.

(i) The word field needs $\log_2 4 = 2$ bits. The cache has $1024/4 = 256$ lines, so the block field needs $\log_2 256 = 8$ bits. The tag is

$$16 - 8 - 2 = 6 \text{ bits}$$

(ii) The number of blocks the cache can hold is

$$\frac{1024}{4} = 256 \text{ blocks}$$

Therefore the fields are tag 6 bits, block 8 bits and word 2 bits, and the cache can hold 256 blocks. The main memory has $65536/4 = 16384$ blocks, so every cache line is shared by 64 memory blocks.