GATE2007-81

3.7k views

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?

1. line $4$ to line $11$
2. line $4$ to line $12$
3. line $0$ to line $7$
4. line $0$ to line $8$

edited
1
If someone like me wondered why first block is in 4th block, this is why.

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.

0

Main memory size = $2^{16}$

Cache Size = 32 x 64 = $2^{11}$

So in direct mapping, $2^{16}$/ $2^{11}$ = 32 blocks will be mapped into a line in the cache.

Staring Address =1100H = 0001 0001 0000 0000) B

For Main Memory, 16 bit byte address is splitted as 10 bit for block and 6 bit for Word.  So 1st 10 bits (0001 0001 00) give address as 68.

For Cache Memory 16 bits are splitted as 5- tag, 5-Block and 6-word.

So 68th block in the main memory is mapped to 68 mod 32 = 4th block in cache memory.

0

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?

0

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.

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$

edited
1
thanx
2
@papesh

memory location 1100H .

how could u say it is in Bytes?

Do u mean as it is byte addressable , it should be in bytes?
4
@srestha

it is given as byte addressable so, I have taken it in bytes.
1
nice explanation thanks a lot
0
To replace cache block we need to follow LRU algorithm by default? If nothing is given!!
1

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

1

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

Answer is lines 4 to 11 as we start from

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

0
Sir how does we came to know about line 11 and not 12?
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....
0
Nice explanation.

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)

edited

Related questions

1
12.3k views
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 ... of the data cache do not change in between the two accesses. How many data misses will occur in total? $48$ $50$ $56$ $59$
Consider a $4$-way set associative cache consisting of $128$ lines with a line size of $64$ words. The CPU generates a $20-bit$ address of a word in main memory. The number of bits in the TAG, LINE and WORD fields are respectively: $9, 6, 5$ $7, 7, 6$ $7, 5, 8$ $9, 5, 6$
Consider the following program segment. Here $\text{R1, R2}$ and $\text{R3}$ ... interrupt occurs during the execution of the instruction INC R3 , what return address will be pushed on to the stack? $1005$ $1020$ $1024$ $1040$
Consider the following program segment. Here $\text{R1, R2}$ and $\text{R3}$ ... Assume that the memory is word addressable. After the execution of this program, the content of memory location $2010$ is: $100$ $101$ $102$ $110$