GATE CS 2016 Set 2 Q30 — ALU, Data-path and Control Unit

We can model this computation as a two-stage pipeline for each of the 10 inputs $X_i$ ($1 \le i \le 10$):

• Stage 1 ($G$): Executed by $U_G$ (takes $3\text{ ns}$). We have $2$ instances of $U_G$.
• Stage 2 ($F$): Executed by $U_F$ (takes $5\text{ ns}$). We have $2$ instances of $U_F$.

Since we have $2$ instances of $U_G$, we can process the $G$ operations in pairs of two:

• $G(X_1), G(X_2)$ complete at $t = 3\text{ ns}$
• $G(X_3), G(X_4)$ complete at $t = 6\text{ ns}$
• $G(X_5), G(X_6)$ complete at $t = 9\text{ ns}$
• $G(X_7), G(X_8)$ complete at $t = 12\text{ ns}$
• $G(X_9), G(X_{10})$ complete at $t = 15\text{ ns}$

Now, we schedule the $F$ operations on the $2$ instances of $U_F$ as soon as their inputs from $G$ are ready:

• At $t = 3\text{ ns}$, $G(X_1)$ and $G(X_2)$ are ready. $F(G(X_1))$ and $F(G(X_2))$ run from $t = 3$ to $t = 8\text{ ns}$.
• At $t = 8\text{ ns}$, $F(G(X_3))$ and $F(G(X_4))$ start (since $G(X_3), G(X_4)$ were ready at $t = 6$) and run until $t = 13\text{ ns}$.
• At $t = 13\text{ ns}$, $F(G(X_5))$ and $F(G(X_6))$ start and run until $t = 18\text{ ns}$.
• At $t = 18\text{ ns}$, $F(G(X_7))$ and $F(G(X_8))$ start and run until $t = 23\text{ ns}$.
• At $t = 23\text{ ns}$, $F(G(X_9))$ and $F(G(X_{10}))$ start and run until $t = 28\text{ ns}$.

Thus, the minimum time required to complete all computations is 28 nanoseconds.