Structural hazards

What is a Structural Hazard?

WHY it happens: Pipelining aims to execute multiple instructions simultaneously, but hardware resources are finite and often shared. To reduce cost and complexity, designers may provide only one instance of expensive components (memory, multipliers). When two stages need that component at the same time, we get a structural hazard.

WHAT happens: The pipeline must introduce a stall (also called a bubble or pipeline interlock). The instruction that cannot proceed waits for one or more clock cycles until the resource is free.

HOW it affects performance: Each stall wastes one clock cycle where no new work progresses. If a hazard occurs frequently, the effective CPI increases above the ideal of 1.0.

Common Causes and Examples

1. Single-Port Memory (Most Common)

THE PROBLEM: Classic MIPS has separate instruction and data caches, but consider a system with a single unified memory:

Cycle 1: Instruction A is in IF (Instruction Fetch), reading memory
Cycle 4: Instruction D is in MEM (Memory access), reading/writing data

If both try to access memory simultaneously, we have a structural hazard.

Worked example Single Memory Port Conflict

Pipeline timeline (simplified 5-stage: IF, ID, EX, MEM, WB):

Time:    12    3    4    5    6
I1:     IF   ID   EX  MEM   WB
I2:          IF   ID   EX  MEM   WB
I3:               IF   ID   EX  MEM   WB
I4:                    IF  STALL  IF   ID  ...
               ↑
                     Conflict! I1 in MEM, I4 in IF

Why the stall?: In cycle 4, I1 needs memory for data access (MEM stage) and I4 needs memory for instruction fetch (IF stage). Only one can proceed.

The fix: I4 stalls in IF, waits one cycle. I1 completes its memory access, then I4 fetches its instruction in cycle 5.

Performance impact: CPI increases. If30% of instructions are loads/stores, and the pipeline depth is 5, we get a stall ~every 5/1.3 ≈ 4 instructions = 25% performance loss.

WHY this design exists: Dual-ported memory (separate instruction and data ports) is expensive. Some embedded systems use single-port memory to save cost/power. The Harvard architecture (separate instruction/data memories) avoids this hazard but requires more hardware.

2. Insufficient Functional Units

Worked example Single ALU Shared by Multiple Stages

Some processors use the ALU in both the EX stage (arithmetic) and the IF stage (PC increment: PC = PC + 4).

Conflict scenario:

Cycle 3: ADD instruction EX (needs ALU for addition)
Cycle 3: Next instruction in IF (needs ALU to compute PC+4)

Resolution: Provide a separate ader for PC increment (cheap, simple ader), or stall IF until EX completes.

Modern solution: Dedicated PC incrementer hardware. The cost of a 32-bit adder is tiny compared to the performance loss from frequent stalls.

3. Register File Ports

The register file needs:

Read ports: ID stage reads two source registers (e.g., rs, rt)
Write port: WB stage writes one destination register (rd)

Hazard if: More than 2 reads or 1 write attempted in one cycle.

Mathematical Analysis: Performance Impact

Let's derive the effective CPI when structural hazards occur.

Formula CPI with Structural Hazards

Ideal CPI (perfect pipeline): $\text{CPI}_{\text{ideal}} = 1.0$

Actual CPI with structural hazards: $\text{CPI}_{\text{actual}} = \text{CPI}_{\text{ideal}} + \text{Stall cycles per instruction}$

Stall cycles per instruction: $\text{Stalls} = \text{Frequency of hazard} \times \text{Stall penalty per hazard}$

Example: Memory structural hazard

Fraction of instructions that are loads/stores: $f_{\text{mem}} = 0.30$
These conflict with instruction fetch every $N$ cycles (depends on pipeline depth)
Stall penalty: 1 cycle per conflict If conflicts occur for every memory instruction a 5-stage pipeline: $\text{Stalls} \approx f_{\text{mem}} \times 1 = 0.30 \text{ cycles/instruction}$ $\text{CPI}_{\text{actual}} = 1.0 + 0.30 = 1.30$

Performance loss: $\text{Speedup lost} = \frac{1.0}{1.30} \approx 0.77 \text{ (23\% slower)}$

WHY this formula?: Each stall adds one cycle where the pipeline does no useful work. The frequency of hazards depends on the instruction mix (how often we access memory, use specific units) and the pipeline structure (how many stages can conflict).

Derivation from scratch:

Ideal throughput: One instruction completes per cycle → CPI = 1.0
Stall insertion: When a hazard occurs, insert a "bubble" (NOP). The instruction that would enter the conflicting stage waits one cycle.
Counting stalls: If $p$ is the probability a hazard occurs per instruction, and each hazard costs $s$ cycles, then: $\text{Average stalls per instruction} = p \times s$
Total CPI: $\text{CPI} = 1 + p \times s$

For memory hazards with $p = f_{\text{mem}}$ and $s = 1$ : $\text{CPI} = 1 + f_{\text{mem}}$

Solutions to Structural Hazards

Formula Resolution Strategies

Add hardware resources (eliminate the hazard)

Dual-ported memory or separate I-cache/D-cache
Multiple functional units (2 ALUs, dedicated multiplier)
More register file ports Cost: $\uparrow$ Silicon area, power, design complexity

Pipeline interlock logic (detect and stall)

Hardware detects conflicts, inserts stalls automatically
Control logic: If (stage A needs resource R) AND (stage B needs resource R), stall stage B Cost: $\uparrow$ Control complexity, $\downarrow$ Performance

Schedule instructions (avoid conflicts)

Compiler/programmer reorders instructions to prevent simultaneous resource access
Requires knowledge of pipeline structure

Cost: May not always be possible; limited by dependencies

Accept lower performance (do nothing)

For rare hazards, stalling occasionally may be acceptable
Trade-off: performance vs. cost

WHICH to choose?:

High-performance processors: Add hardware (cost is justified by performance)
Embedded systems: Tolerate occasional stalls (area/power critical)
Modern CPUs: Separate I/D caches standard; structural hazards mostly eliminated

Structural vs. Data vs. Control Hazards

Recall Explain to a 12-year-old

You're playing a video game with your friend, taking turns on a single controller (the controller is like a "resource" in the processor).

Structural hazard: You both need the controller at the exact same time to press buttons. Since there's only one controller, one of you has to wait. That's a structural hazard—not enough controllers (hardware) for everyone who needs one right now.

Data hazard: You need to see what your friend does before you can take your turn (like waiting to see where they move before you move). That's about the order and information passing between you.

Control hazard: You're waiting to see if your friend beats the boss to decide whether you should retry or move to the next level. That's about decisions changing what you do next.

Structural hazards are the simplest: just not enough "stuff" to go around when everyone needs it at once!

| Hazard Type | Cause | Solution | |-------------|----------| | Structural | Hardware resource conflict | Add resources, stall | | Data | Instruction depends on previous result | Forwarding, stall | | Control | Branch outcome unknown | Prediction, stall |

KEY INSIGHT: Structural hazards are the only type caused by hardware limitations, not by the instruction sequence itself. Data and control hazards exist even with unlimited hardware—they're about dependencies and decisions. Structural hazards can be eliminated with enough money (duplicate every resource), but data/control hazards are fundamental to the algorithm.

Common Mistakes and Steel-Manning

Common mistake Mistake 2: "Adding a bubble completely wastes a clock cycle"

Why it feels right: The instruction that stalls does no work during the bubble cycle, so it seems like "wasted time."

The truth: The pipeline still does work for other instructions. The stall prevents one instruction from advancing, but instructions ahead of it continue progressing. The throughput decreases (CPI > 1), but the pipeline doesn't sit completely idle.

Example:

Before stall:  I1[MEM] I2[EX] I3[ID] I4[IF]
Stall cycle:   I1[WB]  I2[MEM] I3[EX] I4[stall] (I4 waits)
After stall:   done    I2[WB]  I3[MEM] I4[ID]   (I4 resumes)

The fix: A stall reduces throughput (fewer instructions per second) but doesn't freeze the entire pipeline. Think of it as one lane of a highway stopping while others keep moving.

Worked Example: Analyzing a Hazard Scenario

Worked example Full Pipeline Trace with Structural Hazard

Setup: 5-stage pipeline (IF, ID, EX, MEM, WB), single unified memory (no separate I/D caches).

Instruction sequence:

I1: LW  R1, 0(R2)    # Load from memory
I2: ADD R3, R1, R4
I3: SUB R5, R3, R6
I4: SW  R5, 0(R7)    # Store to memory
I5: AND R8, R5, R9

Pipeline timeline (clock cycles):

    1    2    3    4    5    6    7    8    9
I1: IF   ID   EX  MEM   WB
I2:      IF   ID   EX  MEM   WB
I3:           IF   ID   EX  MEM   WB
I4:              STALL  IF   ID   EX  MEM   WB
I5:                         IF   ID   EX  MEM   WB

Why the stall in cycle 4?

I1 is in MEM stage (cycle 4): needs memory to load data
I4 should be in IF stage (cycle 4): needs memory to fetch instruction
Conflict: Only one memory access allowed per cycle
Resolution: I4 stalls, waits until cycle 5 to fetch its instruction

Performance impact:

Ideal cycles: 5 instructions, ideal CPI = 1.0 → 9 cycles total (5 + pipeline depth - 1 = 5 + 4)
Actual cycles: 10 cycles (one extra stall)
Actual CPI: 10/5 = 2.0 (terrible! 100% overhead from just one stall)

Wait, that calculation is wrong. Let me recalculate:

Ideal: First instruction takes 5 cycles, then one per cycle → total = 5 + (5-1) = 9 cycles
Actual: 9 + 1 stall = 10 cycles
CPI: 10/5 = 2.0? No, wait—CPI calculation:
Total cycles = 10
Total instructions = 5
CPI = 10/5 = 2.0 is correct, but this seems high for one stall.

Actually, I need to reconsider. Let me trace more carefully: Correct timeline:

    1    2    3    4    5    6    7    8    9
I1: IF   ID   EX  MEM   WB
I2:      IF   ID   EX  MEM   WB
I3:           IF   ID   EX  MEM   WB
I4:                IF   ID   EX  MEM   WB
               ↑ Conflict with I1[MEM] in cycle 4

In cycle 4: I1 is in MEM, I4 wants to do IF. Stall I4.

    1    2    3    4    5    6    7    8    9   10
I1: IF   ID   EX  MEM   WB
I2:      IF   ID   EX  MEM   WB
I3:           IF   ID   EX  MEM   WB
I4:              STALL  IF   ID   EX  MEM   WB
I5:                         IF   ID   EX  MEM   WB

Total cycles: 9 (I5 completes in cycle 9, WB stage) Wait, let me count: I5[WB] in cycle 9 means 9 cycles total.

Hm, but we had a stall. Let me re-trace:

The stall means I4 and all subsequent instructions shift by 1 cycle:

    1    2    3    4    5    6    7    8    9   10
I1: IF   ID   EX  MEM   WB
I2:      IF   ID   EX  MEM   WB
I3:           IF   ID   EX  MEM   WB
I4:                    IF   ID   EX  MEM   WB    (shifted by stall)
I5:                         IF   ID   EX  MEM   WB

Wait, that's still wrong. When I4 stalls in cycle 4, it doesn't do IF. It does IF in cycle 5:

    1    2    3    4    5    6    7    8    9   10
I1: IF   ID   EX  MEM   WB
I2:      IF   ID   EX  MEM   WB
I3:           IF   ID   EX  MEM   WB
I4:               X    IF   ID   EX  MEM   WB
I5:                         IF   ID   EX  MEM   WB

X = stall (no progress). Now I5 in cycle 5 also can't do IF because I4 is doing IF. So I5 waits:

    1    2    3    4    5    6    7    8    9   10
I1: IF   ID   EX  MEM   WB
I2:      IF   ID   EX  MEM   WB
I3:           IF   ID   EX  MEM   WB
I4:               X    IF   ID   EX  MEM   WB
I5:                    X    IF   ID   EX  MEM   WB

Wait, this cascades? Let me think about this differently.

Correct understanding: When I4 stalls in cycle 4, the pipeline inserts a bubble in front of I4. I4 doesn't advance, so neither does I5:

    1    2    3    4    5    6    7    8    9
I1: IF   ID   EX  MEM   WB
I2:      IF   ID   EX  MEM   WB
I3:           IF   ID   EX  MEM   WB
I4:                IF   ID   EX  MEM   WB
I5:                         IF   ID   EX  MEM   WB

In cycle 4, I4's IF is blocked. I4 stays in "waiting to enter IF." In cycle 5, I1 exits MEM, memory is free, I4 does IF. Total time: 9 cycles.

CPI calculation:

5 instructions in 9 cycles: CPI = 9/5 = 1.8 Without hazard: 5 instructions in 9 cycles (wait, that's the same!)

Let me recalculate the ideal case:

First instruction: 5 cycles (IF cycle 1, WB in cycle 5)
Subsequent instructions: one per cycle (pipelining)
Total for 5 instructions: 5 + (5-1) = 9 cycles So the ideal is also 9 cycles? Then where's the stall penalty?

AH! I see the issue: In my timeline, I4 entering IF in cycle 4 is already the ideal case (no structural hazard). Let me redo this with the hazard:

WITH structural hazard (I1[MEM] conflicts with I4[IF] in cycle 4):

    1    2    3    4    5    6    7    8    9   10
I1: IF   ID   EX  MEM   WB
I2:      IF   ID   EX  MEM   WB
I3:           IF   ID   EX  MEM   WB
I4:              (stall) IF   ID   EX  MEM   WB
I5:                          IF   ID   EX  MEM   WB

Total: 10 cycles. CPI = 10/5 = 2.0. WITHOUT hazard (separate I/D memory):

    1    2    3    4    5    6    7    8    9
I1: IF   ID   EX  MEM   WB
I2:      IF   ID   EX  MEM   WB
I3:           IF   ID   EX  MEM   WB
I4:                IF   ID   EX  MEM   WB
I5:                     IF   ID   EX  MEM   WB

Total: 9 cycles. CPI = 9/5 = 1.8.

Penalty: 1 cycle stall, 11% performance loss (9/10 = 0.9 speedup).

Connections

Pipelining Fundamentals - Structural hazards are one of three hazard types
Data Hazards - Compare resource conflicts vs. data dependencies
Control Hazards - Branch prediction vs. hardware duplication trade-offs
Memory Hierarchy - Separate I/D caches eliminate memory structural hazards
Superscalar Processors - Multiple issue requires many more resources, more structural hazards
Pipeline Stalls - Mechanism for handling all hazard types
Instruction-Level Parallelism - Resource constraints limit ILP extraction

#flashcards/hardware

What is a structural hazard? :: A pipeline hazard caused by resource conflicts when multiple instructions need the same hardware component simultaneously (e.g., memory, ALU, register ports).

What causes the most common structural hazard in basic pipelined processors?

Single-port unified memory: instruction fetch (IF stage) conflicts with data access (MEM stage).

How does a structural hazard affect CPI?

It increases CPI above 1.0 by inserting stalls. CPI_actual = CPI_ideal + (frequency of hazard × stall penalty).

What are the two main solutions to structural hazards?

(1) Add hardware resources (duplicate memory, functional units, ports) to eliminate conflicts. (2) Insert pipeline stalls to serialize access to the shared resource.

Why do modern high-performance processors have few structural hazards?

They use separate instruction and data caches (Harvard architecture), multiple functional units, and multi-ported register files, duplicating resources to avoid conflicts.

How is a structural hazard different from a data hazard?

Structural: hardware resource conflict (not enough hardware). Data: instruction dependency (waiting for result). Structural can be eliminated by adding hardware; data hazards are algorithmic.

What is the performance penalty of a single structural hazard stall?

One clock cycle per stall. If stalls are frequent (e.g., 30% of instructions), CPI can increase from 1.0 to 1.3, losing ~23% performance.

When might a designer accept structural hazards instead of adding hardware?

In cost/power-sensitive embedded systems, or when the hazard is rare enough that the performance loss is acceptable compared to the cost of duplicating hardware.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho yaar, structural hazard ka core idea bilkul simple hai - jaise ghar mein ek hi bathroom ho aur do log ek saath usko use karna chahein, toh ek ko wait karna padega. Same cheez processor ke andar hoti hai. Jab hum pipelining karte hain, tab multiple instructions ek saath different stages mein chal rahi hoti hain. Ab agar do stages ek hi hardware resource ko (jaise memory, ALU, ya register file port) same clock cycle mein use karna chahein, toh conflict ho jaata hai. Isko kehte hain structural hazard, aur iska solution hota hai ek instruction ko "stall" karna, matlab ek cycle wait karwana jab tak resource free na ho jaye.

Ab yeh happen kyun hota hai? Kyunki hardware resources mehenge hote hain, toh designers paisa aur complexity bachane ke liye kabhi kabhi sirf ek hi instance dete hain expensive components ka. Classic example hai single unified memory - jab ek instruction apna data access kar rahi hoti (MEM stage) aur doosri instruction ko fetch karna hai (IF stage), dono ko ek saath memory chahiye, par memory ke paas sirf ek hi port hai. Isse ek ko rukna padta hai. Iska common fix hai Harvard architecture use karna, jisme instruction aur data ke liye alag alag memory hoti hai, ya phir dual-ported memory - par yeh sab extra hardware maangte hain.

Yeh cheez matter kyun karti hai? Kyunki pipelining ka pura goal hai ideal CPI (Cycles Per Instruction) ko 1.0 ke kareeb laana, matlab har cycle mein ek naya kaam complete ho. Par jab bhi stall aata hai, ek cycle waste ho jaata hai aur CPI badh jaati hai, jisse performance girti hai. Jaise agar 30% instructions load/store hain, toh frequently stalls aate hain aur 25% tak performance loss ho sakta hai. Isliye smart designers chhote-chhote solutions dete hain, jaise PC increment ke liye ek separate cheap adder, taaki main ALU free rahe. Yeh trade-off samajhna zaroori hai - thoda extra hardware kabhi kabhi bahut zyada performance bacha leta hai.

What is a Structural Hazard?

Common Causes and Examples

1. Single-Port Memory (Most Common)

2. Insufficient Functional Units

3. Register File Ports

Mathematical Analysis: Performance Impact

Solutions to Structural Hazards

Structural vs. Data vs. Control Hazards

Common Mistakes and Steel-Manning

Worked Example: Analyzing a Hazard Scenario

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Processor Datapath & Pipelining

Connections