GATE IT 2007 | Question: 37

Question

Consider a Direct Mapped Cache with 8 cache blocks (numbered $0-7$). If the memory block requests are in the following order

$3, 5, 2, 8, 0, 63, 9,16, 20, 17, 25, 18, 30, 24, 2, 63, 5, 82,17, 24.$

Which of the following memory blocks will not be in the cache at the end of the sequence ?

• A. $3$
• B. $18$
• C. $20$
• D. $30$

Comments

i used the mod with " 7 instead of 8 " so carefull felt this may hlp someone 
=> a silly mistake

Answer 1

Answer is (B).

Cache location (memory block) = block req mod number of cache blocks. Since each block has only one location (associativity is $1$) the last mod $8$ request will be in cache (no need of any replacement policy as mapping is direct).

$3, 5, 2, 8, 0, 63, 9, 16, 20, 17, 25, 18, 30, 24, 2, 63, 5, 82, 17, 24$

Block $0- 8$, $ 0, 16, 24, 24$. At end contains $24.$
1- $9, 17, 25, 17.  $
2- $2, 18, 2, 82.$
3- $3$.
4- $20.$
5- $5, 5.$
6- $30.$
7- $63 63.$

So, memory block $18$ is not in cache while $3$, $20$ and $30$ are in cache.

Comments

Doubt: In Direct Mapped cache, the Blocks are replaced when there is a clash, like if in Block-0 we have 8 at first, so when the CPU asks for 16, then 16 will replace 8 in Block-0.
In this question they asked "which block will not be there in the cache at the end of the sequence", so how are we considering multiple block addresses in the same cache block without replacing them?

---

A faster way to get the solution is to access the blocks in reverse order.

---

@Abbas2131 bro the blocks getting replaced . Its just that it’s not explicitly mentioned in question.

Answer 2

in direct mapping function is used to map the data.

(main memory block number) MOD (number of cache memory line)=cache memory line number.

Comments

@ abhishekmehta4u
Small correction required. The second 63th main memory block will be placed in 7th cache line.

Answer 3

….………………………………………………………….