Consider a pipelined processor with 5 stages, (formula) , (formula) ,… — GATE CS 2021 Set 2 Q53

Consider a pipelined processor with

5

stages,

\text{Instruction Fetch} (\textsf{IF})

\text{Instruction Decode} \textsf{(ID)}

\text{Execute } \textsf{(EX)}

\text{Memory Access } \textsf{(MEM)}

, and

\text{Write Back } \textsf{(WB)}

. Each stage of the pipeline, except the

\textsf{EX}

stage, takes one cycle. Assume that the

\textsf{ID}

stage merely decodes the instruction and the register read is performed in the

\textsf{EX}

stage. The

\textsf{EX}

stage takes one cycle for

\textsf{ADD}

instruction and two cycles for

\textsf{MUL}

instruction. Ignore pipeline register latencies.

Consider the following sequence of

8

instructions:

\textsf{ADD, MUL, ADD, MUL, ADD, MUL, ADD, MUL}

Assume that every

\textsf{MUL}

instruction is data-dependent on the

\textsf{ADD}

instruction just before it and every

\textsf{ADD}

instruction (except the first

\textsf{ADD}

) is data-dependent on the

\textsf{MUL}

instruction just before it. The

\textit{speedup}

defined as follows.

\textit{Speedup} = \dfrac{\text{Execution time without operand forwarding}}{\text{Execution time with operand forearding}}

The

\textit{Speedup}

achieved in executing the given instruction sequence on the pipelined processor (rounded to

2

decimal places) is _____________

View worked solution

Answer: 1.87 : 1.88

To find the speedup, we calculate the total execution cycles for both cases: without operand forwarding and with operand forwarding.

1. Without Operand Forwarding

Since the register read is performed in the $\textsf{EX}$ stage and register write is in the $\textsf{WB}$ stage, a dependent instruction can only enter its $\textsf{EX}$ stage after the preceding instruction completes its $\textsf{WB}$ stage.

$I_1$ (ADD): $\textsf{EX}$ in cycle 3, $\textsf{WB}$ in cycle 5.
$I_2$ (MUL): $\textsf{EX}$ starts in cycle 6 (after $I_1$ completes $\textsf{WB}$ in cycle 5). $\textsf{EX}$ takes 2 cycles (6, 7), $\textsf{WB}$ in cycle 9.
$I_3$ (ADD): $\textsf{EX}$ starts in cycle 10, $\textsf{WB}$ in cycle 12.
$I_4$ (MUL): $\textsf{EX}$ in cycles 13–14, $\textsf{WB}$ in cycle 16.
$I_5$ (ADD): $\textsf{EX}$ in cycle 17, $\textsf{WB}$ in cycle 19.
$I_6$ (MUL): $\textsf{EX}$ in cycles 20–21, $\textsf{WB}$ in cycle 23.
$I_7$ (ADD): $\textsf{EX}$ in cycle 24, $\textsf{WB}$ in cycle 26.
$I_8$ (MUL): $\textsf{EX}$ in cycles 27–28, $\textsf{MEM}$ in cycle 29, $\textsf{WB}$ in cycle 30.

Total execution time without forwarding = 30 cycles.

2. With Operand Forwarding

With forwarding, the result computed at the end of the $\textsf{EX}$ stage of an instruction is directly forwarded to the start of the $\textsf{EX}$ stage of the next dependent instruction.

$I_1$ (ADD): $\textsf{EX}$ in cycle 3. Result forwarded at the end of cycle 3.
$I_2$ (MUL): $\textsf{EX}$ in cycles 4–5. Result forwarded at the end of cycle 5.
$I_3$ (ADD): $\textsf{EX}$ in cycle 6. Result forwarded at the end of cycle 6.
$I_4$ (MUL): $\textsf{EX}$ in cycles 7–8. Result forwarded at the end of cycle 8.
$I_5$ (ADD): $\textsf{EX}$ in cycle 9. Result forwarded at the end of cycle 9.
$I_6$ (MUL): $\textsf{EX}$ in cycles 10–11. Result forwarded at the end of cycle 11.
$I_7$ (ADD): $\textsf{EX}$ in cycle 12. Result forwarded at the end of cycle 12.
$I_8$ (MUL): $\textsf{EX}$ in cycles 13–14, $\textsf{MEM}$ in cycle 15, $\textsf{WB}$ in cycle 16.

Total execution time with forwarding = 16 cycles.

3. Speedup Calculation

\text{Speedup} = \frac{\text{Execution time without forwarding}}{\text{Execution time with forwarding}} = \frac{30}{16} = 1.875

Rounding to two decimal places, we get 1.88 (or 1.87 depending on the rounding method).

Free practice · Your answers on this page are not saved.

GATE CS 2021 Set 2 Q53 — Instruction Pipelining

1. Without Operand Forwarding

2. With Operand Forwarding

3. Speedup Calculation

Related questions