Instruction execution in a processor is divided into 5 stages, Instruction…
2017
Instruction execution in a processor is divided into 5 stages, Instruction Fetch (IF), Instruction Decode (ID), Operand fetch (OF), Execute (EX), and Write Back (WB). These stages take 5, 4, 20, 10 and 3 nanoseconds (ns) respectively. A pipelined implementation of the processor requires buffering between each pair of consecutive stages with a delay of 2 ns. Two pipelined implementation of the processor are contemplated:
I. a naive pipeline implementation (NP) with 5 stages and
II. an efficient pipeline (EP) where the OF stage is divided into stages OF1 and OF2 with execution times of 12 ns and 8 ns respectively.
The speedup (correct to two decimal places) achieved by EP over NP in executing 20 independent instructions with no hazards is _________ .
Answer: 1.5 to 1.51 — Concept. In a synchronous pipeline every stage is driven by one common clock, so the clock period must be long enough for the slowest stage plus the buffer…
Attempted by 109 students.
Show answer & explanation
Correct answer: 1.5 to 1.51
Concept. In a synchronous pipeline every stage is driven by one common clock, so the clock period must be long enough for the slowest stage plus the buffer (register) delay that separates consecutive stages: clock period = max(stage delay) + buffer delay. A pipeline of depth k then completes n independent instructions in (k + n − 1) clock periods — k periods to push the first instruction through, and one more period for each of the remaining n − 1 instructions. Speedup of one design over another is simply the ratio of their total execution times, which is why splitting the slowest stage can win even though it makes the pipeline one stage deeper.
Application to this problem. The stage times are IF = 5, ID = 4, OF = 20, EX = 10, WB = 3 (all in ns), the buffer delay is 2 ns, and n = 20 instructions with no hazards.
Design | Stage delays (ns) | Slowest stage | Clock period | Depth k |
|---|---|---|---|---|
Naive pipeline (NP) | 5, 4, 20, 10, 3 | 20 ns | 20 + 2 = 22 ns | 5 |
Efficient pipeline (EP) | 5, 4, 12, 8, 10, 3 | 12 ns | 12 + 2 = 14 ns | 6 |
NP clock period: the largest of 5, 4, 20, 10 and 3 ns is the OF stage at 20 ns; adding the 2 ns buffer delay gives a clock period of 22 ns.
NP total time: NP has depth k = 5, so it needs 5 + 20 − 1 = 24 clock periods, i.e. 24 × 22 = 528 ns.
EP clock period: splitting the 20 ns OF stage into OF1 = 12 ns and OF2 = 8 ns leaves stage delays 5, 4, 12, 8, 10, 3 ns, so the slowest stage is now 12 ns and the clock period drops to 12 + 2 = 14 ns.
EP total time: EP has depth k = 6, so it needs 6 + 20 − 1 = 25 clock periods, i.e. 25 × 14 = 350 ns.
Speedup of EP over NP = time on NP / time on EP = 528 / 350 = 1.5085714…
Cross-check. The clock period improves by a factor 22 / 14 = 1.571, but EP pays for the extra stage with one additional clock period (25 instead of 24), so the realised speedup must sit a little below 1.571 — and 1.5086 does. Note also that splitting the slowest stage unevenly (12 and 8 rather than 10 and 10) is what limits the gain: the new bottleneck is 12 ns, not 10 ns.
Reporting to two decimal places. The exact value is 528 / 350 = 1.5085714… , so rounding to two decimals gives 1.51 while truncating (chopping) at the second decimal gives 1.50. Numerical-answer questions are marked against a published band rather than a single number, and the official key for this question accepts 1.50 to 1.51 — both entries are correct. The safe habit for such questions is to carry the exact fraction to the very end and only then convert; when the third decimal makes rounding and truncation differ, either form lies inside the accepted band.
Speedup = 528 / 350 ≈ 1.51 (exactly 1.5086; 1.50 is equally accepted).
A video solution is available for this question — log in and enroll to watch it.