Full cycle counting: mixed hazards and multi-cycle stages

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Branch penalty for resolution at the end of stage r? from Lesson 5.2.4
• Stalls with forwarding for load → next use? from Lesson 5.2.3
• Pipelined time for n instructions? from Lesson 5.1.1

1 · The Hook

🎣

Real GATE pipeline questions mix everything: a multiply that sits in EX for three cycles, a load feeding an add, forwarding available or not, and sometimes a table where every instruction spends a different number of cycles in each stage. One timing rule, applied cell by cell, handles all of them.

2 · Predict First

🤔

A 4-stage pipeline where I1 needs 2 cycles in S1 and I2 needs 1. If I1 starts S1 in cycle 1, when can I2 start S1?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Cycle 3: S1 is busy with I1 for cycles 1–2.

The timing rule

Instruction i may start stage s in the first cycle when all of these hold:

• it has finished stage s − 1;
• the previous instruction has finished its work in stage s (inter-stage buffers hold finished work, so a stage frees up as soon as its work is done);
• any source operand it needs in stage s is available (forwarding rules, Lesson 5.2.3);
• if the previous instruction is a branch, its outcome is known (for stage 1).

Fill a table cell by cell, instruction by instruction. The answer is the last cycle of the last stage of the last instruction.

Per-instruction stage times (GATE format)

Applying the rule:

One pass: 13 cycles. Running I1–I4 twice (a loop): 20 cycles.

Multi-cycle EX in the 5-stage pipeline

MUL spends 3 cycles in EX; others 1. With forwarding:

I1: MUL R1, R2, R3     (EX 3 cycles)
I2: ADD R4, R1, R5
I3: SUB R6, R7, R8
I4: ADD R9, R4, R6

10 cycles (EX is busy until cycle 5, and R1 is forwarded at its end). Without forwarding: I2's ID must reach I1's WB (cycle 7), and so on: 14 cycles.

Out-of-order completion

If a short instruction could pass a long one and write back first, WAW and WAR hazards appear (Lesson 5.2.2). The in-order rule above (condition 2) prevents passing; GATE questions state if they allow it.

4 · Visual

Timing rule for each cell (instruction i, stage s):

   start(i, s) = max( end(i, s-1) + 1 ,          finished previous stage
                      end(i-1, s) + 1 ,          stage free
                      operand ready cycle ,      data hazard
                      branch resolved + 1 )      control hazard (stage 1)
   end(i, s)   = start(i, s) + cycles(i, s) - 1

5 · Worked Examples

Example 1 Easy

In the 4-stage table above, when does I3 start S3, and why not earlier?

Solution

Cycle 7: it finished S2 in cycle 5, but I2 occupies S3 until the end of cycle 6.

Example 2 Medium

Same multiply sequence, but MUL needs 4 cycles in EX (with forwarding). Total cycles?

Solution

I1 EX 3–6, MEM 7, WB 8; I2 EX 7, I3 EX 8, I4 EX 9, MEM 10, WB 11.

Example 3 GATE

How many cycles for the loop for (i = 1 to 2) { I1; I2; I3; I4; }?

Solution

Filling the table for 8 instructions with the timing rule: the last instruction (I4, second iteration) finishes S4 in cycle 23.

6 · GATE Traps

⚠️

• A stage is free when the previous instruction has finished its work there, not when it has moved two stages on.
• Multi-cycle stages block later instructions from that stage.
• Apply the forwarding rule at the end of a multi-cycle EX.
• In a loop, the second iteration's I1 follows the first iteration's I4 directly.

7 · Memory Hook

🧠

"Max of four: my last stage, their this stage, my operands, the branch."

8 · Connect the Dots

This lesson counted cycles for any mix. The final lesson of Phase 5 lifts the view to whole programs: CPI from an instruction mix and comparing pipeline designs with different depths and clocks.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksTable, one pass

Cycles for I1, I2, I3 once?

Numerical answer: ________

Q2NAT2 marksTable, loop

The same three instructions run 3 times in a row (9 instructions). Total cycles?

Numerical answer: ________

Q3NAT2 marksTable, two passes

Cycles for I1–I4 executed twice?

Numerical answer: ________

Q4NAT2 marksMulti-cycle with load

With forwarding (MUL: 3 cycles in EX): LOAD R1, 0(R6) · MUL R3, R1, R4 · ADD R5, R3, R1 · STORE R5, 4(R6). Cycles?

Numerical answer: ________

Q5NAT2 marksWithout forwarding

The same four instructions without forwarding (split-cycle register file). Cycles?

Numerical answer: ________

10 · Rule Card

• start(i,s) = max(end(i,s−1)+1, end(i−1,s)+1, operand ready, branch resolved+1); end = start + cycles − 1.
• Multi-cycle EX blocks later EX; forward at its end.
• Answer = end of last stage of the last instruction.
• Out-of-order completion creates WAR/WAW hazards.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

cell-by-cell timing ruleper-instruction stage latency tablemulti-cycle execution stageinter-stage bufferin-order completion

12 · Answer Vault