GATE CSE 2016 Set 2 | Question: 30

Question

Suppose the functions $F$ and $G$ can be computed in $5$ and $3$ nanoseconds by functional units $U_{F}$ and $U_{G}$, respectively. Given two instances of $U_{F}$ and two instances of $U_{G}$, it is required to implement the computation $F(G(X_{i}))$ for $1 \leq i \leq 10$. Ignoring all other delays, the minimum time required to complete this computation is ____________ nanoseconds.

Comments

I think that is where intuition helps.

---

@Vijay Kusumakar here we not need to apply pipline to get ans just think that there are 2 instances of G so that to execute 10 instr we willl need max $15 ← (3* (10/2))$

now when we execute 10 instr with 2 instances of F then it will take $25 ← (5*(10/2))$

But here we have to think that both F and G will be calculated simultaneously so But firstly G will exexute 3ms to genrate 2 instance of output of G so that the F can start its working so 

time needed $=3+ max(12ms + 25ms) = 3+25=28$

---

@Ray Tomlinson first actually useful comment by you :)

Answer 1

For i=1, G() will take 3 ns and after that only F() will start and will take 5 ns. --> total 8

Now, while F() (for i=1) is executing G() (for i=2) can be computed --> total 8+5

Similarly for every F() for i G() can be calculate for i+1, therefore only at the start we need 3ns .

So total will be 10*5/2 + 3 = 28

Comments

Sir Could please explain why you are dividing 50 by 2.

Please,I am confusing.

---

@sambslvarao this is because we have two instances of F and G, if there were only one instance then it would be 10*5+3=53

---

@shikhar__deep05 I did not get how did you solve plz could u elaborate?

---

solution is not clear to me!

Answer 2

We have to do 10 calculations of U and G as the loop runs from i = 1 to 10.
Since we have 2 instances of UF and UG, each unit need to be run 5 times to complete the execution.
Suppose computation starts at time 0, which means G starts at 0 and F starts at 3rd second since F is dependent on G and G finishes computing first element at 3rd second.
Computation of F ten times using two UF units can be done in 5*10/2 = 25ns.
For the start UF needs to wait for UG output for 3ns and rest all are pipelined and hence no more wait.
So, answer is 3 + 25 = 28ns

Comments

All your answers will be deleted for doing copying. Not sure what you are trying to achieve by this.

Answer 3

Unit(G1)	Unit(G2)	Unit(F1)	Unit(F2)	TIME = MAX(Unit G,Unit F)
$I_{2}$	$I_{1}$	_____	_____	Here it will be 3 because only Time of Unit G will be considered
$I_{4}$	$I_{3}$	$I_{2}$	$I_{1}$	Since Unit F takes more time, so Unit G will finish it’s execution before Unit F. Total time = 5
$I_{6}$	$I_{5}$	$I_{4}$	$I_{3}$	Total time = 5
$I_{8}$	$I_{7}$	$I_{6}$	$I_{7}$	Total time = 5
$I_{10}$	$I_{9}$	$I_{8}$	$I_{7}$	Total time = 5
_____	_____	$I_{10}$	$I_{9}$	Here it will be 5 because only Time of Unit F will be considered.

 

Given two instances of Unit F and two instances of Unit G

We can run two instructions $I_{m}, I_{n}$ simultaneously in $U_{m}, U_{n}$ respectively.

Total time = 3 + 5*5 = 3 + 35 = 28ns

 

Answer 4

1. Initial Computation of G(X1) and G(X2):

   • Both instances of UG can compute G(X1) and G(X2) simultaneously in 3 nanoseconds.

2. Pipelined Computation of F(G(Xi)):

   • After 3 nanoseconds, UF1 and UF2 can start computing F(G(X1)) and F(G(X2)), respectively.
   • While UF1 and UF2 are busy, UG1 and UG2 can compute G(X3) and G(X4), completing in another 3 nanoseconds.
   • This pattern continues, with UF1 and UF2 processing the results of G operations, and UG1 and UG2 working on subsequent G(Xi) calculations.

3. Total Time:

   • The first 4 computations (F(G(X1)) to F(G(X4))) take 5 nanoseconds each (the time for F), for a total of 20 nanoseconds.
   • The remaining 6 computations (F(G(X5)) to F(G(X10))) can be completed in 6 * 3 = 18 nanoseconds, as the F units are always busy.
   • Therefore, the total time is 20 nanoseconds (for the first 4) + 3 nanoseconds (initial G computations) + 5 nanoseconds (for the last F computation) = 28 nanoseconds.