2.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 | 2.7k views
0
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.

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$
by Boss (25.5k points)
edited
0
thanx
+1
@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?
+3
@srestha

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

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

0

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.

by Veteran (424k points)
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....
by Boss (11k points)
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 overlao 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..

i.e. (bitwise) 0001000100000000

if you have noticed main memory is 16 bits..word offset or block 0ffset 6 , no. of lines 5 so tah 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 first block of main memory is mapped is 4

so, answer is 4 to 11(A)

by (257 points)