GATE CS Mastery
Cheat sheets

GATE CS 2019 · Computer Organization and Architecture

Question 11

MCQPrinted as CS Q.11 markWrong answer: −1/3Easy (estimate)

Question

A certain processor uses a fully associative cache of size 16 kB16\text{ kB}. The cache block size is 16 bytes16\text{ bytes}. Assume that the main memory is byte addressable and uses a 3232-bit address. How many bits are required for the Tag and the Index fields respectively in the addresses generated by the processor?

Choose one option
Official answer and solution
Official answer
D
From
Official GATE 2019 answer key

Solution

Recall the addressing fields of a fully associative cache.

In a cache memory hierarchy, a memory address is divided into:

Address=[Tag∣Index (Set)∣Block Offset]\text{Address} = [\text{Tag} \mid \text{Index (Set)} \mid \text{Block Offset}]

We are given:

  • Cache size = 16 kB16\text{ kB}
  • Block size = 16 bytes=24 bytes16\text{ bytes} = 2^4\text{ bytes}, which requires log⁡2(16)=4 bits\log_2(16) = 4\text{ bits} for the block offset.
  • Main memory address = 32 bits32\text{ bits}.

In a fully associative cache, any block can be placed in any cache line. Effectively, there is only 11 set (the entire cache is a single set). Therefore, the number of index bits required is:

Index bits=log⁡2(1)=0 bits\text{Index bits} = \log_2(1) = 0\text{ bits}

The remaining address bits are allocated to the Tag field:

Tag bits=32−Index bits−Offset bits=32−0−4=28 bits\text{Tag bits} = 32 - \text{Index bits} - \text{Offset bits} = 32 - 0 - 4 = 28\text{ bits}

Thus, Tag = 28 bits28\text{ bits} and Index = 0 bits0\text{ bits}.

Final answer

D

Common trap

Calculating index bits as log2(number of cache blocks), which applies only to direct-mapped caches.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2019 Computer Science and Information Technology (CS)
Question
11 of 65, printed as CS Q.1
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.