GATE 2026 CS2 Q.56: solution and answer

GATE 2026 · CS2Q.56 · 2 marks · NAT

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 $17 6_{10}$ . The maximum possible size of the cache (in KB) for this configuration is ____________. (answer in integer)

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The maximum possible size of the cache is $128 KB$ .

Official answer: 128Source: Official answer key, GATE 2026 CS2 (IIT Guwahati)

Physical memory $= 1 MB = 2^{20}$ bytes and the word length is 1 byte, so a physical address is 20 bits wide (bit19 to bit0), with no separate word-offset-within-word bits needed.
Write $0xA2C28$ in 20-bit binary: $10100010110000101000$ (bit19 $\dots$ bit0). (Check: this reproduces $0xA2C28 = 66666 4_{10}$ .)
A direct-mapped address splits as $Tag ∣ Block number (k bits) ∣ Block offset (b bits)$ , with block size $= 2^{b}$ bytes, number of blocks $= 2^{k}$ , and cache size $= 2^{k + b}$ bytes.
$17 6_{10} = 1011000 0_{2}$ (8 bits). Scanning every possible 8-bit window of the 20-bit address (all 13 offsets $b = 0, \dots, 12$ ) for the value $10110000$ shows exactly one match: bits $[13 : 6] = 1, 0, 1, 1, 0, 0, 0, 0 = 176$ . So the block-offset width must be $b = 6$ .
With $b = 6$ fixed, grow the block-number width $k$ upward from 8 one bit at a time; the field still reads 176 only while each newly absorbed higher bit is 0. bit14 $= 0$ ( $k = 9$ , field still $176$ ), bit15 $= 0$ ( $k = 10$ , still $176$ ), bit16 $= 0$ ( $k = 11$ , still $176$ ).
bit17 $= 1$ , so absorbing it changes the field's value away from 176 (it becomes $2048 + 176 = 2224$ ). Hence $k = 11$ is the largest block-number width consistent with the given mapping, i.e. at most $2^{11} = 2048$ cache blocks.
Maximum cache size $= 2^{k + b} = 2^{11 + 6} = 2^{17}$ bytes $= 2^{17} / 2^{10} = 2^{7} = 128 KB$ . (Tag width $= 20 - 17 = 3$ bits, nonzero, so the split is self-consistent.)

KEY IDEA

In a direct-mapped cache, the address splits into Tag | Block number ( $k$ bits) | Block offset ( $b$ bits). Given only the numeric value of the block number (not $k$ or $b$ individually), find every bit-offset $b$ at which an 8-bit window of the physical address equals that block number in binary; here only $b = 6$ works. Then, holding $b$ fixed, the block-number field can be widened ( $k$ increased) for free as long as every newly included higher-order bit is 0, since a leading 0 does not change the field's decimal value — this is what lets the cache be "maximum possible" size rather than a single fixed size.

WATCH OUT FOR

Assuming the number of bits in the binary form of the block number (here $17 6_{10} = 1011000 0_{2}$ , 8 bits) directly gives $k$ , and stopping there — i.e. computing cache size as $2^{8 + 6} = 16 KB$ instead of recognizing that higher-order zero bits can be folded into a wider block-number field without changing its decimal value, which is what the word "maximum possible" in the question is asking you to exploit.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 22 Memory & cache questions, with notes

GATE 2026 CS2 Q.56: solution and answer

Answer and solution

More Memory & cache questions