edited by
9,913 views
41 votes
41 votes

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 by

5 Answers

Best answer
59 votes
59 votes
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 by
27 votes
27 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.

15 votes
15 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....
3 votes
3 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 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 by
Answer:

Related questions

22 votes
22 votes
1 answer
2
30 votes
30 votes
2 answers
3
go_editor asked Apr 23, 2016
9,840 views
Consider the following program segment. Here $\text{R1, R2}$ and $\text{R3}$ are the general purpose registers.$$\begin{array}{|l|l|l|c|} \hline & \text {Instruction} & \...
35 votes
35 votes
5 answers
4
go_editor asked Apr 23, 2016
9,356 views
Consider the following program segment. Here $\text{R1, R2}$ and $\text{R3}$ are the general purpose registers.$$\small \begin{array}{|c|l|l||c|} \hline & \text {Instruct...