GATE CSE 2025 | Set 1 | Question: 26

Question

Consider a memory system with $1 \mathrm{M}$ bytes of main memory and $16 \mathrm{~K}$ bytes of cache memory. Assume that the processor generates $20$-bit memory address, and the cache block size is $16$ bytes. If the cache uses direct mapping, how many bits will be required to store all the $\operatorname{tag}$ values? [Assume memory is byte addressable, $1 \mathrm{~K}=2^{10}$, $1 \mathrm{M}=2^{20}$.]

• A. $6 \times 2^{10}$
• B. $8 \times 2^{10}$
• C. $2^{12}$
• D. $2^{14}$

Comments

Option A is correct

Answer 1

Answer - (A)

Answer 2

Option - a

Comments

A.

Answer 3

We are given a memory system with the following parameters:

• Main memory size: $1~\text{M bytes} = 2^{20}$ bytes  
• Cache size: $16~\text{K bytes} = 2^{14}$ bytes  
• Cache block size: $16$ bytes = $2^4$ bytes  
• Address width: $20$ bits (byte-addressable)  
• Cache organization: Direct-mapped

In a direct-mapped cache, each memory block maps to exactly one cache line based on its index.

• Number of cache lines (blocks) = $\frac{\text{Cache size}}{\text{Block size}} = \frac{2^{14}}{2^4} = 2^{10}$

So, there are $2^{10}$ cache lines.A 20-bit address is partitioned into:

$$
\begin{array}{|c|c|c|}
\hline
\text{Tag} & \text{Index} & \text{Offset} \\
\hline
\end{array}
$$

• Offset: determines byte within a block → $\log_2(\text{block size}) = \log_2(16) = 4$ bits  
• Index: selects which cache line → $\log_2(\text{number of lines}) = \log_2(2^{10}) = 10$ bits  
• Tag: remaining bits → $20 - 10 - 4 = 6$ bits

Thus, each cache line stores a 6 bit tag. Since there are $2^{10}$ cache lines, and each requires 6 bits for its tag:

$$
\text{Total tag storage} = 6 \times 2^{10} \text{ bits}
$$

 

$$
\color{lime} \boxed{\text{A. } 6 \times 2^{10}}
$$

Answer 4

In Direct mapping Tag bits can be find out using Log(mms/cms)= 6 bits and Block offset bits its Log(Block size) = 4 bits and line number bits = 20-(TAG+BO) = 10 bits now calculate the tag directory size