Structural hazards and stalls; CPI and speedup with stalls

0 · Recall Warm-up

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

• What does each of IF, ID, EX, MEM, WB do? from Lesson 5.1.3
• Large-n speedup of a balanced k-stage pipeline? from Lesson 5.1.2
• What is a structural reason for separate I- and D-caches? from Lesson 5.1.3

1 · The Hook

🎣

The ideal pipeline finishes one instruction per cycle. Real programs keep breaking that promise: an instruction needs hardware someone else is using, or a value not computed yet, or the program jumps somewhere unexpected. Each such situation is a hazard, and each lost cycle is a stall. Speedup questions in GATE are mostly about counting stalls.

2 · Predict First

🤔

A balanced 6-stage pipeline, no latch overhead. A quarter of the instructions each cause 2 stall cycles. What speedup over the non-pipelined machine?

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

3 · Core Concept

💡

Predict First — the answer

Average CPI = 1 + 0.25 × 2 = 1.5; non-pipelined takes 6 cycles of the same length per instruction: speedup = 6 / 1.5 = 4.

Hazards

A hazard prevents the next instruction from executing in its planned cycle. Three kinds:

• Structural: two instructions need the same hardware in the same cycle.
• Data: an instruction needs a result that is not ready yet (Lessons 5.2.2, 5.2.3).
• Control: the next instruction to fetch depends on a branch not yet resolved (Lesson 5.2.4).

Stalls (bubbles)

The simplest fix: hold the later instruction (and everything behind it) for one or more cycles; an empty slot, a bubble, moves down the pipeline instead.

Structural hazards

Examples:

• One memory port for both instructions and data: a load or store in MEM blocks the IF of a later instruction (1 stall each).
• A non-pipelined unit that takes several cycles (a divider that is busy for 4 cycles): a second divide must wait.
• A register file with too few ports.

Fixes: duplicate the resource (separate I- and D-caches), or pipeline the unit.

CPI and speedup with stalls

CPI_pipelined = 1 + stall cycles per instruction (average).

With balanced stages and no latch overhead, a non-pipelined machine takes k cycles (of the same length) per instruction:

Speedup = k / (1 + stalls per instruction).

In general: Speedup = (CPI_non-pipelined × T_non-pipelined) / (CPI_pipelined × T_pipelined).

Total cycles

For n instructions: k + n − 1 + total stall cycles.

4 · Visual

Single memory port: I1's MEM in cycle 4 blocks I4's fetch for one cycle.

5 · Worked Examples

Example 1 Easy

30% of instructions are loads/stores; with a single memory port each causes 1 stall. CPI?

Solution

1 + 0.3 × 1 = 1.3.

Example 2 Medium

That 5-stage pipeline (balanced, no overhead). Speedup over non-pipelined?

Solution

5 / 1.3 ≈ 3.85.

Example 3 GATE

A 5-stage pipeline at 1 GHz runs 1,000 instructions with 300 stall cycles in total. Time?

Solution

5 + 999 + 300 = 1,304 cycles = 1,304 ns.

6 · GATE Traps

⚠️

• Add stalls to CPI = 1, then divide k by it for the speedup.
• Total cycles still include the k − 1 fill cycles.
• Structural hazards come from shared hardware, not from data values.
• "Instructions that incur 2 stalls" contribute fraction × 2 to CPI.

7 · Memory Hook

🧠

"Speedup = depth ÷ (1 + stalls)."

8 · Connect the Dots

This lesson priced stalls in general and met structural hazards. Next: data dependences, the RAW, WAR and WAW relations between instructions, and which of them actually cause stalls in our pipeline.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markSpeedup with stalls

A balanced 8-stage pipeline without overhead; 20% of instructions incur 3 stall cycles each. Speedup over non-pipelined?

Numerical answer: ________

Q2NAT2 marksCPI

40% of instructions stall 1 cycle and 10% stall 2 cycles. Pipelined CPI?

Numerical answer: ________

Q3MCQ1 markHazard type

A load in MEM and an instruction fetch in IF need the same single-ported memory in the same cycle. This is a:

• (A) control hazard
• (B) WAW hazard
• (C) data hazard
• (D) structural hazard

Q4NAT2 marksTotal cycles

A 6-stage pipeline runs 500 instructions; 120 stall cycles occur. Total cycles?

Numerical answer: ________

Q5MSQ2 marksFixes

Which remove a structural hazard caused by one shared memory port?

• (A) Separate instruction and data caches
• (B) Stalling the conflicting fetch
• (C) Forwarding
• (D) A second memory port

10 · Rule Card

• Hazards: structural (hardware), data (values), control (branches).
• Stall = bubble; CPI = 1 + average stalls.
• Speedup (balanced, no overhead) = k / (1 + stalls); in general (CPI·T)_np / (CPI·T)_p.
• Total cycles = k + n − 1 + stalls.

11 · Concept Ledger

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

hazardstructural hazarddata hazardcontrol hazardstall (bubble)CPI with stallsspeedup = k/(1 + stalls)

12 · Answer Vault