ISRO2018-6

Question

A data driven machine is one that executes an instruction if the needed data is available. The physical ordering of the code listing does not dictate the course of execution. Consider the following pseudo-code:

• A.  Multiply $E$ by $0.5$ to get $F$
• B. Add $A$ and $B$ to get $E$
• C. Add $B$ with $0.5$ to get $D$
• D. Add $E$ and $F$ to get $G$
• E. Add $A$ with $10.5$ to get $C$

Assume $A, B, C $ are already assigned values and the desired output is $G$. Which of the following sequence of execution is valid?

1. B, C, D, A, E
2. C, B, E, A, D
3. A, B, C, D, E
4. E, D, C, B, A

Answer 1

We can give data dependency as follows with each node being the corresponding instruction.

So, instruction A cannot happen before instruction B and also instruction D cannot happen before either instruction A or instruction B. Only option satisfying this is option B. 

Answer 2

the desired output is $G$.

$G$ should be produced at last.

$G$ is produced only by instruction $D$ so $D$ should be at last in sequence.

Hence $b.$ is correct choice.

Answer 3

writing pseudo-code:-

A. F=0.5*E

B.E=A+B

C.D=0.5+B

D.G=E+F

E.C=A+10.5

A,B,C are already assigned by value and data driven going to execute next instruction only if data available.

options:-

A.=>> B,C,D

      B= > E=A+B we can execute it as A,B are already assigned

      C=> D=0.5+B we can execute since B is already assigned.

      D=>> G=E+F we cannot execute it since F=E*0.5 and it is not computed yet.

Option B:-  

    Execute C:- D=B+0.5 , can execute as B is assigned

    Execute B:- E=A+B.can execute as A,B is assigned

     Execute E:- C=A+10.5,can execute as A is assigned

     Execute A:- F=E*0.5, can execute as E is already computed by B.

   Execute D:- G=E+F, can execute as BOTH E,F are already computed

Comments

Ans C)?

---

C is not possible as :-

A=>> F=E+0.5, BUT E IS NOT YET COMPUTED. For B=>> E=A+B it needs to be executed first.

B followed by A is ok.