Skip to content
GATETECH
Official PYQ · 2013Q20Memory Hierarchy: Cache, Main Memory and Secondary StorageMCQ1 mark

GATE CS 2013 Q20 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

Explain with AI

In a kk-way set associative cache, the cache is divided into vv sets, each of which consists of kk lines. The lines of a set are placed in sequence one after another. The lines in set ss are sequenced before the lines in set (s+1)(s+1). The main memory blocks are numbered 0 onwards. The main memory block numbered jj must be mapped to any one of the cache lines from

Choose one option
View worked solution

Answer: A

In a kk-way set associative cache, the cache is divided into vv sets, where each set contains exactly kk cache lines.

A main memory block jj is mapped to set ss using the modulo operation:

s=j mod vs = j \bmod v

Since the cache lines are laid out sequentially, and each set contains kk lines:

  • Set 00 occupies lines 00 to k−1k-1.
  • Set 11 occupies lines kk to 2k−12k-1.
  • In general, set ss occupies lines from s×ks \times k to s×k+(k−1)s \times k + (k-1).

Substituting s=j mod vs = j \bmod v into the range, block jj can be mapped to any line in the range:

(j mod v)×kto(j mod v)×k+(k−1)(j \bmod v) \times k \quad \text{to} \quad (j \bmod v) \times k + (k-1)

This matches Option A.

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