17,787 views
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.

### 4 Comments

By reading the language in the question, how did  we get idea that this question is based on pipeline.

As they did not used a single term related to pipelining
Simple just see the timings of different functional units , when F functional units are computing G's it will take 5ns , withinn this 5ns , computation of two more G's can take place.
I think that is where intuition helps.

## 11 Answers

Best answer
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}.$$
by

### 4 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

if somebody is trying to understand through a pipeline diagram,

### 4 Comments

Why F not overlapping in 2 and 3 instructions.
edited

@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.

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)

by

### 4 Comments

great
What is clock cycle here ? Is it 1ns ?
thanks! man for clearing the doubt

This might also work .

### 4 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!
Answer:

46 votes
4 answers
1
14,897 views
64 votes
4 answers
2
57 votes
13 answers
3
70 votes
8 answers
4