ISRO CSE 2020 | Question: 6

Question

A non-pipelined CPU has $12$ general purpose registers $(R0,R1,R2, \dots ,R12)$. Following operations are supported

• $\begin{array}{ll} \text{ADD Ra, Rb, Rr} & \text{Add Ra to Rb and store the result in Rr} \end{array}$
• $\begin{array}{ll} \text{MUL Ra, Rb, Rr} & \text{Multiply Ra to Rb and store the result in Rr} \end{array}$

$\text{MUL}$ operation takes two clock cycles, $\text{ADD}$ takes one clock cycle.

Calculate minimum number of clock cycles required to compute the value of the expression $XY+XYZ+YZ$. The variable $X,Y,Z$ are initially available in registers $R0,R1$ and $R2$ and contents of these registers must not be modified.

• A. $5$
• B. $6$
• C. $7$
• D. $8$

Comments

option B ) 6 cycles xy+xyz+yz = y(x+xz+z)

---

Ans

Answer 1

Let's first rewrite the expression as: y*(x + z + x*z)

the instructions are:
ADD R0, R1, R3

MUL R0, R1, R4

ADD R3, R4, R3

MUL R2, R3, R3

Since it is a non-pipelined processor it will take 2*2 + 2*1 = 6 cycles

Comments

Is it allowed to optimze the instruction to determine minimum number of clock cycle needed?

---

got it now

---

may be because if it is pipe line then no of stages, dependency all other factors need to be considered so the answer may vary

Answer 2

Given expression is : XY + XYZ + YZ  now rewrite it as  X( Y+ YZ) +YZ;

Take required general purpose registers R0, R1, R2, R3;

from the expression X*( Y+ Y*Z) +Y*Z

1) MUL Y, Z, R0;  multiply y and z and store in R0 ; op(Y*Z)

2) ADD Y, R0, R1    store in R1 : op( Y+YZ)

3) MUL X, R1, R2    multiply X*(Y+Y*Z) and store in R2;

now add R2 with R0 and store in R3 ;

4) ADD R2, R0, R3;

Operation 1) and 3) take 2 clock cycles each and operation 2) and 4) take 1 each

Total  2+1+2+1= 6

 

Answer 3

Ans