The Gateway to Computer Science Excellence

+19 votes

Best answer

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$

$\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$

+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.

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.

0

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 |

Is this way of visualizing the que correct?

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

0

@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.

+3

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

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,257 answers

198,084 comments

104,733 users