GATE CS 2013 Q.20 (CS Q.20): Memory Hierarchy: Cache, Main Memory and Secondary Storage

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

$(j \bmod v) * k$ to $(j \bmod v) * k + (k-1)$

$(j \bmod v)$ to $(j \bmod v) + (k-1)$

$(j \bmod k)$ to $(j \bmod k) + (v-1)$

$(j \bmod k) * v$ to $(j \bmod k) * v + (v-1)$

Official answer and solution

Official answer: A
From: Official GATE 2013 answer key

Solution

Derive the set index for memory block j and multiply by line capacity k to obtain the line number range.

In a $k$ -way set associative cache:

Total number of sets $= v$ .
Each set contains $k$ lines.
A main memory block numbered $j$ maps to set index: $s = j \bmod v$

Because the cache lines are arranged sequentially set by set:

Set 0 occupies lines $0$ through $k - 1$ .
Set 1 occupies lines $k$ through $2k - 1$ .
In general, set $s$ begins at line $s \cdot k$ and ends at line $s \cdot k + (k - 1)$ .

Substituting $s = j \bmod v$ :

\text{Starting line} = (j \bmod v) * k

\text{Ending line} = (j \bmod v) * k + (k - 1)

Thus, block $j$ may be placed in any cache line from $(j \bmod v) * k$ to $(j \bmod v) * k + (k - 1)$ .

Final answer

Option (A)

Common trap

Confusing the number of sets $v$ with associativity $k$ in the modulo operation.

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

Source

Paper: GATE 2013 Computer Science and Information Technology (CS)
Question: 20 of 65, printed as CS Q.20
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