GATE 2023 CS Q.64: solution and answer

GATE 2023 · CSQ.64 · 2 marks · NAT

An 8-way set associative cache of size 64 KB (1 KB = 1024 bytes) is used in a system with 32-bit address. The address is sub-divided into TAG, INDEX, and BLOCK OFFSET.

The number of bits in the TAG is ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

TAG = 19 bits

Official answer: 19Source: Official answer key, GATE 2023 CS (IIT Kanpur)

Cache capacity = 64 KB = 65536 bytes; it is 8-way set associative; the address is 32 bits wide, split into TAG, INDEX and BLOCK OFFSET.
Let the (unstated) block size be $B$ bytes. Number of blocks in the cache $= \frac{65536}{B}$ . Since the cache is 8-way set associative, number of sets $= \frac{65536}{8 B}$ .
$INDEX bits = lo g_{2} (number of sets) = lo g_{2} (\frac{65536}{8 B})$ , and $OFFSET bits = lo g_{2} (B)$ .
Adding them: $INDEX + OFFSET = lo g_{2} (\frac{65536}{8 B}) + lo g_{2} (B) = lo g_{2} (\frac{65536}{8}) = lo g_{2} (8192) = 13 bits$ — the block size $B$ cancels out, so this total is the same for every possible block size, which is exactly why the question can be answered without ever specifying it.
$TAG bits = Address width - (INDEX bits + OFFSET bits) = 32 - 13 = 19$ bits.

KEY IDEA

In a set-associative cache, $Cache size = Number of sets \times Ways \times Block size$ , so $Number of sets \times Block size = \frac{Cache size}{Ways}$ , a quantity independent of block size. Since $INDEX bits + OFFSET bits = lo g_{2} (Number of sets \times Block size)$ , this sum is fixed even though the block size itself is never stated in the question — only $TAG bits = Address width - (INDEX + OFFSET)$ needs to be found, and it comes out the same for every possible block size.

WATCH OUT FOR

Assuming a block/line size must be given and getting stuck, or (wrongly) assuming a specific block size such as 32 or 64 bytes and computing a TAG value that depends on that unstated assumption; also forgetting to divide by the associativity (8-way) when computing the number of sets, which gives INDEX+OFFSET = 16 and TAG = 16 instead of 19.

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

GATE 2023 CS Q.64: solution and answer

Answer and solution

More Memory & cache questions