GATE CSE 2007 | Question: 71

Question

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} & \text{Operation }& \text{Instruction Size} \\ & & & \text{(no. of words)} \\\hline & \text{MOV R1,(3000)} & \text{R1} \leftarrow \text{M[3000]} & \text{$2$} \\\hline \text{LOOP:}& \text{MOV R2,(R3)} & \text{R2} \leftarrow \text{M[R3]} & \text{$1$} \\\hline & \text{ADD R2,R1} & \text{R2} \leftarrow \text{R1 + R2} & \text{$1$} \\\hline & \text{MOV (R3),R2} & \text{M[R3]} \leftarrow \text{R2} & \text{$1$} \\\hline& \text{INC R3} & \text{R3} \leftarrow \text{R3 + 1} & \text{$1$} \\\hline & \text{DEC R1} & \text{R1} \leftarrow \text{R1 – 1} & \text{$1$} \\\hline& \text{BNZ LOOP} & \text{Branch on not zero} & \text{$2$} \\\hline & \text{HALT} & \text{Stop} & \text{$1$} \\\hline\end{array}$$

Assume that the content of memory location $3000$ is $10$ and the content of the register $\text{R3}$ is $2000$. The content of each of the memory locations from $2000$ to $2010$ is $100$. The program is loaded from the memory location $1000$. All the numbers are in decimal.

Assume that the memory is word addressable. The number of memory references for accessing the data in executing the program completely is

• A. $10$
• B. $11$
• C. $20$
• D. $21$

Comments

$INC/DEC$ affects all the flags except carry flag.

$MOV$ does not affect any flags.

$ADD/SUB$ affects all the flags.

---

since word addressable , instruction #1 is 2 words wouldn't it be 2 + 20 => 22  ?

---

simillar branch questions :- 
CO & Architecture: GATE CSE 2007 | Question: 72
CO & Architecture: GATE CSE 2007 | Question: 73

Answer 1

Loop is executed $10$ times and there are two memory reference in the loop (each MOV
is loading $1$ word, so $1$ memory reference for each MOV inside the loop). So number
of memory reference inside loop is

$2 \text{(MOV)}\times 10\text{ (times iteration)}\times 1\text{(1 word access/ MOV)}
=20\text{ memory accesses.}$

One memory access is outside the loop for the first instruction

MOV R1, (3000)

So, totally $20+1 = 21$

Correct Answer: $D$

Comments

@VS you are right. @akash.dinkar12 accessing data is different from updating data. Just considering the loop, here, we are “accessing” data in the first MOV instruction only. In the second MOV instruction we are accessing register and not the memory for, again, “accessing” data. If we think this way then the answer would be 11. 

---

@Arjun Sir, in the question, they have clearly mentioned “number of memory references for accessing the data...”

So, as we can see in the 4^th instruction, it’s not accessing any data. This instruction just stores whatever is inside R2 to the corresponding memory location.

Don’t you think the question is a little ambiguous? Because if we calculate the answer this way, we will get a total of 11 as the answer, which also happens to be one of the options given. So, in exam, how are we supposed to know what exactly should be the answer – 11 or 21? Or is it just luck that comes into play while answering such questions? :) 

---

Here we have to give mem acess only so we are not including Instruction fetches. So 2 words doesn't matter here matters only this that it requires 1 mem acess . Instruction size comes into play mostly during fetches.

U can solve this question for better understanding. CO & Architecture: GATE CSE 2004 | Question: 64

 

Answer 2

Ist memory reference R1←M[3000] and then in the loop which runs for 10 times, because the content of memory location 3000 is 10 given in question and loop will run 10 times as

R2← M[R3]

M[R3] ←R2

There are two memory reference every iteration

10*2=20

So total memory access will be 21

Comments

@shipra tressa
R1 is 10 initially and then r1 is decremented by 1 and BNZ will not return true till the immediate value isn't 0; so 10,9,8 till 0

 

---

@Aari did your doubt got resolved?
I have same doubt after reading your comment:o

---

i have a silly doubt here, in BNZ LOOP what are we comparing against 0(how are we comparing R1 against 0, it is not mentioned...)

Answer 3

The number of memory references for accessing the data in executing the program completely is :-

https://gateoverflow.in/1269/gate2007-71?show=224234#c224234

https://gateoverflow.in/1269/gate2007-71?show=103284#c103284

$M[3000]=10\ | \ R3=2000\ |\ M[2000]\ to\ M[2010]=100$

 

$R1=10(M_{ref})||R2=100(M_{ref})||R2=110||M[2000]=110(M_{ref})||R3=2001||R1=9||\Rightarrow3 (M_{ref})$

$R2=100(M_{ref})||R2=109||M[2001]=109(M_{ref})||R3=2002||R1=8||\Rightarrow2 (M_{ref})$

$R2=100(M_{ref})||R2=108||M[2002]=108(M_{ref})||R3=2003||R1=7||\Rightarrow2 (M_{ref})$

$R2=100(M_{ref})||R2=107||M[2003]=107(M_{ref})||R3=2004||R1=6||\Rightarrow2 (M_{ref})$

$R2=100(M_{ref})||R2=106||M[2004]=106(M_{ref})||R3=2005||R1=5||\Rightarrow2 (M_{ref})$

$R2=100(M_{ref})||R2=105||M[2005]=105(M_{ref})||R3=2006||R1=4||\Rightarrow2 (M_{ref})$

$R2=100(M_{ref})||R2=104||M[2006]=104(M_{ref})||R3=2007||R1=3||\Rightarrow2 (M_{ref})$

$R2=100(M_{ref})||R2=103||M[2007]=103(M_{ref})||R3=2008||R1=2||\Rightarrow2 (M_{ref})$

$R2=100(M_{ref})||R2=102||M[2008]=102(M_{ref})||R3=2009||R1=1||\Rightarrow2 (M_{ref})$

$R2=100(M_{ref})||R2=101||M[2009]=101(M_{ref})||R3=2010||R1=0||\Rightarrow2 (M_{ref})$

Total $\Rightarrow 21 (M_{ref})$

Answer 4

Option D is correct 

before loop there is 1 memory access

Loop is accessed 10 times as Branch if not zero is checked 10 times, and each time, R1 is getting decremented.

in 1 loop there are 2 memory accesses

total 

1+ 10(2) = 21

 

one could also ask what will be the memory after execution,

2010 will be stored from 2000 memory location to 2009 memory location

Answer 5

Answer is 21

Answer 6

solution for this question : https://youtu.be/4PNjSGDRnjc?si=xY_uMDY7kHG9TCuV