# GATE2004-65

5.7k views

Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently used (LRU) scheme. The number of cache misses for the following sequence of block addresses is:

$8, 12, 0, 12, 8$.

1. $2$
2. $3$
3. $4$
4. $5$

edited
1
what will be the number of conflict cache miss ? is it 2?
1
@akshat sharma...No, total cache miss is 4 but conflict cache miss is only one for the last element 8.
0
isn't '0' also a conflict miss?

We have $4$ blocks and $2$ blocks in a set

$\implies$ there are $2$ sets. So blocks will go to sets as follows:
$$\begin{array}{|c|c|} \hline \textbf {Set Number} & \textbf{Block Number} \\\hline \text{0} & \text{0,8,12} \\\hline\text{1} & \\\hline \end{array}$$
Since the lowest bit of block address is used for indexing into the set, so $8, 12$ and $0$ first miss in cache with $0$ replacing $8$ (there are two slots in each set due to $2-\text{way}$ set) and then $12$ hits in cache and $8$ again misses. So, totally $4$ misses.

Correct Answer: $C$

edited
1
How can tag bits be the lowest most bits ? Tag bits are the upper most bits. Lower most bits is the index. Here as there are only 2 sets, index bit = 1. isn't it ?
1
Yes. You are right. I have corrected it. It's index or set bits and not tag bits. Tag bits are the upper bits and relevant to identify which block is currently present in a cache block. In this question this part is not asked and we just need to identify the 1 index bit.
2
Very Nice explanation...
1
Sir, did you use LRU into it?
0

@Arjun can you please tell me why is no element placed in SET 1

0
Because of how a set-associative cache operates. You place a block M in set M mod S, where S is the number of sets. All of the main memory blocks here are even, so even mod 2 = 0.
1
 Set No. Block NO. misses/hits 1 0 $\require {cancel} \cancel {8}_ {\text{miss}}, \cancel {0}_{\text {miss}}, \cancel{8}_{\text {miss}}$ 1 2 0 $\cancel{12}_{_{\text{miss}}}, 12_{\text{hit}}$ 1

@Arjun Sir

Is this way of visualizing the que correct?

@ankitgupta.1729

Bhai can you please check this procedure. Is this correct?

1
@JEET u have to map only on set no. 1. ur content of "set no. 2 block no. 0" should be placed on "set no. 1 block no. 1". As there is 2-way set associative, so, each set can accommodate 2 block.
1
So, two blocks are already there in each set.

Didn't get whay you are pointing to?
4

numbering of blocks and sets each should start from 0.

so we will have set 0 and set 1 i.e. 2 sets and in each set we have 2 blocks.

And in set associative cache we do mod S and not mod B to select a line of cache where we want to place the block.

Like for eg :- 12 mod 2 = 0 so we place this block in set 0. Now if a line is empty in that set then place 12 on that line else use page replacement policy

 Set No. Block NO. or line number misses/hits 0 0 $\require {cancel} \cancel {8}_ {\text{miss}}, \cancel {0}_{\text {miss}}, 8$ 1 $12$ 1 2 3

0

@Satbir

Didn't get. So, what's the mistake in my observation?

1

Cache is 2-way associative, and has total 4 blocks.

So, no. of sets $\frac{4}{2} = 2^1 \implies 1$ bit for deciding which set each block belongs to, which by standard is the least significant bit, which is $0$ for $\{0, 8, 12\}$

Each set can contain 2 blocks.

So, @`JEET set 2 should not contain anything.

2 way set associative

4 blocks

Set size = # of blocks / # of sets

= 4/2 = 2

So Block addresses will be divided by 2 ... On the basis of their remainder we will place those blocks in the sets .. applying LRU approach ... answer will be 4 ..

Option C is the correct answer

total 4 cache misses are there.

## Related questions

1
7.9k views
Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$ \begin{array}{|l|l|c|} \hline \text {Instruction} & \text{Operation }& \text{Instruction size (in Words)} \\\hline \text{MOV $R_1,5000$} & \text{$R1$} \ ... text{2 clock cycles }\\\hline \end{array} The total number of clock cycles required to execute the program is $29$ $24$ $23$ $20$
A 4-stage pipeline has the stage delays as $150$, $120$, $160$ and $140$ $nanoseconds$, respectively. Registers that are used between the stages have a delay of $5$ $nanoseconds$ each. Assuming constant clocking rate, the total time taken to process $1000$ data items ... will be: $\text{120.4 microseconds}$ $\text{160.5 microseconds}$ $\text{165.5 microseconds}$ $\text{590.0 microseconds}$
A hard disk with a transfer rate of $10$ Mbytes/second is constantly transferring data to memory using DMA. The processor runs at $600$ MHz, and takes $300$ and $900$ clock cycles to initiate and complete DMA transfer respectively. If the size of the transfer is $20$ Kbytes, what is the percentage of processor time consumed for the transfer operation? $5.0 \%$ $1.0\%$ $0.5\%$ $0.1\%$
The microinstructions stored in the control memory of a processor have a width of $26$ bits. Each microinstruction is divided into three fields: a micro-operation field of $13$ bits, a next address field $(X),$ and a MUX select field $(Y).$ There are $8$ status bits in the input of the MUX. ... the size of the control memory in number of words? $10, 3, 1024$ $8, 5, 256$ $5, 8, 2048$ $10, 3, 512$