GATE CS 2015 Set 3 Q14 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

In a direct-mapped cache, the physical address is divided into three fields: Tag, Line Index (or Cache Line Address), and Block Offset.

1. Determine the Bit Widths

• Physical Address Size: The main memory is $2^{20}$ bytes, so the physical address is $20$ bits.
• Block Offset: The block size is $16$ bytes ($2^4$ bytes), which requires $\log_2(16) = 4$ bits.
• Line Index: The cache has $2^{12}$ lines, which requires $\log_2(2^{12}) = 12$ bits.
• Tag: $$\text{Tag bits} = \text{Physical Address bits} - (\text{Line Index bits} + \text{Block Offset bits})$$ $$\text{Tag bits} = 20 - (12 + 4) = 4 \text{ bits}$$

Thus, the 20-bit physical address format is partitioned as:

2. Analyze the Address $\textsf{(E201F)}_{16}$

Convert the hexadecimal address $\textsf{(E201F)}_{16}$ into binary:

Now, split the 20-bit binary address according to our fields:

• Tag (MSB 4 bits): $$1110_2 = \textsf{E}_{16}$$
• Line Index (Middle 12 bits): $$0010 \; 0000 \; 0001_2 = \textsf{201}_{16}$$
• Block Offset (LSB 4 bits): $$1111_2 = \textsf{F}_{16}$$

Therefore, the tag is $\textsf{E}$ and the cache line address is $\textsf{201}$.