Sir, how did you got the range..? I'm not able to understand how you got this (j mod v) * k + (k-1).

Please explain Sir.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+26 votes

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\text{ mod }v) * k \text{ to } (j \text{ mod } v) * k + (k-1) $
- $(j \text{ mod } v) \text{ to } (j \text{ mod } v) + (k-1) $
- $(j \text{ mod } k) \text{ to } (j \text{ mod } k) + (v-1) $
- $(j \text{ mod } k) * v \text{ to } (j \text{ mod } k) * v + (v-1) $

+41 votes

Best answer

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{k } (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.)

(Associativity plays no role in mapping- $k$-way associativity means there are $k$ spaces for a block and hence reduces the chances of replacement.)

+9 votes

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.

+1

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

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 6k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 16

40,976 questions

47,609 answers

146,779 comments

62,342 users