GATE CS 1990 Q7a — Memory Hierarchy: Cache, Main Memory and Secondary Storage

We can determine the address structure by analyzing the specifications of the main memory and the cache memory.

1. Bits required for addressing the main memory

• Number of blocks in main memory: $16,384 = 2^{14}$ blocks
• Block size: $256 = 2^8$ words
• Total number of words in main memory: $$\text{Total Words} = 2^{14} \text{ blocks} \times 2^8 \text{ words/block} = 2^{22} \text{ words}$$
• Since each word is individually addressable, the number of bits required to address the main memory is: $$\log_2(2^{22}) = 22 \text{ bits}$$

2. Bits for TAG, SET, and WORD fields

The 22-bit physical address is divided into three fields: [ TAG | SET | WORD ].

• WORD field: Since each block contains $256 = 2^8$ words, we need $8$ bits for the WORD (offset) field.
• SET field: The cache has $128$ blocks divided into $4$-block sets (4-way set associative). $$\text{Number of sets} = \frac{128 \text{ blocks}}{4 \text{ blocks/set}} = 32 \text{ sets} = 2^5 \text{ sets}$$ Thus, we need $5$ bits for the SET field.
• TAG field: $$\text{TAG bits} = \text{Total Address bits} - (\text{SET bits} + \text{WORD bits})$$ $$\text{TAG bits} = 22 - (5 + 8) = 9 \text{ bits}$$

Summary of fields:

• TAG: $9$ bits
• SET: $5$ bits
• WORD: $8$ bits