GATE CS 2015 Set 2 Q.54 (CS Q.44): Instruction Pipelining and Hazards

Consider the sequence of machine instructions given below:

MUL R5, R0, R1
DIV R6, R2, R3
ADD R7, R5, R6
SUB R8, R7, R4

In the above sequence, R0 to R8 are general purpose registers. In the instructions shown, the first register stores the result of the operation performed on the second and the third registers. This sequence of instructions is to be executed in a pipelined instruction processor with the following 4 stages: (1) Instruction Fetch and Decode (IF), (2) Operand Fetch (OF), (3) Perform Operation (PO) and (4) Write back the result (WB). The IF, OF and WB stages take 1 clock cycle each for any instruction. The PO stage takes 1 clock cycle for ADD or SUB instruction, 3 clock cycles for MUL instruction and 5 clock cycles for DIV instruction. The pipelined processor uses operand forwarding from the PO stage to the OF stage. The number of clock cycles taken for the execution of the above sequence of instructions is _____.

Your answer

Official answer and solution

Official answer: 13
From: Official GATE 2015 answer key

Solution

Trace cycle-by-cycle execution through the 4 pipeline stages (IF, OF, PO, WB) with operand forwarding.

Stage latencies:

IF: 1 cycle
OF: 1 cycle
PO: ADD/SUB = 1 cycle, MUL = 3 cycles, DIV = 5 cycles
WB: 1 cycle
Operand forwarding: Result is available at the end of the PO stage and can be forwarded to the OF stage in the next cycle.

Instruction dependencies:

$I_1$ : MUL R5, R0, R1 (writes R5)
$I_2$ : DIV R6, R2, R3 (writes R6)
$I_3$ : ADD R7, R5, R6 (reads R5 and R6, writes R7)
$I_4$ : SUB R8, R7, R4 (reads R7, writes R8)

Cycle-by-cycle execution trace:

$I_1$ $I_{1}$ (MUL):
- Cycle 1: IF
- Cycle 2: OF
- Cycles 3-5: PO (3 cycles, finishes PO at end of cycle 5)
- Cycle 6: WB
  R5 is forwarded at end of cycle 5.

$I_2$ $I_{2}$ (DIV):
- Cycle 2: IF
- Cycle 3: OF (reads R2, R3 independent of $I_1$ )
- Cycles 4-8: PO (5 cycles, finishes PO at end of cycle 8)
- Cycle 9: WB
  R6 is forwarded at end of cycle 8.

$I_3$ $I_{3}$ (ADD):
- Needs R6 from $I_2$ , which is only ready at the end of cycle 8.
- $I_3$ enters OF in Cycle 9.
- Cycle 9: OF (receives forwarded R6 and R5)
- Cycle 10: PO (1 cycle for ADD, finishes at end of cycle 10)
- Cycle 11: WB
  R7 is forwarded at end of cycle 10.

$I_4$ $I_{4}$ (SUB):
- Needs R7 from $I_3$ , which is forwarded at the end of cycle 10.
- Cycle 11: OF (receives forwarded R7)
- Cycle 12: PO (1 cycle for SUB, finishes at end of cycle 12)
- Cycle 13: WB

The entire sequence completes execution at the end of Cycle 13.
Total clock cycles = 13.

Final answer

Common trap

Stalling $I_2$ behind $I_1$ when their operands and execution units are independent, or forwarding during WB instead of PO.

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

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 2
Question: 54 of 65, printed as CS Q.44
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