Suppose the functions \(F\) and \(G\) can be computed in 5 and 3 nanoseconds…
2016
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 ≤ i ≤ 10\). Ignoring all other delays, the minimum time required to complete this computation is _____________ nanoseconds.
Answer: 28 — Key insight: identify the bottleneck stage and use total work divided across identical functional units. Compute total work for F: 10 inputs × 5 ns = 50 ns.…
Attempted by 23 students.
Show answer & explanation
Correct answer: 28
Key insight: identify the bottleneck stage and use total work divided across identical functional units.
Compute total work for F: 10 inputs × 5 ns = 50 ns. With two F units this requires at least 50/2 = 25 ns of continuous F processing.
Compute total work for G: 10 inputs × 3 ns = 30 ns. With two G units this requires at least 30/2 = 15 ns to produce all G results.
The first F can only start after the first G finishes (3 ns), so the earliest completion of all F work is 3 ns + 25 ns = 28 ns.
Since G can finish producing all inputs in 15 ns (which is less than 28 ns), it does not limit the overall schedule. Therefore the minimum time required is 28 nanoseconds.
A video solution is available for this question — log in and enroll to watch it.