Skip to content
GATETECH
Official PYQ · 2023Q54Memory Hierarchy: Cache, Main Memory and Secondary StorageNAT2 marks

GATE CS 2023 Q54 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

Explain with AI
An 88-way set associative cache of size 64 KB  (1 KB=1024  bytes)64 \mathrm{~KB} \;(1 \mathrm{~KB}=1024\; \text{bytes}) is used in a system with 3232-bit address. The address is sub-divided into TAG, INDEX,\text{TAG, INDEX}, and BLOCK OFFSET.\text{BLOCK OFFSET.}

The number of bits in the TAG\text{TAG} is ___________.
View worked solution

Answer: 19

In a set-associative cache, the physical address is divided into three fields:

Address Width=TAG+INDEX+BLOCK OFFSET\text{Address Width} = \text{TAG} + \text{INDEX} + \text{BLOCK OFFSET}

Let us express the number of bits for each field:

  • Let the block size be BB bytes. The number of bits required for the BLOCK OFFSET is: BLOCK OFFSET=log⁡2(B)\text{BLOCK OFFSET} = \log_2(B)
  • The number of sets in an NN-way set-associative cache is given by: Number of Sets=Cache SizeN×B\text{Number of Sets} = \frac{\text{Cache Size}}{N \times B} Therefore, the number of bits for the INDEX is: INDEX=log⁡2(Cache SizeN×B)=log⁡2(Cache SizeN)−log⁡2(B)\text{INDEX} = \log_2\left(\frac{\text{Cache Size}}{N \times B}\right) = \log_2\left(\frac{\text{Cache Size}}{N}\right) - \log_2(B)

Now, we sum the INDEX and BLOCK OFFSET bits:

INDEX+BLOCK OFFSET=[log⁡2(Cache SizeN)−log⁡2(B)]+log⁡2(B)\text{INDEX} + \text{BLOCK OFFSET} = \left[\log_2\left(\frac{\text{Cache Size}}{N}\right) - \log_2(B)\right] + \log_2(B) INDEX+BLOCK OFFSET=log⁡2(Cache SizeN)\text{INDEX} + \text{BLOCK OFFSET} = \log_2\left(\frac{\text{Cache Size}}{N}\right)

Notice that the block size BB cancels out completely. This means the sum of the index and block offset bits is independent of the block size.

Given:

  • Cache Size=64 KB=216 bytes\text{Cache Size} = 64 \text{ KB} = 2^{16} \text{ bytes}
  • Associativity (N)=8=23\text{Associativity } (N) = 8 = 2^3
  • Address Width=32 bits\text{Address Width} = 32 \text{ bits}

Substituting these values into our equation:

INDEX+BLOCK OFFSET=log⁡2(21623)=log⁡2(213)=13 bits\text{INDEX} + \text{BLOCK OFFSET} = \log_2\left(\frac{2^{16}}{2^3}\right) = \log_2(2^{13}) = 13 \text{ bits}

Finally, we calculate the number of bits in the TAG field:

TAG=Address Width−(INDEX+BLOCK OFFSET)\text{TAG} = \text{Address Width} - (\text{INDEX} + \text{BLOCK OFFSET}) TAG=32−13=19 bits\text{TAG} = 32 - 13 = 19 \text{ bits}

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Memory Hierarchy: Cache, Main Memory and Secondary Storage questions