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

The same concept is used in pipelining. Bottleneck here is $U_F$ as it takes $5\;\text{ns}$ while $U_G$ takes $3\;\text{ns}$ only. We have to do $10$ such calculations and we have $2$ instances of $U_F$ and $U_G$ respectively. So, $U_F$ can be done in $50/2 = 25$ nano seconds. For the start $U_F$ needs to wait for $U_G$ output for $3\;\text{ns}$ and rest all are pipelined and hence no more waiting is needed. So, answer is

$$3 + 25 = 28\;\text{ns}.$$

Comments

no where it is written that pipeline concept is to be used ...?   then cant we do without pipeline..since i was thinking w/o pipelining..!!

---

Very good explanation sir.

---

a simpler word for instances are parellel units

Answer 2

if somebody is trying to understand through a pipeline diagram,

Comments

@Arjun sir I think the above diagram is wrong bcz we are calculating G3 and G4 using two instances of UG, after that, we are calculating G5 and G6 but where we are storing the result of G3 and G4. Also nowhere told that extra buffers are there.

I think this can be the correct diagram.

---

@samarpita Correct. As it is not mentioned when is $F$ reading the value of $G(X_i)$ and there are no mention of extra buffers. 

In fact we need a lot of buffers practically. 

Your diagram seems correct. 

---

I think each column entry is representing 1ns time and not cycle.

Answer 3

Just assume we have two stages in pipeline. They are  G & F taking 3 & 5 seconds.
We have two instances of Uf & Ug.  It is like having dual core processor. We have two pipeline processors.

So we will do  i=1 to 5 in  one processor  &  i= 6 to 10 in another processor.
So they will be done in parallel.

So only focus on i=1 to 5.

In ideal pipeline processor CPI=1 (First instruction takes full time, after it in every cycle one  instruction gets completed unless there is any form of hazard)

So from 5 instructions, first one will take (5+3)= 8ns
For the rest 4 instructions in every 5 ns, 1 instruction will be completed. (Since max(5,3)=5)
5*4= 20ns

So total time taken = 28 ns (ans)

Comments

great

---

What is clock cycle here ? Is it 1ns ?

---

thanks! man for clearing the doubt

Answer 4

This might also work .

Comments

Cleared all the doubts.. Good explanation

---

Thank you providing beautiful answer but i try to one basic mistake is that :-

Don’t use one stage for next instruction until previous instruction leaved that stage and moved to next stage. (I am saying that in case, we have single buffer for stages to store the data). If you suppose multiple buffer for each stage than you can avoid above line.

---

Very well explained..!

---

thanks!