GATE CS 2026 Set 2 Q.56: Memory Hierarchy: Cache, Main Memory and Secondary Storage

Consider a system with 1 MB physical memory and a word length of 1 byte. The system uses a direct mapped cache, with block numbers starting from 0. The word with physical address 0xA2C28 is mapped to the cache block number $176_{10}$ . The maximum possible size of the cache (in KB) for this configuration is ___________. (answer in integer)

Note: $1\text{K}=2^{10}$ and $1\text{M}=2^{20}$

Your answer

Official answer and solution

Official answer: 128
From: Official GATE 2026 answer key

Solution

Match the binary pattern of cache block index $176_{10} = 10110000_2$ within the 20-bit physical address 0xA2C28 to find the maximum bit position $b + k$ of the cache index + offset fields.

Writing the 20-bit physical address 0xA2C28 from MSB (bit 19) to LSB (bit 0) and the target cache block number $176_{10}$ in binary:

\texttt{0xA2C28} = \underbrace{1010}_{19..16}\,\underbrace{0010}_{15..12}\,\underbrace{1100}_{11..8}\,\underbrace{0010}_{7..4}\,\underbrace{1000}_{3..0}

176_{10} = 128 + 32 + 16 = 10110000_2

In a direct-mapped cache with $2^k$ blocks (where $k \ge 8$ since $176 < 2^k$ ) and block size $2^b$ bytes, the $k$ -bit cache index occupies bits $[b, b+k-1]$ of the physical address and must evaluate to $176_{10}$ :

Inspecting the bits of 0xA2C28, bits $[13..6]$ are 10110000 ( $= 176_{10}$ ), so the block offset has $b = 6$ bits ( $2^6 = 64$ bytes per block).
Furthermore, bits $14$ , $15$ , and $16$ are all 0 (bit $17$ is 1). Thus the cache index field can extend from bit $6$ up to bit $16$ (00010110000 $= 176_{10}$ ), giving $k = 11$ index bits ( $2^{11} = 2048$ blocks).

Therefore, the maximum possible cache size is:

\text{Cache Size} = 2^{b + k} = 2^{6 + 11} = 2^{17}\text{ bytes} = 128\text{ KB}

Final answer

128

Common trap

Stopping at bit 15 (0x2 = 0010) without noticing that bit 16 (the LSB of 0xA = 1010) is also 0.

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

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 56 of 65
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.

Question

Solution

Source