The Gateway to Computer Science Excellence
+18 votes
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$
in CO and Architecture by Veteran (105k points)
edited by | 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.

Source: Arjun sir answer below.
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.

 

 

4 Answers

+41 votes
Best answer
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 by
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

@vupadhayayx86

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

+21 votes

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)
+12 votes
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.
0 votes

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

staring address 1100H or 0x1100

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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,422 answers
195,194 comments
99,829 users