The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 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 (346k points)
retagged by | 2.5k views

2 Answers

+35 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 (346k 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!!
+7 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 Veteran (26.9k points)

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

33,593 questions
40,128 answers
38,389 users