Question 40

We need to compute $F(G(X_i))$ for 10 inputs ($1 \le i \le 10$).

• $G$ requires 3 ns on a $U_G$ unit (2 units available: $G_1, G_2$).
• $F$ requires 5 ns on a $U_F$ unit (2 units available: $F_1, F_2$).
• $F(G(X_i))$ can only start after $G(X_i)$ finishes.

Schedule $U_G$ instances (2 parallel units, 3 ns each):

• Inputs $X_1, X_2$: processed from $t = 0$ to $t = 3$. (Ready at $t = 3$)
• Inputs $X_3, X_4$: processed from $t = 3$ to $t = 6$. (Ready at $t = 6$)
• Inputs $X_5, X_6$: processed from $t = 6$ to $t = 9$. (Ready at $t = 9$)
• Inputs $X_7, X_8$: processed from $t = 9$ to $t = 12$. (Ready at $t = 12$)
• Inputs $X_9, X_{10}$: processed from $t = 12$ to $t = 15$. (Ready at $t = 15$)

Schedule $U_F$ instances (2 parallel units, 5 ns each):
Because each $F$ operation takes 5 ns (which is longer than 3 ns), the $U_F$ units are the bottleneck and run continuously without waiting once primed:

• Batch 1 ($X_1, X_2$): Ready at $t = 3$. Processed on $F_1, F_2$ from $t = 3$ to $t = 8$.
• Batch 2 ($X_3, X_4$): Ready at $t = 6 \le 8$. Processed on $F_1, F_2$ from $t = 8$ to $t = 13$.
• Batch 3 ($X_5, X_6$): Ready at $t = 9 \le 13$. Processed on $F_1, F_2$ from $t = 13$ to $t = 18$.
• Batch 4 ($X_7, X_8$): Ready at $t = 12 \le 18$. Processed on $F_1, F_2$ from $t = 18$ to $t = 23$.
• Batch 5 ($X_9, X_{10}$): Ready at $t = 15 \le 23$. Processed on $F_1, F_2$ from $t = 23$ to $t = 28$.

The entire computation completes at $t = 28$ ns.

Therefore, the minimum time required is 28 nanoseconds.