GATE CSE 2013 | Question: 20

Question

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

• A. $(j\text{ mod }v) * k \text{ to } (j \text{ mod } v) * k + (k-1) $
• B. $(j \text{ mod } v) \text{ to } (j \text{ mod } v) + (k-1) $
• C. $(j \text{ mod } k) \text{ to } (j \text{ mod } k) + (v-1) $
• D. $(j \text{ mod } k) * v \text{ to } (j \text{ mod } k) * v + (v-1) $

Comments

“one after the other” is the keyword here, that is why multiplication by k is necessary

---

So till (j mod v)  set number how many times k blocks we have covered (i.e nothing but the total blocks before (j mod v) set ) till the end of (j mod v) set (i.e total blocks in (j mod v) set = [(j mod v)*k + k-1] ) is correct answer!

---

The real obstacle for this problem is just understanding the question,

“each of which consists of lines 

Lines of a set are placed in sequence one after another.

cache lines from

---

 Try to solve By Drawing diagram like this it will be easy to understand this questionm

https://youtu.be/Izu3CHW4NbQ?si=oQ5AcYlr10kXb1Qa

Answer 1

Number of sets in cache $= v$.

The question gives a sequencing for the cache lines. For set $0$, the cache lines are numbered $0, 1, .., k-1$. Now for set $1$, the cache lines are numbered $k, k+1,... k+k-1$ and so on.

So, main memory block $j$ will be mapped to set $(j \ \text{mod} \ v)$, which will be any one of the cache lines from $(j \ \text{mod  } v) * k \ \text{ to } (j \ \text{mod  } v) * k + (k-1)$.
(Associativity plays no role in mapping- $k$-way associativity means there are $k$ spaces for a block and hence reduces the chances of replacement.)

Correct Answer: $A$

Comments

(j mod v) gives only the set number, to find cache line we multiply set number with number of lines in each set, ie (j mod v)∗k

---

Why the statement "The lines in set s are sequenced before the lines in set (s+1)" is not considered ?

---

@Anand patel “Why the statement "The lines in set s are sequenced before the lines in set (s+1)" is not considered ?” because it is the normal way in which we enter memory blocks in set associative cache and line set s is obvious to be sequenced before lines in set s+1.

Answer 2

set number	block
0	0
0	1
0	2
0	3
1	0
1	1
1	2
1	3
2	0
2	1
2	2
2	3
3	0
3	1
3	2
3	3

In above exaple 16 blocks are there. and 4 sets.Each set contains 4 blocks.

Suppose memory address are like this : 0,4,8,14 these all can fit into set 0 in any order where it get place but mostly FIFO.

j^th is memory block will be placed at j mod v = set number 

Let j=14 the main memory block. 14 mod 4 = 2 we are at set number 2  but to read at set to we need to pass set0 and set1 each having k size .

so 2 * k =2*4 gives =8^th cache block that is starting block of 3rd cache set.But each cache also having k way set associativy that means more k-1 block can be placed in that set.

so (j mod v) * k + (j mod v)*k +(k-1) should be the ans.

Comments

Forget everything for a while and just see

The cache memory has k lines and v sets

Sets are built using lines.

Now there  are number of blocks but we shall consider block no j now

For mapping we know

To map block no J to set no V we use (j mod v)

Now we have number of lines as k

So multiply it by k

i. e (j mod v) *k

 

Now range part:

(J mod V) *K

And we  add k-1 for the numbee of lines - 1

So total is (j mod v) *k +k-1

---

each set has k lines but you have assumed cache has k lines

Answer 3

Think of it as two-dimensional array, $A[v][k]$ with $v$ rows and $k$ columns since each set $i$ has exactly $k$ blocks in it.

A block $j$ will map to set $j\%v$ and any of the blocks $0$ through $k-1$ of that set.

Thus, you need the position of $A[j\%v][0]$ and $A[j\%v][k-1]$ in memory. Using simple 2D array address translation, these come out to be $(j\%v)*k$ and $(j\%v)*k+(k-1)$.

Answer: Option (A).

Answer 4

..….......…..….…..….….…...……………………................….…