The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+32 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

  1. $(j\text{ mod }v) * k \text{ to } (j \text{ mod } v) * k + (k-1) $
  2. $(j \text{ mod } v) \text{ to } (j \text{ mod } v) + (k-1) $
  3. $(j \text{ mod } k) \text{ to } (j \text{ mod } k) + (v-1) $
  4. $(j \text{ mod } k) * v \text{ to } (j \text{ mod } k) * v + (v-1) $
asked in CO & Architecture by Veteran (386k points)
retagged by | 3.9k views

2 Answers

+46 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{ 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.)
answered by Veteran (386k points)
edited by
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.
why they multiply it with k in option (a) of range..
That is to get the cache line number. I have added that in the answer. Now, it should be easy.

k is block no and in this example there are 16 cache blocks

Block no. 13 rightly placed between 4 to 7

ur architecture part is damn too good.....
Simple and easy to understand!!
nice explanation @Arjun Sir
clear-cut explanation sir...
+15 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.

jth 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 =8th 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.

answered by Boss (26.2k points)
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
48,720 questions
52,823 answers
68,570 users