The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
2.7k views

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 (342k points)
retagged by | 2.7k views

2 Answers

+38 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 mod v), which will be any one of the cache lines from (j mod v) * k to (j 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 (342k points)
edited by
0

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. 


 

 

0
why they multiply it with k in option (a) of range..
0
That is to get the cache line number. I have added that in the answer. Now, it should be easy.
+39

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

Block no. 13 rightly placed between 4 to 7

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

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 (25.7k points)
Answer:

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

35,506 questions
42,827 answers
121,678 comments
42,181 users