GATE CS 2021 Set 2 Q.63 (CS Q.53): Instruction Pipelining and Hazards

Consider a pipelined processor with 5 stages, Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Write Back (WB). Each stage of the pipeline, except the EX stage, takes one cycle. Assume that the ID stage merely decodes the instruction and the register read is performed in the EX stage. The EX stage takes one cycle for ADD instruction and two cycles for MUL instruction. Ignore pipeline register latencies.

Consider the following sequence of 8 instructions:

\text{ADD}, \text{MUL}, \text{ADD}, \text{MUL}, \text{ADD}, \text{MUL}, \text{ADD}, \text{MUL}

Assume that every MUL instruction is data-dependent on the ADD instruction just before it and every ADD instruction (except the first ADD) is data-dependent on the MUL instruction just before it. The Speedup is defined as follows:

\text{Speedup} = \frac{\text{Execution time without operand forwarding}}{\text{Execution time with operand forwarding}}

The Speedup achieved in executing the given instruction sequence on the pipelined processor (rounded to 2 decimal places) is ______.

Your answer

Official answer and solution

Accepted answers: 1.87 to 1.88
From: Official GATE 2021 answer key

Solution

Construct cycle-by-cycle pipeline reservation tables for the 8-instruction sequence both with and without operand forwarding.

Pipeline specifications:

Stages: IF (1 cycle), ID (1 cycle), EX (1 cycle for ADD, 2 cycles for MUL), MEM (1 cycle), WB (1 cycle).
ID merely decodes; operand register read takes place in the EX stage.
Instruction sequence: $I_1(\text{ADD}), I_2(\text{MUL}), I_3(\text{ADD}), I_4(\text{MUL}), I_5(\text{ADD}), I_6(\text{MUL}), I_7(\text{ADD}), I_8(\text{MUL})$ .

Case 1: Without operand forwarding:
Since operands are read in the EX stage and results are written back in the WB stage, instruction $I_{k+1}$ can enter its EX stage only after instruction $I_k$ has completed its WB stage.

$I_1$ (ADD): $\text{IF}=1, \text{ID}=2, \text{EX}=3, \text{MEM}=4, \text{WB}=5$ .
$I_2$ (MUL): reads result in EX at cycle 6: $\text{EX}=6, 7, \text{MEM}=8, \text{WB}=9$ .
$I_3$ (ADD): reads result in EX at cycle 10: $\text{EX}=10, \text{MEM}=11, \text{WB}=12$ .
$I_4$ (MUL): $\text{EX}=13, 14, \text{MEM}=15, \text{WB}=16$ .
$I_5$ (ADD): $\text{EX}=17, \text{MEM}=18, \text{WB}=19$ .
$I_6$ (MUL): $\text{EX}=20, 21, \text{MEM}=22, \text{WB}=23$ .
$I_7$ (ADD): $\text{EX}=24, \text{MEM}=25, \text{WB}=26$ .
$I_8$ (MUL): $\text{EX}=27, 28, \text{MEM}=29, \text{WB}=30$ .
Total execution time without operand forwarding is $T_{\text{without}} = 30\text{ cycles}$ .

Case 2: With operand forwarding:
With forwarding, results are forwarded immediately from the end of the execution stage to the beginning of the next instruction's execution stage:

$I_1$ (ADD): $\text{EX}=3$ ; forwards result at end of cycle 3.
$I_2$ (MUL): enters $\text{EX}$ at cycle 4: $\text{EX}=4, 5$ ; forwards result at end of cycle 5.
$I_3$ (ADD): enters $\text{EX}$ at cycle 6: $\text{EX}=6$ ; forwards result at end of cycle 6.
$I_4$ (MUL): enters $\text{EX}$ at cycle 7: $\text{EX}=7, 8$ ; forwards at end of cycle 8.
$I_5$ (ADD): enters $\text{EX}$ at cycle 9: $\text{EX}=9$ ; forwards at end of cycle 9.
$I_6$ (MUL): enters $\text{EX}$ at cycle 10: $\text{EX}=10, 11$ ; forwards at end of cycle 11.
$I_7$ (ADD): enters $\text{EX}$ at cycle 12: $\text{EX}=12$ ; forwards at end of cycle 12.
$I_8$ (MUL): enters $\text{EX}$ at cycle 13: $\text{EX}=13, 14, \text{MEM}=15, \text{WB}=16$ .
Total execution time with operand forwarding is $T_{\text{with}} = 16\text{ cycles}$ .

Calculate the speedup:

\text{Speedup} = \frac{T_{\text{without}}}{T_{\text{with}}} = \frac{30}{16} = 1.875

Rounding to 2 decimal places yields $1.88$ (official key range: 1.87 to 1.88).

Final answer

1.88

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 63 of 65, printed as CS Q.53
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source