retagged by
22,393 views
99 votes
99 votes
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.
retagged by

12 Answers

Best answer
104 votes
104 votes
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}.$$
edited by
219 votes
219 votes

if somebody is trying to understand through a pipeline diagram,

edited by
68 votes
68 votes

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)

22 votes
22 votes

This might also work .

Answer:

Related questions

50 votes
50 votes
4 answers
1
Akash Kanase asked Feb 12, 2016
17,629 views
The width of the physical address on a machine is $40$ bits. The width of the tag field in a $512$ KB $8$-way set associative cache is ________ bits.