GATE CSE 2007 | Question: 81

Question

Consider a machine with a byte addressable main memory of $2^{16}$ bytes. Assume that a direct mapped data cache consisting of $32$ lines of $64$ bytes each is used in the system. A $50$ x $50$ two-dimensional array of bytes is stored in the main memory starting from memory location $1100H$. Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses. 

Which of the following lines of the data cache will be replaced by new blocks in accessing the array for the second time?

• A. line $4$ to line $11$
• B. line $4$ to line $12$
• C. line $0$ to line $7$
• D. line $0$ to line $8$

Comments

For Main Memory, 16 bit byte address is splitted as 10 bit for block and 6 bit for Word.  

Why 10 and 6 bits division?

---

CSHuB

Size of cache line is 64 byte, which can be represented by 6 bits. So 6 out of 16 bits of main memory address is used for word and remaining 10 bits for block.

---

Is my reasoning correct?

main memory has $2^{^{16}}/2^{^{6}} = 2^{^{10}}$ blocks, now first bytes is stored at location 1100H, If we count it in decimal it will be 4352. Now We’ve to check In which block 4352 byte is present in main memory $\therefore$ 4352/64 because each block has 64 elements/bytes. Now it turns out that it is 68^th block. Now in question they have mentioned the direct mapping therefore 68 mod 32 = 4. I think this is why we’re storing at location 4.

Answer 1

Cache Organization:

Staring Address $=1100H = 16^3+16^2+0+0 =4352B$ is the starting address.

We need to find Starting block $=\dfrac{4352\ B}{64\ B}= 68^{th}$ block in main memory from where array start storing elements.

$50\times 50\ B =\text{array size}=50\times \dfrac{50\ B}{64\ B} =39.0625$ blocks needed $\approxeq 40\ blocks$

$\text{68,69,70....107 block}$ we need $=40\text{ blocks}$

Starting block is $68\pmod {32}= 4^{th}$ cache block and after that in sequence they will be accessed.
As shown in below table, line number $4$ to $11$ has been replaced by array in second time

\begin{array}{|c|c|c|} \hline \textbf {Cache Block Number}  &  \textbf{First Cycle }& \textbf{Second cycle} \\\hline \text{0} & \text{96} & \text{} \\\hline \text{1} & \text{97} & \text{} \\\hline \text{2} & \text{98} & \text{}\\\hline\text{3} & \text{99} & \text{}\\\hline\text{4} & \text{68 // 100} & \text{68}\\\hline\text{5} & \text{69 // 101} & \text{}69\\\hline\text{6} & \text{70//102} & \text{70}\\\hline\text{7} & \text{71//103} & \text{71}\\\hline\text{8} & \text{72//104} & \text{72}\\\hline\text{9} & \text{73//105} & \text{73}\\\hline\text{10} & \text{74/106} & \text{74}\\\hline\text{11} & \text{75//107} & \text{75}\\\hline\text{12} & \text{76} & \text{}\\\hline\text{13} & \text{77} & \text{}\\\hline\text{14} & \text{78} & \text{}\\\hline\text{15} & \text{79} & \text{}\\\hline\text{16} & \text{80} & \text{}\\\hline\text{17} & \text{81} & \text{}\\\hline\text{18} & \text{82} & \text{}\\\hline\text{19} & \text{83} & \text{}\\\hline\text{20} & \text{84} & \text{}\\\hline\text{21} & \text{85} & \text{}\\\hline\text{22} & \text{86} & \text{}\\\hline\text{23} & \text{87} & \text{}\\\hline\text{24} & \text{88} & \text{}\\\hline\text{25} & \text{89} & \text{}\\\hline\text{26} & \text{90} & \text{}\\\hline\text{27} & \text{91} & \text{}\\\hline\text{28} & \text{92} & \text{}\\\hline\text{29} & \text{93} & \text{}\\\hline\text{30} & \text{94} & \text{}\\\hline\text{31} & \text{95} & \text{}\\\hline \end{array}

Correct Answer: $A$

Comments

To replace cache block we need to follow LRU algorithm by default? If nothing is given!!

---

@vupadhayayx86

it is given that, Direct Mapping, you should use K mod n method to replace

---

check the answers on this question too https://gateoverflow.in/1273/gate2007-80

Answer 2

Answer is lines 4 to 11 as we start from

1100 H = (0001 0001 0000 0000)_b excluding lower 6 bits for offset, we get 0001 0001 00 bits for cache block which is the 4th block.

Comments

Sir how does we came to know about line 11 and not 12?

---

@arpit_18 For this you had to solve the previous part of this question that asked the number of misses . And if you had solve that, then you would have realized that the starting 8 blocks are the only block which gets replaced and that also twice (first  time in 1st iteration when wrapping back and second time in 2nd iteration again when wrapping back).

---

 

Or , easy way to calculate fast:

64 bytes can be store in 1 cache line and each array element takes a single byte.

And , Total elements = 50*50 = 2500

So , 2500 elements / 64 = 40(after ceil)

40 lines are needed to fully cache the array , but only 32 lines are available in the given cache . So 8 lines have to be replaced . Therefore 4-11.

But this way you won’t get to know how many times did actual replacement happened . If that was asked, then the answer would’ve been 16 because of those 8 lines being replaced twice.

 

---

Got it, Thanks for explanation :)

Answer 3

hexadecimal value of 1100 corresponds to 16^3+16^2 location.

in cache it will start from(16^3+16^2)/64 =68 location onwards.which is 68mod32=4(since direct mapped and cache lines=32)

num.of block required for array=2500/64=40blocks.

but we have only 32 blocks so first 8 block will be replaced by last 8 and we know first 8 is from 4 to 11.

so A is the ans....

Comments

Nice explanation.

Answer 4

A VERY FAST WAS TO CALCULATE++++++++++++++++++

for first access there is 50*50/64 = 39.0625= with ceil 40 misses

now cache has 32 lines already given..

so after getting 32 misses it will overlap with first accessed 8 lines or blocks 

so ultimately for 2nd access we can understand that 8 blocks or lines will be replaced.

now which 8?

0 to 7.     and       4 to 11 are only possible answers..

if given starting address was 0000H or 0x0000 (both same)

answer would have been 0 to 7

so by trial we can know answer is 4 to 11 (A)

 

 

 

 

another way to be sure of it..

staring address 1100H or 0x 1100

i.e. (bit-wise) 0001000100000000

if you have noticed main memory is 16 bits..word offset or block offset 6 , no. of lines 5 so tag is 5

16=5+5+6

00010-00100-000000 so block index is 00100 which is 4

so staring block or line of cache where 1100 H address of main memory is mapped is 4 

so, answer is 4 to 11(A)

Comments

@blackcloud
I think this one is the best possible answer and is easily understandable.