Control hazards: branch penalty, flushing, prediction, delayed branch

0 · Recall Warm-up

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

• Stalls between a load and the very next dependent instruction, with forwarding? from Lesson 5.2.3
• RAW, WAR, WAW: which is a true dependence? from Lesson 5.2.2
• PC-relative branch target? from Lesson 1.2.2

1 · The Hook

🎣

The pipeline fetches a new instruction every cycle, but after a branch it does not know which one to fetch until the branch is resolved in EX. Every cycle spent waiting, or fetching the wrong path, is a branch penalty. With branches making up a fifth of all instructions, this is the biggest pipeline loss in GATE problems.

2 · Predict First

🤔

In the 5-stage pipeline, a branch is resolved at the end of EX (cycle 3 if it is fetched in cycle 1). If the pipeline simply waits, in which cycle can the correct next instruction be fetched? How many cycles are lost?

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

3 · Core Concept

💡

Predict First — the answer

Cycle 4; normally it would be fetched in cycle 2, so 2 cycles are lost.

Branch penalty

If the branch outcome (and target) is known at the end of stage r, the next correct fetch is in the cycle after: penalty = r − 1 cycles when the pipeline stalls.

• Resolved in EX (stage 3): 2 cycles.
• Resolved in ID (stage 2, with extra comparison hardware): 1 cycle.
• Resolved in stage 4: 3 cycles.

Policies

• Stall (freeze): stop fetching until resolved. Every branch pays the penalty.
• Predict not taken: keep fetching sequentially. If the branch is not taken, no loss; if taken, flush the wrongly fetched instructions: pay the penalty.
• Predict taken: useful only if the target is known early.
• Delayed branch: the instruction(s) right after the branch (the delay slots) always execute; the compiler fills them with useful instructions that should run either way. A filled slot hides one cycle of penalty.
• Dynamic prediction: hardware remembers past outcomes (1-bit or 2-bit counters, a branch target buffer). Named here only.

CPI with branches

• Stall always: CPI = 1 + f_b × penalty.
• Predict not taken: CPI = 1 + f_b × p_taken × penalty.

Example: 20% branches, 60% taken, penalty 2: stall 1 + 0.4 = 1.4; predict-not-taken 1 + 0.2 × 0.6 × 2 = 1.24.

Counting cycles for a program with a taken branch

A 5-stage pipeline (stages 6, 8, 11, 9, 7 ns; 1 ns latch → τ = 12 ns). 12 instructions; I4 is a branch taken to I9, resolved at the end of stage 4; the pipeline stalls until then.

• Executed: I1, I2, I3, I4, I9, I10, I11, I12 (8 instructions).
• I4 enters stage 1 in cycle 4 and finishes stage 4 in cycle 7; I9 is fetched in cycle 8; I12 is fetched in cycle 11 and finishes in cycle 15.
• Time = 15 × 12 = 180 ns.

4 · Visual

5 · Worked Examples

Example 1 Easy

Branches are resolved in stage 4 of a pipeline that stalls on every branch. Penalty per branch?

Solution

4 − 1 = 3 cycles.

Example 2 Medium

A 5-stage pipeline (branches resolved in EX, stall on branch) runs 10 instructions; the 6th is a branch (taken or not, the pipeline stalls). Total cycles?

Solution

5 + 9 + 2 = 16.

Example 3 GATE

25% branches, 70% taken, penalty 3 cycles, predict-not-taken. CPI?

Solution

1 + 0.25 × 0.7 × 3 = 1.525.

6 · GATE Traps

⚠️

• Penalty = r − 1 for resolution at the end of stage r.
• Predict-not-taken pays only on taken branches.
• Skipped instructions (I5–I8 above) are not counted.
• Delay slots execute always, taken or not.

7 · Memory Hook

🧠

"Know at stage r, lose r − 1." Predict-not-taken: lose only when taken.

8 · Connect the Dots

Chapter 5.2 is complete: structural, data and control hazards and their costs. Chapter 5.3 combines them: full cycle counts with several hazards at once, stages that take several cycles, and comparing whole pipeline designs.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markPenalty

A 6-stage pipeline resolves branches at the end of stage 4 and stalls. Penalty per branch (cycles)?

Numerical answer: ________

Q2NAT2 marksCPI

30% branches, 40% of them taken, penalty 2, predict-not-taken. CPI?

Numerical answer: ________

Q3NAT2 marksProgram cycles

A 5-stage pipeline (branch resolved in EX, stall until resolved). 7 instructions; I3 is a branch taken to I6. How many cycles until the last instruction (I7) completes?

Numerical answer: ________

Q4MCQ1 markDelayed branch

In a delayed branch with one delay slot:

• (A) the pipeline flushes two instructions
• (B) the instruction after the branch executes only if the branch is not taken
• (C) the branch executes one cycle late
• (D) the instruction after the branch always executes

Q5MSQ2 marksPolicies

Which statements are true?

• (A) Stall-on-branch costs nothing for branches that are not taken.
• (B) Moving branch resolution from EX to ID reduces the penalty from 2 to 1 cycle.
• (C) Predict-not-taken loses cycles only on taken branches.
• (D) Compilers fill delay slots with instructions that should execute either way.

10 · Rule Card

• Penalty = r − 1 (resolution at the end of stage r): EX → 2, ID → 1.
• Stall: CPI = 1 + f_b·penalty. Predict-not-taken: 1 + f_b·p_taken·penalty.
• Delay slots always execute; filled slots hide penalty.
• Count only executed instructions; next fetch after resolution.

11 · Concept Ledger

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

branch penaltybranch resolution stagestall on branch (freeze)predict not takenflushpredict takendelayed branch and delay slotdynamic branch predictionbranch target buffer

12 · Answer Vault