what will be the number of conflict cache miss ? is it 2?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+9 votes

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

- $2$
- $3$
- $4$
- $5$

+16 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 ?

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

49,845 questions

54,783 answers

189,422 comments

80,415 users